Ханойская башня почти всегда встречается, когда в программировании изучают рекурсию. Руками её решают сотни ходов, а в программе хватает нескольких строк. Давайте разберёмся, как это устроено. Стержни называются левый, средний и правый, а диски нумеруются от самого маленького: 1, 2, 3…
Что такое рекурсия
Рекурсия — это когда в решении задачи та же самая процедура применяется к задаче поменьше. Если уменьшать задачу дальше, рано или поздно дойдёшь до такой, ответ на которую очевиден (например, для 0 дисков ничего делать не нужно), и тогда всё останавливается.
Ханойская башня через рекурсию
Представим, что нужно перенести башню из n дисков слева направо.
- Перенести верхние n − 1 дисков с левого стержня на средний.
- Переместить самый большой диск n с левого стержня на правый.
- Перенести 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. Связь числа ходов с двоичной записью подробнее объясняется в статье о закономерностях.
