Для n дисков в Ханойской башне наименьшее число ходов, за которое можно перенести башню на другой стержень, равно 2ⁿ − 1. Это число получается, если перемножить n двоек и вычесть 1.
| Число дисков | Минимум ходов |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
С каждым новым диском число ходов примерно удваивается. Давайте разберём по порядку, почему так получается.
Смотрим на самый большой диск
Пусть башню из n дисков нужно перенести слева направо. Самый большой диск лежит под остальными, поэтому сразу его не сдвинуть. Чтобы перенести его вправо, в этот момент должно выполняться следующее.
- Сверху на большом диске ничего нет.
- Правый стержень свободен (ведь диск побольше нельзя положить на диск поменьше).
Значит, остальные n − 1 дисков должны лежать башней на среднем стержне.
Делим ходы на три части
Отсюда перенос n дисков делится на три части.
- Перенести верхние n − 1 дисков с левого стержня на средний.
- Одним ходом переместить самый большой диск с левого стержня на правый.
- Перенести n − 1 дисков со среднего стержня на большой диск.
Части 1 и 3 — это та же самая задача «перенести башню из n − 1 дисков». Если обозначить наименьшее число ходов для n дисков через T(n), то
T(n) = T(n − 1) + 1 + T(n − 1) = 2 × T(n − 1) + 1.
Для одного диска нужен 1 ход, поэтому T(1) = 1. Отсюда по порядку получаются 3, 7, 15, 31…
Почему получается 2ⁿ − 1
Если прибавить 1 к обеим частям этого соотношения, получится
T(n) + 1 = 2 × (T(n − 1) + 1).
Значит, «число ходов плюс 1» с каждым новым диском увеличивается ровно вдвое. Для одного диска T(1) + 1 = 2, поэтому для n дисков получается 2 в n-й степени, то есть 2ⁿ. Вычтем 1 — и T(n) = 2ⁿ − 1.
Почему короче нельзя
Мы увидели, что по такому порядку можно перенести башню за 2ⁿ − 1 ходов. А нет ли способа перенести её за меньшее число ходов?
Как мы выяснили, в тот момент, когда самый большой диск двигают в первый раз, все остальные n − 1 дисков должны лежать на одном другом стержне. До этого момента нужно сделать не меньше ходов, чем требуется для переноса башни из n − 1 дисков. Так же и после того, как большой диск в последний раз положили вправо, чтобы собрать остальные n − 1 дисков на нём, нужно сделать не меньше ходов, чем для переноса башни из n − 1 дисков. Сам большой диск тоже нужно сдвинуть как минимум один раз.
При любом порядке ходов эти три части обязательно потребуются. Поэтому меньше, чем 2 × T(n − 1) + 1 ходов, не получится. Известно также, что кратчайшее решение на самом деле только одно.
В режиме «Классика» приложения — 127 ходов
В режиме «Классика» приложения «Ханойская башня» 7 дисков, поэтому наименьшее число ходов — 2⁷ − 1 = 127. Если у вас получилось 127 ходов, вы решили задачу кратчайшим путём. Если двигать маленький диск всё время в одну сторону по кругу, как рассказано в статье о правилах и игре, башня будет собрана ровно за 127 ходов.
