Калькулятор «Ханойской башни»

Сколько это на самом деле

Числа выше точны и сами по себе почти ничему не учат: после нескольких миллиардов одно очень большое число похоже на другое. Что делает эта арифметика, легче увидеть, чем рассказать. Каждый лишний диск удваивает работу, поэтому линейка с равномерно расставленными дисками — это линейка с умножающимися промежутками времени, и весь путь от перерыва на кофе (десять дисков, семнадцать минут) до возраста Вселенной (пятьдесят девять дисков) оказывается длиной примерно в пятьдесят шагов.

• 1 диск — 1 ход — 1 секунда: первый размер, который доходит до секунды.
• 6 дисков — 63 хода — 1 минута: первый размер, который доходит до минуты.
• 12 дисков — 4 095 ходов — 1 час: первый размер, который доходит до часа.
• 17 дисков — 131 071 ход — 1 день: первый размер, который доходит до суток.
• 25 дисков — 33 554 431 ход — 1 год: первый размер, который доходит до года.
• 32 диска — 4 294 967 295 ходов — 136 лет: первый размер, который доходит до человеческой жизни.
• 38 дисков — 274 877 906 943 хода — 8,71 тысячи лет: первый размер, который доходит до всей записанной истории.
• 59 дисков — 576 460 752 303 423 487 ходов — 18,3 миллиарда лет: первый размер, который доходит до возраста Вселенной.

Затенённая полоса слева — это всё, во что здесь действительно можно сыграть. Одиннадцать дисков — долгая партия; двадцать пять — год непрерывных ходов; пятьдесят девять переваливают за возраст Вселенной. Правила вдоль этой оси не меняются нигде — меняется только число.

Формула

Идеальная партия из n дисков занимает ровно 2ⁿ − 1 ходов — это и есть формула «Ханойской башни», которую там, где нет надстрочных знаков, пишут как 2^n − 1. Это не лучший чей-то результат, а доказанный предел снизу. Чтобы самый большой диск вообще смог сдвинуться, все меньшие должны быть убраны с дороги на вспомогательную башню, а как только он перешёл, все они должны вернуться на него сверху. Два полных переноса n − 1 дисков плюс один ход:

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

1. 1Перенесите n−1 дисков над ним на вспомогательную башню. Пока они не убраны, ничего другого сделать нельзя.

2. 2Самый большой диск теперь свободен, а его целевая башня пуста. Он переходит за один ход — единственный, который нужен на этом этапе.

3. 3Соберите на нём заново стопку из n−1 дисков. Это та же задача с одним диском меньше — и так до одного диска, который перемещается за один ход.

Разворачивая, получаем 1, 3, 7, 15, 31, 63 — каждое вдвое больше предыдущего плюс один, то есть последовательность чисел, на единицу меньших степени двойки. Каждый добавленный диск чуть более чем удваивает работу, и поэтому головоломка меньше чем за пятьдесят шагов проходит путь от перерыва на кофе до срока, превышающего возраст Вселенной.

Та же рекуррента объясняет, почему головоломка так знаменита в курсах информатики. Раз работа удваивается с каждым диском, рекурсивное решение работает за O(2ⁿ) — и за этим не прячется никакой более хитрый алгоритм: само число ходов экспоненциально, и каждый ход нужно выдать. Чего оно не стоит, так это памяти: рекурсия спускается по одному диску, поэтому держит O(n) кадров стека — по одному на диск плюс один для базового случая: шестнадцать для самого большого поля здесь и шестьдесят пять для легенды. Полный вывод и объяснение, почему к этой рекурренте неприменима основная теорема о рекуррентных соотношениях, — на странице алгоритма «Ханойской башни».

Минимум ходов по числу дисков

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

За пределами поля

После 15 дисков головоломка перестаёт быть тем, во что играют, и становится тем, что считают. Числа по-прежнему точны — просто до них уже не дожить.

У этих чисел есть имя

Число, на единицу меньшее степени двойки, называется числом Мерсенна и записывается M_n = 2ⁿ − 1 — значит, каждое число в таблицах выше именно такое, и число ходов партии «Ханойской башни» никогда не бывает другим. Когда число Мерсенна оказывается простым, это простое число Мерсенна, и именно на таких числах десятилетиями идёт охота за рекордно большими простыми: проверить 2ⁿ − 1 на простоту куда дешевле, чем произвольное число такого же размера.

M_n может быть простым, только когда простое и само n, но одного этого мало — и контрпример можно сыграть прямо здесь. Одиннадцать простое, а его 2 047 ходов — нет, ведь 2 047 = 23 × 89. Из размеров этого поля простое число ходов дают 3, 5, 7 и 13 дисков. OEIS A000225 — вся последовательность целиком.

Легенда о шестидесяти четырёх дисках

Головоломка поступила в продажу в 1883 году, и меньше чем через год у неё появилась история: в храме в Бенаресе жрецы перекладывают шестьдесят четыре золотых диска между тремя алмазными иглами, и когда последний диск ляжет на место, миру придёт конец. Арифметика успокаивает. Шестидесяти четырём дискам нужно 18 446 744 073 709 551 615 ходов, а при одном ходе в секунду это 585 миллиардов лет — примерно в сорок раз больше нынешнего возраста Вселенной.

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

Сколько ходов занимает «Ханойская башня»?

Минимум — 2ⁿ − 1 ходов для n дисков. Трём дискам нужно 7, пяти — 31, десяти — 1 023, двадцати — 1 048 575. Каждый лишний диск чуть более чем удваивает итог, потому что решить n дисков — это дважды решить n − 1 дисков и сделать один ход между.

Почему формула именно 2ⁿ − 1?

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

Какова временная сложность «Ханойской башни»?

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

Сколько заняли бы 64 диска?

Шестидесяти четырём дискам нужно 18 446 744 073 709 551 615 ходов. При одном ходе в секунду это 585 миллиардов лет — намного больше нынешнего возраста Вселенной, в чём и состоит смысл легенды, добавленной к головоломке в 1884 году.

Может ли решение быть короче, чем 2ⁿ − 1?

Нет. 2ⁿ − 1 — доказанная нижняя граница, а не просто лучший известный результат: самый большой диск обязан сдвинуться хотя бы раз, а до этого все меньшие диски должны быть и не на нём, и не на его целевой башне. Это вынуждает два частичных переноса, и рассуждение повторяется до самого низа.

Работает ли калькулятор для наполовину решённого поля?

На этой странице — нет: 2ⁿ − 1 предполагает, что все диски начинают на одной башне. Для кратчайшего решения из позиции, где часть пути уже пройдена, возьмите решатель: он считает оптимальный путь из любой допустимой расстановки. Открыть решатель →