Прыг-прыг. Алгоритмическая головоломка о лягушках

Прыг-прыг. Алгоритмическая головоломка о лягушках

Как вы могли заметить по логотипу, Библиотеке программиста нравятся лягушки ��. Как настоящие ( T ), так и игрушечные ( F ). Однажды мы наблюдали такую сценку. На одномерной доске с 2n + 1 ячейками в первых n ячейках разместились n истинных лягушек в n первых ячейках и n лягушек-игрушек в последних n ячейках. По одной лягушке в ячейке, и ещё одна ячейка, разделяющая семейства. На рисунке показан случай для n = 3 .

В рамках хода лягушка прыгает на пустую клетку. Напрямик или перепрыгнув через представителя противоположного семейства. Через своих сородичей лягушки одного типа не прыгают, это считается неуважительным. Трушные лягушки двигаются только вправо, фейковые – влево. Каждый тип может делать более одного хода подряд. В результате перепрыгиваний они хотят обменяться местами, как на картинке.

Вопрос: сколько ходов потребуется для 3 T и 3 F ? Предложите алгоритм решения задачи.

Вопрос со звёздочкой ��: сколько ходов нужно для m T и n F , если m и n не равны?

Программное решение✨: попробуйте реализовать визуализацию решения для общего случая (из вопроса со звёздочкой) на любимом языке программирования. Напишите функцию, которая принимает на вход числа m и n , а возвращает число ходов, а также последовательность строк, содержащих T , F и пробел для пустой ячейки. Каждая строка соответствует одном ходу.

Эта задача – четырнадцатый эпизод нашего сериала головоломок. После описания задачи идёт ответ на предыдущую – задачу о взломе банковского замка.

Решение задачи о взломе банковского замка

Решение. Решим задачу в общем случае, то есть для любого числа n . Пронумеруем переключатели слева направо от 1 до n и обозначим состояния переключателя «включено» и «выключено» соответственно как 1 и 0 . Чтобы помочь себе в решении общего случая головоломки, начнём с решения четырёх самых простых примеров.

Прыг-прыг. Алгоритмическая головоломка о лягушках

Теперь рассмотрим общий пример головоломки, когда исходная строка состоит из n единиц:

Прежде чем мы сможем выключить самый левый переключатель, переключатели должны находиться в состоянии

Следовательно, для начала нам нужно отключить последние n – 2 переключателей и сделать это за минимальное количество ходов. Другими словами, мы должны сначала решить ту же проблему, что и для последних n – 2 переключателей. Это может быть сделано рекурсивно с использованием решений для случаев n = 1 и n = 2 .

После этого мы сможем переключить первый переключатель, чтобы получить

Теперь, прежде чем мы сможем переключить второй переключатель, нам придётся пройти через такое состояние, при котором все переключатели, следующи за ним будут «вкл». Перевести все переключатели с третьего по последний на «вкл» можно, поменяв последовательность ходов, сделанных ранее, на обратную, чтобы переключить последние n – 2 переключателей из положения «вкл» в положение «выкл». Это даст нам

Обозначим M(n) количеством переключений, сделанных алгоритмом. Получится следующее рекуррентное выражение:

Это выражение действует для n ≥ 3 , при этом известно, что M(1) = 1 , M(2) = 2 . Решение рекуррентного уравнения по стандартной методике для линейных неоднородных рекуррентных уравнений второго порядка с постоянными коэффициентами даёт следующий необычный результат:

Для чётных n данная формула сводится к

Действительно: если n = 7 , то M(n) = 85 .

Как ответили читатели Библиотеки программиста? Алгоритмические ответы с указанием рекуррентных соотношений дали читатели lasangqwerty и maximzombi:

Читатель wil4 привёл саму последовательность переключений:

Также задача подробно обсуждалась в нашем сообществе вк, там вы можете увидеть много различных подходов, в том числе ручной перебор и программные решения. Первым точное решение привёл Сергей Семёнов.