История и легенда
Головоломку придумал французский математик Эдуард Люка в 1883 году. Чтобы сделать её интереснее, он сопроводил игрушку легендой: где-то в храме монахи перекладывают 64 золотых диска по тем же правилам, и когда закончат, наступит конец света. Беспокоиться не стоит: даже при одном ходе в секунду на это понадобится больше полутриллиона лет.
Минимальное число ходов
Для n дисков минимум — 2ⁿ − 1 ходов. Каждый новый диск удваивает задачу и добавляет ещё один ход.
| Дисков | Минимум ходов |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
Как решать
У задачи красивое рекурсивное решение: чтобы перенести башню из n дисков, нужно перенести верхние n − 1 дисков на вспомогательный стержень, переложить самый большой диск на целевой, а затем перенести n − 1 дисков сверху. Для практики удобнее простое правило:
- Самый маленький диск ходит через ход, всегда по кругу в одном направлении.
- Если дисков нечётное число — первым ходом кладите маленький диск на целевой стержень; если чётное — на вспомогательный.
- Между ходами маленького диска делайте единственный возможный ход другим диском.
Что тренирует
Ханойская башня — классическая задача на планирование: нужно думать на несколько шагов вперёд и разбивать большую цель на подзадачи. Похожие головоломки («Лондонская башня») используют в нейропсихологии для оценки исполнительных функций. В жизни этот навык помогает разложить сложный проект на последовательность простых действий.