(no subject)
Наткнулся примерно месяц назад на http://rosalind.info/ на такую задачку.
Даны две перестановки чисел от 1 до n (n < 11). Перестановку разрешается изменять только выполняя т.н. развороты. Скажем, 1 4 5 2 6 3 можно поменять на 1 4 6 2 5 3.
Спрашивается, за какое минимальное количество разворотов можно получить из одной перестановки другую?
Тут самое интересное. Там есть подсказка. Которую я не открывал, конечно, и думал сам. Первое, приходящее в голову решение (жадное) не даёт минимум. Следующее решение, которое мне пришло в голову, оказалось перебором (стыдно даже сказать, каким именно) и там всё грустно со временем (а надо успеть за 5 минут).
Когда я открыл подсказку, там оказалось следующее: "Don't be afraid to try an ugly solution". Я оценил чувство юмора разработчиков. Видимо, есть ugly решение, но менее ugly, чем моё. Прямо континуум-гипотеза...
За последнее время я узнал, что полиномиальное решение существует (за n3), и было найдено совсем недавно. Но это решение, мне кажется, точно не заслуживает того, чтобы называться ugly.
Даны две перестановки чисел от 1 до n (n < 11). Перестановку разрешается изменять только выполняя т.н. развороты. Скажем, 1 4 5 2 6 3 можно поменять на 1 4 6 2 5 3.
Спрашивается, за какое минимальное количество разворотов можно получить из одной перестановки другую?
Тут самое интересное. Там есть подсказка. Которую я не открывал, конечно, и думал сам. Первое, приходящее в голову решение (жадное) не даёт минимум. Следующее решение, которое мне пришло в голову, оказалось перебором (стыдно даже сказать, каким именно) и там всё грустно со временем (а надо успеть за 5 минут).
Когда я открыл подсказку, там оказалось следующее: "Don't be afraid to try an ugly solution". Я оценил чувство юмора разработчиков. Видимо, есть ugly решение, но менее ugly, чем моё. Прямо континуум-гипотеза...
За последнее время я узнал, что полиномиальное решение существует (за n3), и было найдено совсем недавно. Но это решение, мне кажется, точно не заслуживает того, чтобы называться ugly.