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

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

Поле в верхней части страницы — это бесплатная игра «Ханойская башня», которая работает прямо в браузере: ничего не нужно скачивать и не нужно заводить аккаунт. Выберите от 3 до 15 дисков и перенесите всю стопку с левой башни на правую.

• Телефон или планшет: коснитесь башни, чтобы поднять верхний диск, затем коснитесь другой, чтобы положить его.
• Мышь: перетащите диск или щёлкните сначала по одной башне, потом по другой.
• Клавиатура: ← и → выбирают башню, ↑ поднимает диск, ↓ кладёт; 1, 2 и 3 сразу переходят к башням A, B и C, а Esc возвращает диск на место.

Ошибки ничего не стоят. Отменить возвращает последний ход, Сбросить начинает ту же игру заново, а Подсказка поднимает диск, который следующим переложило бы кратчайшее решение, и говорит, куда его нести. Ход делает его за вас. А если хочется просто посмотреть, Решить автоматически доиграет головоломку с того места, где сейчас стоит поле, а не только с начала.

Пока вы не сделали ход, ничего не считается. После первого хода панель показывает:

• число ходов, таймер и показатель эффективности — вашу партию в процентах от идеальной;
• идёте ли вы по-прежнему оптимальным путём или на сколько ходов от него отстали.

Лента времени под полем записывает всю партию. Вернитесь к любой прежней позиции или воспроизведите игру со скоростью 0,5×, 1×, 2× или 4×; та же скорость задаёт темп автоматического решения. Режим концентрации убирает всё, кроме башен, а страница запоминает, со сколькими дисками вы играли в прошлый раз. Когда вы закончите, экран результата сравнит ваши ходы с минимумом и предложит добавить ещё один диск.

Задача о Ханойской башне

Задача начинается с трёх башен и стопки дисков разного размера на одной из них, самый большой — внизу. Цель — перенести всю стопку на другую башню, соблюдая три правила:

1. За один ход переносится только один диск.
2. Двигать можно только верхний диск башни.
3. Больший диск никогда нельзя класть на меньший.

Вот и вся головоломка, освоить её можно примерно за минуту. Трудной её делает третье правило: каждому диску нужно ждать на каком-то допустимом месте, пока перекладываются диски под ним, а при трёх башнях места всегда мало. На странице «Как играть в Ханойскую башню» правила показаны в картинках, есть тренировочное поле и разобранный пример.

Французский математик Эдуард Люка опубликовал головоломку в 1883 году. Через год журнальная статья о ней добавила легенду, благодаря которой она и прославилась: брахманы перекладывают шестьдесят четыре золотых диска, и когда они закончат, наступит конец света. При одном ходе в секунду на это ушло бы около 585 миллиардов лет.

Минимальное число ходов и формула 2ⁿ − 1

Минимальное число ходов в Ханойской башне из n дисков равно 2ⁿ − 1; часто это записывают как 2^n − 1. Для трёх дисков нужно 7 ходов, для четырёх — 15, а Ханойская башня из 5 дисков требует ходов не меньше чем 31. Это доказанная нижняя граница, а не рекорд: ни для одного размера более короткого решения не существует, и именно с этим числом сравнивает вас показатель эффективности на поле.

Уравнение, стоящее за формулой

Уравнение следует прямо из правил. Прежде чем самый большой диск сможет сдвинуться, n − 1 дисков над ним должны оказаться сложенными на свободной башне; затем он переходит; затем эти диски возвращаются на него сверху. Если обозначить через T(n) наименьшее число ходов, за которое это можно сделать, то

T(n) = 2·T(n − 1) + 1, начиная с T(0) = 0: нет дисков — нет ходов.

Каждый размер стоит вдвое больше предыдущего плюс один: 1, 3, 7, 15, 31, 63. Каждое из этих чисел на единицу меньше степени двойки — отсюда и замкнутая формула T(n) = 2ⁿ − 1. В доказательстве того, что 2ⁿ − 1 — это минимум, разобраны обе половины утверждения: почему этого числа ходов всегда достаточно и почему меньше невозможно, а калькулятор минимального числа ходов даёт точное значение для любого числа дисков вплоть до шестидесяти четырёх.

Минимальное число ходов по количеству дисков

Каждый размер ведёт к полному решению, где все ходы перечислены и сыграны на поле. Самая большая партия здесь — 15 дисков, то есть 32 767 ходов: каждый добавленный диск удваивает длину партии и прибавляет ещё один ход.

Алгоритм Ханойской башни и рекурсия

Уравнение выше — это и есть алгоритм, если прочитать его как инструкцию. Чтобы перенести n дисков с исходной башни на целевую:

1. Перенесите n − 1 дисков с исходной башни на свободную.
2. Перенесите самый большой диск с исходной башни на целевую.
3. Перенесите n − 1 дисков со свободной башни на целевую.

Шаги 1 и 3 — та же задача, только на один диск меньше, поэтому алгоритм решает их, вызывая сам себя, а вызов без дисков просто возвращается. Это и есть вся рекурсия Ханойской башни, и именно поэтому почти каждый курс программирования использует эту головоломку, чтобы объяснить рекурсию. Секрет в том, чтобы не пытаться представить все ходы сразу: доверьтесь меньшему вызову — он сделает свою часть, — и три шага окажутся всем решением.

Поскольку алгоритм делает ровно 2ⁿ − 1 ходов, время его работы — O(2ⁿ), и быстрее нельзя: каждый из этих ходов должен быть сделан. Памяти же он расходует всего O(n). Страница алгоритма Ханойской башни выполняет код построчно рядом с живым полем и по ходу рисует дерево вызовов, а итеративное решение получает те же ходы с помощью двух правил и одного цикла.

Ханойская башня на Python, Java и других языках

Три шага почти дословно превращаются в код. Ханойская башня на Python — это функция из семи строк: базовый случай для нуля дисков, два рекурсивных вызова и одна строка между ними, печатающая ход. Ханойская башня на Java — тот же метод внутри класса и место, где можно узнать, почему число ходов для шестидесяти четырёх дисков не помещается в long. Есть и полные программы на C, C++, C# и JavaScript.

Каждая программа была запущена, а её вывод сверен с решателем этого сайта, и к каждой прилагается разбор, объясняющий, зачем нужна каждая строка, а не что делает синтаксис.

Другие способы играть и учиться

Когда три башни и полная стопка станут простыми, есть что попробовать дальше:

• Задача дня — одна перемешанная позиция, общая для всех, новая каждую полночь по UTC. Решите её без решателя, чтобы продлить серию.
• Решатель — все ходы кратчайшего решения из любой допустимой позиции, в том числе из той, где вы застряли на этом поле.
• Стратегии — единственная идея, повторяющаяся за каждым размером, и правило, которое подсказывает следующий ход без планирования.
• Варианты — четыре башни вместо трёх, кольцо, по которому диски ходят только в одну сторону, два цвета для сортировки и случайная начальная позиция.
• Для учителей — план урока на 45 минут, рабочий лист для печати с ответами и поле, которое можно встроить в страницу курса.

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

Что такое Ханойская башня?

Ханойская башня — это головоломка из трёх башен и стопки дисков разного размера. Нужно перенести всю стопку с одной башни на другую, по одному диску за ход, и больший диск никогда не должен лежать на меньшем. Её опубликовал французский математик Эдуард Люка в 1883 году.

Можно ли играть в Ханойскую башню онлайн бесплатно?

Да. Поле на этой странице бесплатное, работает в любом современном браузере на телефоне, планшете или компьютере и не требует ни загрузки, ни аккаунта. Число дисков из последней партии и ваши рекорды хранятся в вашем собственном браузере, а не на сервере.

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

Идеальная партия из n дисков занимает 2ⁿ − 1 ходов. Для трёх дисков нужно 7, для пяти — 31, для 15 дисков — 32 767. Более короткого решения не существует, так что это число — жёсткая нижняя граница, а не просто цель.

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

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

Есть ли способ сразу знать следующий ход?

Есть. На каждом нечётном ходу перекладывайте самый маленький диск на одну башню в постоянном направлении: влево, если дисков нечётное число, вправо, если чётное, перескакивая с края на другой край, — поэтому при трёх дисках его самый первый ход идёт с A на C. На каждом чётном ходу делайте единственный допустимый ход, не затрагивающий самый маленький диск. Чередуя эти два правила, вы сыграете идеальную партию, ничего не планируя.

Со сколькими дисками здесь можно играть?

От 3 до 15. Начните с 3, чтобы понять форму решения, а потом добавляйте по одному диску: каждый новый диск примерно удваивает работу.

Можно ли отменить ход или пересмотреть партию?

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