Есть такая классическая задачка, ну или игра: Ханойские башни. Суть в следующем: есть три шеста, на один нанизаны диски, в порядке убывания радиуса. Вроде детской "пирамидки". Два других шеста пусты. Надо перенести диски на другой шест так, чтобы диск диаметром больше не оказался на диске диаметром меньше. Можно использовать третий шест в качестве промежуточного.
Вопросы: возможно ли это? Как это сделать, если это возможно? Сколько операций (переносов дисков) понадобится?
Задачка известна тем, что она типично рекурсивная. Рекурсивным называется алгоритм (или задача), который сводится сам к себе.
Типичные шутки про рекурсию: статья "рекурсия" в толковом словаре отсылает к статье "рекурсия", салат "Рекурсивный" делается из помидоров, огурцов и салата "Рекурсивный", коктейль Рекурсия содержит 30% воды, 20% спирта и 50% коктейля (и сходится к 60:40 строго по Менделееву).
Очень важно, что многие определения рекурсивны по смыслу, но не по сути. Например, факториал: его можно определить так: 0!=1, (n+1)!=n!∙(n+1), то есть рекурсивно, но вычислять это лучше циклом, а не строго как написано.
А ханойские башни рекурсивны по сути.
Пусть у нас есть алгоритм переноса n (и менее) дисков. Надо перенести n+1 диск с шеста номер 1 на шест номер 2.
- Переносим n верхних дисков на шест номер 3.
- Переносим оставшийся самый большой диск на шест номер 2.
- Переносим всё (там n дисков) с шеста номер 3 на шест номер 1.
Всё.
Осталось только убедиться, что башню из одного диска мы перенести можем. Можем.
Пусть число дисков равно N. А число переносов M(N) подчинено уравнению
M(N+1) = 2M(N)+1,
что очевидно, если посмотреть на алгоритм.
Это уравнение разностное, нелинейное, но аффинное. Решим сначала вспомогательное линейное уравнение M(N+1)=2M(N).
Его решение очевидно: это M(N)=C∙2ᴺ при любом числе С.
Одно решение исходного уравнение легко подбирается: это константа -1. И легко видеть, что сумма двух решений (вспомогательного и частного) является решением уравнения: M(N)=C∙2ᴺ-1. И это исчерпывает все решения.
Константу подберем из тривиального условия: если башня из одного диска, то задача решается в один ход: M(1)=1. Отсюда С=1.
В итоге число переносов растет как степень двойки, что роднит задачу с задачей о шахматной доске. Для 10-12 дисков всё просто, но возьми шестьдесят, и у тебя серьезные проблемы. Недаром в легенде говорится, что жрецы где-то там переносят диски, и когда закончат - будет конец света.
Давайте строго докажем разрешимость задачи. Для N=1 всё понятно. Действуем по индукции; пусть всё корректно для некоторого N=n, и проверим корректность для N=n+1.
Ну, перенос верхних n дисков на пустой шест по предположению корректен: не придется класть большой диск на малый. Перенос большого диска с шеста (на котором он один) на пустой шест тоже делается. Далее мы переносим n дисков на этот самый большой, что корректно. Корректность доказана.
Как же действовать на практике? Сначала вы стоите у башни из 6 дисков и бубните: перенос пяти на 3... перенос четырех на 2... перенос трех на 3... перенос двух на 2... перенос одного на 3! Переносим верхний диск на шест-3. Переносим следующий на шест-2. Переносим с 3 на 2. Ну а далее по схеме.
Вот решение для трех дисков:
А вот мой код на Перле:
Есть скрипт для Вим, который играет в эту игру и позволяет играть вам. Но он для графической версии. Может быть, сделать в рамках рубрики про Вим такой скрипт для консоли?