Если решать Ханойскую башню за наименьшее число ходов, в решении обнаруживаются удивительно красивые закономерности. Здесь мы по порядку расскажем о тех, что найдены для кратчайшего решения (2ⁿ − 1 ходов) при переносе башни из n дисков слева направо. Диски нумеруются от самого маленького: 1, 2, 3…
Сколько раз двигается каждый диск — степень двойки
В кратчайшем решении число ходов каждого диска определено. При n дисках диск с номером k двигается 2ⁿ⁻ᵏ раз.
| Диск (при 4 дисках) | Сколько раз двигается |
|---|---|
| 1 | 8 |
| 2 | 4 |
| 3 | 2 |
| 4 | 1 |
| Всего | 15 |
Самый большой диск двигается 1 раз, следующий — 2 раза, следующий — 4 раза, и так далее: с уменьшением диска число ходов удваивается. В сумме 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1, то есть ровно наименьшее число ходов.
Причину можно понять так же, как в статье о формуле минимального числа ходов. Чтобы перенести n дисков, башню из n − 1 дисков переносят дважды. Поэтому диски меньше n двигаются вдвое больше раз, чем при переносе n − 1 дисков.
Какой диск двигается на каком ходу
Если выписать по порядку номера дисков, которые двигаются в кратчайшем решении для 4 дисков, получится следующее.
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Диск 1 встречается через ход, между ними через один встречается 2, между ними — 3, и так далее. Эта последовательность устроена так же, как длина делений на линейке (короткое, среднее, короткое, длинное…).
Её легко получить, если записать номер хода в двоичной системе.
| Ход | Двоичная запись | Число нулей в конце | Какой диск двигается |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 10 | 1 | 2 |
| 3 | 11 | 0 | 1 |
| 4 | 100 | 2 | 3 |
| 5 | 101 | 0 | 1 |
| 6 | 110 | 1 | 2 |
| 7 | 111 | 0 | 1 |
| 8 | 1000 | 3 | 4 |
На ходу m двигается диск с номером «число нулей в конце двоичной записи m, плюс 1». У нечётных ходов двоичная запись оканчивается на 1, поэтому всегда двигается диск 1. Именно поэтому в статье о том, как решать головоломку на ходах с нечётным номером двигают диск 1.
Кроме того, стержни, с которого и на который двигают, тоже можно найти одними двоичными вычислениями (статья об алгоритме).
Связь с кодом Грея
Когда двоичные числа считают подряд от 0, при каждом увеличении на 1 меняется разное число разрядов (от 0111 к 1000 меняются 4 разряда). Способ записи чисел, при котором на каждом шаге меняется только один разряд, называется «кодом Грея».
| Номер | Код Грея | Какой разряд меняется (справа) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
Последовательность меняющихся разрядов «1 2 1 3 1 2 1» точно такая же, как последовательность дисков, которые двигаются в Ханойской башне. Если считать каждый диск одним двоичным разрядом, а «разряд меняется» — «диск двигается», то кратчайшее решение Ханойской башни — то же самое, что последовательный проход по коду Грея.
В какую сторону вращается каждый диск
В статье о том, как решать головоломку говорилось, что диск 1 всегда вращается в одну сторону. На самом деле то же правило верно и для других дисков.
- Диски с нечётными номерами (1, 3, 5…) вращаются в ту же сторону, что и диск 1.
- Диски с чётными номерами (2, 4, 6…) вращаются в сторону, противоположную диску 1.
Когда башню переносят слева направо, при нечётном числе дисков диск 1 идёт по кругу «левый → правый → средний», а при чётном — «левый → средний → правый». Ни один диск до конца ни разу не меняет направление.
Есть и ещё одно правило, о котором рассказано в статье про 10 дисков: в кратчайшем решении диск с нечётным номером никогда не кладут прямо на нечётный, а с чётным — на чётный.
Всего 3ⁿ расположений
Сколько всего есть расположений дисков, не нарушающих правил? Каждый диск лежит на одном из трёх стержней, а порядок дисков на одном стержне определён (от большого к маленькому), поэтому расположений 3ⁿ.
| Число дисков | Расположений |
|---|---|
| 3 | 27 |
| 5 | 243 |
| 7 | 2187 |
| 9 | 19 683 |
Более того, из любого расположения в любое можно перейти, не нарушая правил. Известно и то, что если обозначить каждое расположение точкой и соединить линиями точки, между которыми можно перейти за один ход, получится фигура, очень похожая на «треугольник Серпинского», где в большой треугольник вложены маленькие.
В режиме «Задачи» приложения «Ханойская башня» задачи, где нужно привести расположение к форме образца, составляются из всех этих расположений. Даже для 9 дисков на ★5 перед выдачей задачи кратчайшее число ходов проверено для всех 19 683 расположений.
