Ханойская башня

Головоломка «Ханойская башня»: перенесите всю стопку дисков со стержня A на другой стержень по правилам. Решайте сами или смотрите автоматическое решение и список ходов, например на уроке о рекурсии.

Как пользоваться

1. Выберите количество в поле «Диски» — от 3 до 10.
2. Перетащите верхний диск на другой стержень или нажмите на стержень, чтобы взять верхний диск, и нажмите на другой стержень, чтобы положить его. Клавиши 1, 2 и 3 тоже работают.
3. Нажмите «Отменить», чтобы вернуть ход, или «Начать заново», чтобы начать сначала.
4. Если застряли, нажмите «Показать решение», чтобы посмотреть его с текущей позиции. Можно изменить «Скорость» или нажать «Пауза» и использовать «Один шаг».

Как это работает

• Правила: за раз переносится один диск, брать можно только верхний диск стержня, и нельзя класть больший диск на меньший.
• Минимальное число ходов для n дисков — 2ⁿ − 1. Чтобы перенести n дисков, нужно отложить n − 1 дисков в сторону, один раз переложить самый большой диск, а затем вернуть n − 1 дисков на него.
• Лучший результат для каждого количества дисков сохраняется в этом браузере. Игры, в которых использовалось автоматическое решение, не учитываются.

Частые вопросы

Какое минимальное число ходов в Ханойской башне?

Для n дисков — 2ⁿ − 1: 7 ходов для 3 дисков, 15 для 4, 31 для 5 и 1023 для 10.

Есть ли простой способ решить Ханойскую башню?

На каждом нечётном ходу переносите самый маленький диск на один стержень дальше, всегда в одном и том же направлении. На каждом чётном ходу делайте единственный допустимый ход, в котором не участвует самый маленький диск.

Почему Ханойскую башню используют для объяснения рекурсии?

Решение для n дисков состоит из двух решений для n − 1 дисков и одного хода самым большим диском, поэтому T(n) = 2·T(n − 1) + 1.

Можно ли увидеть все ходы сразу?

Откройте «Список ходов решения», чтобы увидеть все ходы в виде «Диск 1: A → C».