Играй в классическую Ханойскую башню бесплатно в браузере. Перекладывай диски с одного стержня на другой. Без скачивания.
Три стержня, на одном из которых нанизаны диски в порядке убывания размера — самый большой снизу. Цель — перенести всю стопку на другой стержень. Правила: перемещать можно только верхний диск стопки, и нельзя класть больший диск на меньший. Минимальное количество ходов для n дисков равно 2^n − 1: для 3 дисков это 7 ходов, для 4 — 15, для 5 — 31.
Задача решается рекурсивно: чтобы переместить n дисков, сначала перенесите n−1 дисков на вспомогательный стержень, затем переместите самый большой диск на целевой, после чего перенесите n−1 дисков со вспомогательного на целевой. Для 3 дисков последовательность: 1→Ц, 2→В, 1→В, 3→Ц, 1→И, 2→Ц, 1→Ц. Понять рекурсию проще, решив сначала для 2 дисков, затем для 3 — закономерность становится очевидной.
Задача придумана французским математиком Эдуардом Люка в 1883 году. Сопроводительная легенда гласила: в индийском храме монахи перекладывают 64 золотых диска; когда они закончат — наступит конец света. При оптимальной игре это потребует 2^64 − 1 ≈ 18,4 квинтиллиона ходов. Даже при одном ходе в секунду понадобилось бы около 585 миллиардов лет. Задача широко используется в обучении рекурсии и алгоритмам разделения.
Игра позволяет задать стопку в диапазоне от 3 до 8 дисков, а счётчик ходов сравнивает ваш итог с оптимальным значением «2 в степени n минус 1». Трём дискам нужно всего 7 ходов, но каждый добавленный диск примерно удваивает минимум: 4 диска требуют 15, 5 дисков — 31, 6 дисков — 63, 7 дисков — 127, а 8 дисков — 255. Начните с 3 или 4, чтобы усвоить закономерность, где самый маленький диск всегда возвращается на тот же относительный стержень через ход. Как только число ваших ходов стабильно совпадёт с оптимальным, поднимите количество на единицу. Прыжок сразу к 8 дискам, прежде чем рекурсивный ритм станет автоматическим, обычно приводит к сотням впустую потраченных ходов и застрявшей, наполовину разобранной стопке.
Самая частая ошибка — двигать самый маленький диск в непоследовательном направлении. Для чистого решения верхний диск каждый цикл должен идти одинаково: при чётном числе дисков он движется по кругу трёх стержней в одну сторону, при нечётном — в другую. Игроки также буксуют, мысленно погребая самый маленький диск под более крупным и затем забывая, что он должен ходить первым. Ещё одна ловушка — слишком рано зацикливаться на стержне-цели; средний стержень — это необходимое временное хранилище, и отказ его использовать вынуждает к недопустимым размещениям. Поскольку игра блокирует любой ход, кладущий больший диск на меньший, недопустимый клик просто ничего не делает, так что впустую потраченные клики — сигнал, что вы боретесь со структурой, а не следуете чередующемуся ритму маленького диска.
Минимум равен «2 в степени числа дисков, минус один». Для стандартных 4 дисков это 15 ходов; для 8 дисков — 255. Счётчик показывает ваши ходы рядом с этим оптимальным ориентиром, так что вы видите точно, насколько эффективным было ваше решение.
Кликните по стержню с нужным диском, чтобы выбрать его, затем кликните по стержню-назначению. Перемещается только верхний диск выбранного стержня. Повторный клик по тому же стержню отменяет выбор. Нельзя класть диск на меньший.
Игра отклоняет любой ход, кладущий больший диск поверх меньшего, поэтому ничего не происходит. Она также отклоняет выбор пустого стержня. Если клик ничего не даёт, верхний диск назначения меньше того, что вы пытаетесь положить.
Да. Чередуйте два типа ходов: сначала двигайте самый маленький диск на шаг в фиксированном направлении, затем делайте единственный другой доступный допустимый ход. Повторяйте до решения. Эта простая двухшаговая петля даёт оптимальное решение при любом числе дисков без всякого планирования.
Нет. Правила одинаковы при любом числе дисков: по одному диску за раз, никогда больший диск на меньший, заново соберите всю стопку на крайнем правом стержне. С добавлением дисков растёт лишь минимальное число ходов и требуемое время.