Ханойская башня почти всегда встречается, когда в программировании изучают рекурсию. Руками её решают сотни ходов, а в программе хватает нескольких строк. Давайте разберёмся, как это устроено. Стержни называются левый, средний и правый, а диски нумеруются от самого маленького: 1, 2, 3…

Что такое рекурсия

Рекурсия — это когда в решении задачи та же самая процедура применяется к задаче поменьше. Если уменьшать задачу дальше, рано или поздно дойдёшь до такой, ответ на которую очевиден (например, для 0 дисков ничего делать не нужно), и тогда всё останавливается.

Ханойская башня через рекурсию

Представим, что нужно перенести башню из n дисков слева направо.

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

Шаги 1 и 3 — это задача «перенести башню из n − 1 дисков», точно такая же, как исходная. Отличается только то, откуда и куда переносят. Поэтому достаточно написать одну процедуру «перенести n дисков с одного стержня на другой, используя оставшийся», и внутри неё можно вызывать саму себя.

Псевдокод

процедура hanoi(n, откуда, куда, запасной):
    если n равно 0, ничего не делаем и выходим
    hanoi(n − 1, откуда, запасной, куда)    … убираем верхние n−1 дисков
    переместить диск n со стержня «откуда» на стержень «куда»
    hanoi(n − 1, запасной, куда, откуда)    … возвращаем n−1 дисков

hanoi(3, левый, правый, средний) даёт ходы для переноса 3 дисков слева направо

Этого достаточно, чтобы получить решение с наименьшим числом ходов для любого числа дисков. Рабочий код на Python и C есть в статье Решаем Ханойскую башню на Python и C.

Как разворачиваются вызовы

Если выписать, как вызывается hanoi для 3 дисков, получится дерево. Чем глубже отступ, тем более вложенный вызов.

hanoi(3, левый→правый)
├─ hanoi(2, левый→средний)
│   ├─ hanoi(1, левый→правый)     … диск 1 вправо
│   ├─ диск 2 на средний
│   └─ hanoi(1, правый→средний)   … диск 1 на средний
├─ диск 3 вправо
└─ hanoi(2, средний→правый)
    ├─ hanoi(1, средний→левый)    … диск 1 влево
    ├─ диск 2 вправо
    └─ hanoi(1, левый→правый)     … диск 1 вправо

Если читать сверху вниз только строки с перемещениями, получится ровно ответ из 7 ходов. Один вызов порождает внутри два вызова, поэтому с каждым новым диском объём работы почти удваивается.

Сложность

Что считаемДля n дисков
Число перемещений (ходов)2ⁿ − 1
Число вызовов hanoi (вызовы с 0 дисков тоже считаем)2ⁿ⁺¹ − 1
Глубина вызовов (сколько нужно помнить одновременно)n + 1 уровень

Почему ходов ровно 2ⁿ − 1, доказано в статье о формуле минимального числа ходов. Время растёт экспоненциально с числом дисков (O(2ⁿ)), а объём памяти — только пропорционально числу дисков (O(n)). Самих ходов 2ⁿ − 1, поэтому как ни изощряйся, чтобы выписать всё решение, потребуется не меньше времени.

Решение без рекурсии

Можно решить задачу и без рекурсии, одним циклом. Это ровно тот порядок действий для ручного решения, о котором рассказано в статье о том, как решать головоломку.

процедура hanoi_loop(n):
    выбрать направление диска 1 (если n нечётное: левый→правый→средний; если чётное: левый→средний→правый)
    повторять для хода = 1, 2, 3, … , 2ⁿ − 1:
        если ход нечётный, перенести диск 1 на следующий стержень в выбранном направлении
        если ход чётный, сравнить верхние диски двух стержней, где диска 1 нет,
                         и переложить меньший на больший (или на пустой стержень)

Помнить вызовы, как при рекурсии, не нужно, поэтому памяти почти не требуется.

Любой ход напрямую через двоичную запись

Есть и способ найти, что делать на любом ходу, не прослеживая все предыдущие. Пронумеруем стержни 0, 1 и 2. Для хода m (счёт с 1):

  • Двигают диск с номером (число нулей в конце двоичной записи m) + 1.
  • Стержень, с которого двигают, — остаток от деления (m AND (m − 1)) на 3.
  • Стержень, на который двигают, — остаток от деления ((m OR (m − 1)) + 1) на 3.

AND и OR — это поразрядные операции над двоичными числами, «и» и «или». Например, для m = 4 (в двоичной записи 100) в конце два нуля, поэтому двигают диск 3. Стержень, с которого двигают: (4 AND 3) = 0, то есть стержень 0. Стержень, на который двигают: ((4 OR 3) + 1) = 8, а остаток от деления 8 на 3 равен 2, то есть стержень 2.

Ходы, которые даёт эта формула, переносят башню со стержня 0 на стержень 2, если дисков нечётное число, и со стержня 0 на стержень 1, если чётное. Если нужно перенести чётное число дисков на стержень 2, при чтении поменяйте местами стержни 1 и 2. Связь числа ходов с двоичной записью подробнее объясняется в статье о закономерностях.