要移动 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 步(第三个链接),约五千八百五十亿年,比宇宙年龄的四十倍还多——而摆在你面前的八个盘一分半钟就能移完。让小题变得无聊、大题变得地质年代的,是同一条翻倍规则: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
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。