inthink.guide
МагазинНа главную

Играйте. Предсказывайте. Понимайте.

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

Играйте с 3–5 дисками, получайте подсказки для своей позиции и изучайте рекурсивную стратегию в двух коротких анимациях. Пошаговый пример можно открыть в любой момент.

Играть в Ханойскую башню
ABCДиск 44Диск 33Диск 22Диск 11

Уберите маленькую стопку, чтобы освободить самый большой диск.

Правила Ханойской башни

  1. Перенесите всю стопку со стержня A на C.
  2. За ход перемещайте только один диск, всегда верхний.
  3. Нельзя класть большой диск на меньший.

Играть в Ханойскую башню

Выберите исходный стержень, затем целевой. Числа обозначают размер: 1 — самый маленький. Отмените ход или начните заново, чтобы попробовать другой подход.

Ходов: 0
ABCДиск 33Диск 22Диск 11

Выберите исходный стержень, затем целевой.

Подсказки учитывают вашу позицию и не двигают диски за вас. Допустимый обход тоже можно завершить.

Как решить Ханойскую башню

Начните с самого большого диска. В примере из четырёх дисков три маленьких мешают ему. Решите меньшую задачу перед перемещением диска 4.

  1. Уберите маленькую стопку

    Перенесите диски 1, 2 и 3 с A на B, используя C как вспомогательный стержень. Диск 4 остаётся на A. Теперь C свободен, а диск 4 доступен.

    ABCДиск 44Диск 33Диск 22Диск 11

  2. Переместите самый большой диск

    Перенесите диск 4 с A на C. Этот ход ставит его на окончательное место.

    ABCДиск 44Диск 33Диск 22Диск 11

  3. Перенесите маленькую стопку к цели

    Перенесите диски 1, 2 и 3 с B на C, используя A. Они помещаются на диск 4, и задача решена.

    ABCДиск 44Диск 33Диск 22Диск 11

Каждая меньшая стопка следует тому же плану: убрать диски над самым большим, переместить его и вернуть маленькую стопку сверху. Если остался один диск, перенесите его прямо. Это рекурсия: роли исходного, целевого и вспомогательного стержней меняются в каждой подзадаче.

Учитесь, предсказывая следующую цель

Отдельные примеры с четырьмя дисками не меняют вашу игру. Остановитесь, смотрите по одному ходу, ответьте на вопрос или откройте объяснение.

1. Освободите путь большому диску

Посмотрите, как три маленьких диска освобождают диск 4. Предскажите, где они должны быть перед его переносом.

Отдельный пример с четырьмя дисками

Цель: перенести 3 дисков с A на B, используя C.

ABCДиск 44Диск 33Диск 22Диск 11

Сначала освободите путь: перенесите три верхних диска с A на B.

Шаг 0 из 8

2. Повторите меньшую задачу

Диск 4 уже на C. Остаётся та же задача с тремя дисками и другими ролями стержней.

Отдельный пример с четырьмя дисками

Цель: перенести 3 дисков с B на C, используя A.

ABCДиск 44Диск 33Диск 22Диск 11

Диск 4 остаётся на C. Теперь решите задачу трёх дисков с B на C.

Куда сначала идёт диск 1 при переносе трёх дисков с B на C с помощью A?

Шаг 0 из 7

Пошаговые решения

Примеры начинаются со всех дисков на A и заканчиваются на C. Открывайте их сразу: ваша позиция не изменится.

Минимальное число ходов

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

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

3 диска: 7 ходов. 4 диска: 15 ходов. 5 дисков: 31 ход.

Диски: 3 — ходы: 7

Начало: все диски на A. Цель: C. Диск 1 — самый маленький.

  1. Перенесите диск 1 с A на C.
  2. Перенесите диск 2 с A на B.
  3. Перенесите диск 1 с C на B.
  4. Перенесите диск 3 с A на C.
  5. Перенесите диск 1 с B на A.
  6. Перенесите диск 2 с B на C.
  7. Перенесите диск 1 с A на C.
Диски: 4 — ходы: 15

Начало: все диски на A. Цель: C. Диск 1 — самый маленький.

  1. Перенесите диск 1 с A на B.
  2. Перенесите диск 2 с A на C.
  3. Перенесите диск 1 с B на C.
  4. Перенесите диск 3 с A на B.
  5. Перенесите диск 1 с C на A.
  6. Перенесите диск 2 с C на B.
  7. Перенесите диск 1 с A на B.
  8. Перенесите диск 4 с A на C.
  9. Перенесите диск 1 с B на C.
  10. Перенесите диск 2 с B на A.
  11. Перенесите диск 1 с C на A.
  12. Перенесите диск 3 с B на C.
  13. Перенесите диск 1 с A на B.
  14. Перенесите диск 2 с A на C.
  15. Перенесите диск 1 с B на C.
Диски: 5 — ходы: 31

Начало: все диски на A. Цель: C. Диск 1 — самый маленький.

  1. Перенесите диск 1 с A на C.
  2. Перенесите диск 2 с A на B.
  3. Перенесите диск 1 с C на B.
  4. Перенесите диск 3 с A на C.
  5. Перенесите диск 1 с B на A.
  6. Перенесите диск 2 с B на C.
  7. Перенесите диск 1 с A на C.
  8. Перенесите диск 4 с A на B.
  9. Перенесите диск 1 с C на B.
  10. Перенесите диск 2 с C на A.
  11. Перенесите диск 1 с B на A.
  12. Перенесите диск 3 с C на B.
  13. Перенесите диск 1 с A на C.
  14. Перенесите диск 2 с A на B.
  15. Перенесите диск 1 с C на B.
  16. Перенесите диск 5 с A на C.
  17. Перенесите диск 1 с B на A.
  18. Перенесите диск 2 с B на C.
  19. Перенесите диск 1 с A на C.
  20. Перенесите диск 3 с B на A.
  21. Перенесите диск 1 с C на B.
  22. Перенесите диск 2 с C на A.
  23. Перенесите диск 1 с B на A.
  24. Перенесите диск 4 с B на C.
  25. Перенесите диск 1 с A на C.
  26. Перенесите диск 2 с A на B.
  27. Перенесите диск 1 с C на B.
  28. Перенесите диск 3 с A на C.
  29. Перенесите диск 1 с B на A.
  30. Перенесите диск 2 с B на C.
  31. Перенесите диск 1 с A на C.

Что делать, если моя позиция отличается?

Любая позиция с правильным порядком размеров может достичь C. Повтор позиции — петля, а не тупик. Формула относится к стандартному началу, а не к оставшимся ходам из произвольной позиции. Запросите подсказку для своей доски.

Головоломки →