Восьми дискам нужно 255 ходов; шестидесяти четырём из легенды — 2⁶⁴ − 1

Каждый следующий диск удваивает работу и прибавляет один — поэтому у ханойских башен кончается время.

Статистика и данные · Уровень: Классический результат · Обновлено 2026-11-10

Чтобы переместить n дисков, надо сначала убрать верхние n − 1, затем один раз переместить самый большой диск, а после снова положить те n − 1 сверху. Значит, M(n) = 2M(n − 1) + 1 при M(1) = 1, и это решается в 2ⁿ − 1: восьми дискам нужно 255 ходов, а трём — 7, в первых двух ссылках. 255 знакомо каждому, кто читает размеры памяти: это наибольшее значение, которое вмещает беззнаковый байт, и ровно по этой причине.

Версия Лукаса пришла с шестьюдесятью четырьмя золотыми дисками и пророчеством, что мир кончится, когда стопка будет переложена. При одном ходе в секунду это 2⁶⁴ − 1 = 1.844674407371⋅10+19 ходов (третья ссылка), примерно 585 миллиардов лет, больше чем в сорок раз возраста мира, — а головоломка с восемью дисками перед вами занимает полторы минуты. То же удвоение, которое делает малый случай тривиальным, делает большой геологическим, и в этом весь смысл экспоненты: 255 и 1.844674407371⋅10+19 — одно и то же правило, разнесённое на шестьдесят шагов.

Ответ

255

Как его читать

2⁸ − 1 в поле вычислений. Вторая ссылка — три диска; третья — подсчёт шестидесяти четырёх дисков, которые заканчивают мир.

Источник

Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1

Пересчитать в калькуляторе

Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.

Это независимый сторонний информационный сайт. Он не связан с Casio, Texas Instruments или их дистрибьюторами, не спонсируется ими и не имеет их авторизации. Названия моделей и продуктов — товарные знаки соответствующих правообладателей; они приведены здесь только для идентификации устройств.

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