Ханойская башня: история и решение задачи¶

Ханойская башня — классическая математическая головоломка и алгоритмическая задача, в которой требуется переместить набор дисков разного диаметра с одного стержня на другой, используя вспомогательный стержень и соблюдая ограничения на порядок перемещений. Задача служит стандартным примером рекурсии в программировании и иллюстрирует экспоненциальный рост числа операций.

¶Условие задачи

Даны три стержня и несколько дисков разного размера, нанизанных на первый стержень в порядке убывания диаметра (самый большой — снизу). Требуется перенести всю пирамиду на третий стержень, соблюдая правила:

• за один ход перемещается только один диск;
• диск можно класть лишь на пустой стержень или на диск большего диаметра;
• больший диск нельзя класть на меньший.

Классический вариант предполагает три стержня; при большем их числе задача усложняется и допускает иные оптимальные стратегии.

¶Происхождение

Головоломку популяризировал французский математик Эдуард Люка в 1883 году под названием «Башня Брамы». Согласно легенде, в одном из храмов Бенареса монахи перекладывают 64 золотых диска, и когда они завершат работу, наступит конец света. Легенда имеет литературное происхождение и не подтверждается историческими источниками. Название «Ханойская башня» закрепилось позднее, вероятно, из-за ассоциации с Вьетнамом и восточным колоритом.

¶Решение

Оптимальное решение строится рекурсивно. Чтобы переместить n дисков со стержня A на стержень C:

1. переместить n−1 верхних дисков с A на вспомогательный стержень B;
2. переместить самый большой диск с A на C;
3. переместить n−1 дисков с B на C.

Минимальное число ходов описывается формулой:

T(n) = 2ⁿ − 1.

Для трёх дисков требуется 7 ходов, для четырёх — 15, для 64 — 2⁶⁴ − 1, что составляет примерно 1,8·10¹⁹ ходов. При скорости один ход в секунду на это ушло бы порядка 585 миллиардов лет, что многократно превышает возраст Вселенной.

¶Итеративный подход

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

¶Связь с системами счисления

Число ходов 2ⁿ − 1 в двоичной записи представляет собой n единиц. Положение дисков в процессе решения можно сопоставить с двоичным счётчиком: каждый ход соответствует инкременту, а позиция самого младшего единичного разряда указывает номер перемещаемого диска. Эта аналогия используется в задачах о кодах Грея.

¶Применение и значение

Ханойская башня применяется в обучении:

• как пример рекурсии и анализа сложности алгоритмов;
• для демонстрации экспоненциального роста;
• в психологии — в тестах на планирование и решение задач (например, в нейропсихологической диагностике).

Задача также встречается в исследованиях по теории графов: граф состояний головоломки образует так называемый граф Ханоя, свойства которого изучаются в комбинаторике.

¶Варианты

Известны обобщения: четыре и более стержней (задача Тауэра Лондона), ограничения на направление перемещений, диски разной толщины, а также «циклическая» башня, где разрешены ходы только по кругу. Для четырёх стержней оптимальное число ходов меньше, чем 2ⁿ − 1, и точная формула была найдена лишь в 2014 году.