Чтобы переместить 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
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.