Чтобы решать Ханойскую башню, нужно запомнить всего два правила. Если чередовать их, то при любом числе дисков башню можно перенести за наименьшее число ходов. В статье мы объясняем случай, когда башню переносят с левого стержня на правый (правила игры описаны в статье Что такое Ханойская башня?). Диски называем по номерам от самого маленького: 1, 2, 3…
Решение — повторение двух правил
- Ход с нечётным номером (1-й, 3-й, 5-й…): самый маленький диск (1) переносят на следующий стержень в заданном направлении.
- Ход с чётным номером (2-й, 4-й, 6-й…): делают ход, в котором участвует не диск 1. Такой ход всегда только один.
Вот и всё. Диск 1 двигается через ход, а в промежутках по одному разу двигаются остальные диски.
Как выбрать направление движения маленького диска
Направление диска 1 зависит от числа дисков. Представьте три стержня как кольцо: дойдя до края, переходим на противоположный. Когда башню переносят слева направо, порядок такой.
| Число дисков | Порядок движения диска 1 |
|---|---|
| нечётное (3, 5, 7…) | левый → правый → средний → левый… |
| чётное (4, 6, 8…) | левый → средний → правый → левый… |
Запомнить можно так: «если дисков нечётное число, первым ходом диск 1 сразу кладут на тот стержень, куда переносят башню». При чётном числе первым ходом его кладут не на тот стержень, куда переносят башню, а на средний. Выбрав направление, до конца его не меняют.
Если нужно перенести башню на средний стержень, читайте в таблице «правый» и «средний» наоборот.
Проверим на 3 дисках
Дисков 3 (нечётное число), поэтому диск 1 ходит по кругу «левый → правый → средний → левый». Золотым цветом отмечен диск, который двигали в этом ходу.
- Начало
- Ход 1 Диск 1 — вправо
- Ход 2 Диск 2 — в центр
- Ход 3 Диск 1 — в центр
- Ход 4 Диск 3 — вправо
- Ход 5 Диск 1 — влево
- Ход 6 Диск 2 — вправо
- Ход 7 Диск 1 — вправо
Видно, что на 1-м, 3-м, 5-м и 7-м ходах просто идёт диск 1, а 2-й, 4-й и 6-й ходы — это «единственный возможный ход без диска 1».
Почему ход с чётным номером определяется однозначно
На ходу с чётным номером сравнивают верхние диски двух стержней, на которых нет диска 1. Меньший диск остаётся только положить на больший (или на пустой стержень).
- На диск 1 нельзя положить никакой диск (дисков меньше 1 нет).
- Из двух оставшихся стержней большой диск нельзя положить на маленький.
Поэтому возможный ход всегда только один. Приходится выбирать лишь направление диска 1 на нечётных ходах, и если решить это в самом начале, дальше ходы идут сами собой.
Идея «убрать верхние диски и перенести большой»
Помимо запоминания порядка, можно понять, почему он работает. Чтобы перенести башню из n дисков слева направо, нужно разделить задачу на три части:
- Убрать верхние n − 1 дисков на средний стержень.
- Перенести самый большой диск вправо.
- Перенести n − 1 дисков со среднего стержня вправо.
Части 1 и 3 — это задача «перенести башню на один диск меньше», поэтому ту же идею можно применить ещё раз. Для 4 дисков: «убрать 3 диска → перенести диск 4 → вернуть 3 диска», а чтобы убрать 3 диска: «убрать 2 диска → перенести диск 3 → вернуть 2 диска» — и так далее, задача делится на всё более маленькие. Из этой идеи видно и то, что ходов будет 2ⁿ − 1 (статья о формуле минимального числа ходов).
Как восстановить порядок, если запутались
Если вы забыли порядок и диски оказались разбросаны, ничего страшного. Вот как можно навести порядок из любого положения.
- Найдите среди дисков, которые ещё не лежат на правом стержне как надо, самый большой. Это и есть следующий диск, который нужно перенести.
- Чтобы перенести его вправо, все диски меньше него нужно собрать на оставшемся стержне, который не является ни текущим, ни правым.
- Сбор маленьких дисков — повторение той же идеи. Считайте стержень, куда собираете, «целевым» и начните сначала.
Секрет в том, чтобы решать, куда идти, начиная с больших дисков. Режим «Задачи» в приложении (где разбросанные диски нужно привести к форме образца) тоже решается по этой идее.
Советы
- Считайте ходы: на нечётных ходах всегда двигают диск 1, поэтому, зная номер хода, вы не будете гадать, какой диск двигать.
- Чем больше диск, тем реже он двигается: диск 1 двигается примерно на половине ходов, а самый большой диск — только один раз. Если вы много раз двигаете большой диск, вы идёте в обход.
- Сначала берите 3 или 4 диска: пока два правила не войдут в привычку, лучше несколько раз повторить с малым числом дисков. Освоившись, переходите к 5 и 7 дискам.
Ходы для каждого числа дисков
Порядок ходов для разного числа дисков и опорные формы по дороге собраны в этих статьях.
- Ответы к Ханойской башне (3–10 дисков)
- 4 диска (15 ходов на схемах)
- 5 дисков (31 ход)
- 7 дисков (127 ходов)
- 10 дисков (1023 хода)
Попробуйте на практике
Попробуйте два правила на доске ниже. Нажмите на стержень, чтобы поднять самый верхний диск, и на другой стержень, чтобы положить его туда. Сначала дисков 4 (чётное число), поэтому первым ходом диск 1 нужно перенести на средний стержень.
