汉诺塔——移完 64 片圆盘要花 5800 亿年的递归谜题

大家好，我是 Senko。本文将解读谜题界的元老“汉诺塔”。

三根柱子，加上大小不一的圆盘。它只是把一摞圆盘挪到另一根柱子上的简单游戏，可这道谜题附带着“64 片黄金圆盘全部移完之时，世界就会终结”的传说。实际算一算，移完 64 片最少也要约 1845 亿亿步，就算一秒走一步，也要约 5800 亿年，是宇宙年龄的 40 倍以上。区区三根柱子里怎么会涌出天文数字，这背后藏着递归这套强大的想法，下面就来看看。

汉诺塔是什么

汉诺塔（英语 Tower of Hanoi），是能让你亲身体会仅凭两条简单规则，就会生出指数级膨胀的步骤的谜题。先把规则整理一下。

有三根柱子，左边那根上按从大到小叠着 n 片大小不同的圆盘
一次只能移动一片。而且只能动各柱最上面那一片
不能把大的圆盘放到比它小的圆盘上面
把全部圆盘按同样的大小顺序移到另一根柱子上就算完成

圆盘 2 片要 3 步，3 片要 7 步，是小孩也玩得动的难度。可每加一片，所需步数就以比翻倍还略多一点的节奏膨胀，10 片是 1023 步，20 片超过 104 万步，到 64 片就达到把宇宙寿命耗光的规模。这份急速增长的真身，后面揭晓。

1883 年，出自数学家卢卡斯的顽皮心

汉诺塔的出身很清楚。1883 年，法国数学家爱德华·卢卡斯把它当玩具发售。卢卡斯是以素数研究留名的正牌数学家，可这件玩具却是以“暹罗（泰国）的 N·克劳斯教授”这个虚构人物的构思推出的。N. Claus（克劳斯）是 Lucas（卢卡斯）的字母重排（易位词），连同东方风的神秘包装在内，这都是卢卡斯充满顽皮心的做局。

开头介绍的 64 片圆盘的传说，来历也在这里。“印度寺院里僧侣们一直在移动 64 片黄金圆盘，移完之日世界即崩塌”这个故事，是发售次年 1884 年由科普作家亨利·德·帕维尔介绍后传开的，一般认为它并非真实的传承，而是为促销而作的创作。与斑马谜题的爱因斯坦传说一样，谜题常被后加上有魅力的出身故事，不过汉诺塔这一则连编故事的水准都是一流。毕竟它有“完成要花 5800 亿年”的计算作背书，作为世界末日的装置堪称理想。

最少步数为何是“2 的 n 次方减 1”

这道谜题的核心，一句话就说尽了：“移动 n 片的作业，可分解成两次移动 n−1 片的作业，加上最大圆盘的一次移动”

要把最底下的最大圆盘挪到目标柱，就只能先把压在它上面的 n−1 片整个儿撤到空着的那根柱子上。挪完最大圆盘，再把撤走的 n−1 片放回它上面。也就是说，步骤必定是“n−1 片的搬家→最大的一步→n−1 片的搬家”这样的三段结构。

于是，n 片的最少步数就是“n−1 片最少步数的两倍再加一”。1 片是 1 步，依次算下去就是 3 步、7 步、15 步、31 步……一般地即2 的 n 次方减 1 步。每多一片作业量就近乎翻倍，所以 64 片时是 2 的 64 次方减 1，达到约 1845 亿亿步这个怪物般的数字。

把 3 片时的 7 步实际排出来，结构就看得很清楚。

① 最小移到目标柱　② 中等移到空柱　③ 最小移到中等之上（到此上面两片撤离完成） ④ 最大移到目标柱（全局的折返点。仅一步） ⑤ 最小移回原柱　⑥ 中等移到目标柱　⑦ 最小移到中等之上（把撤走的两片放回，完成）

前半三步与后半三步各自就是“两片版的步骤”，中间夹着最大的那一步。可以看出，分解的说明本身就是步骤表。

而且比这更少的步数绝对解不开，这一点也能从同一个分解证明出来。挪动最大圆盘的那一瞬间，其余全部必须已撤到另一根柱子上；而撤离与复归各自都完整需要 n−1 片版的最少步数。解法与极限的证明出自同一个分解，我觉得这就是这道谜题在数学上的美。

作为递归这套想法的入门书

“把问题归结为小一圈的同形问题”这套想法被称为递归，是计算机科学的脊梁之一。汉诺塔作为它最好的教材，一直出现在全世界的编程入门书里。

递归的好处，是不必一步一步去想整体的步骤。7 片的汉诺塔有 127 步，可要记住的只有“两次 6 片版，加最大的一步”这个分解。6 片版丢给 5 片版的分解，5 片版丢给 4 片版……如此甩锅下去，最后落到“1 片就是 1 步”这个自明的底。给数据排序用的快速排序、把文件夹里里外外遍历的处理、分形图形的绘制，实用算法里有很多都是这种“把大问题切成小的相似形”的型。

二进制的节奏与心理测验上的延展

从数学一侧看，还藏着意想不到的图案。把圆盘的移动从头排开就会发现，最小的圆盘每隔一步动一次，第二片每四步动一次，第三片每八步动一次，与二进制计数器进位的节奏完全一致。另外，把所有可能的摆法当成点、把一步之内能互达的摆法连成线，就会浮现出被称为谢尔宾斯基三角形的三角形层层嵌套的分形图案。由递归造出的谜题，其全局地图竟也是由递归造出的图形。听着像编的，可这是真的。

汉诺塔在别的领域也常露面。心理学里把它用作测量提前规划能力（执行功能）的检查课题，其改良版伦敦塔测验成了神经心理学的经典。另外备份的世代管理中，真实存在一种沿用圆盘移动模式的、被称为“汉诺塔方式”的轮换法。第一片每隔一步动、第二片每隔四步动这样的规律性，被挪用成了用较少的磁带均衡保留新旧备份的机制。19 世纪的玩具在现代的机房里干活，我觉得是件愉快的事。

不迷路的走法，以及四根柱子的世界

有没有不迷路走出最短步骤的诀窍

要记的规则只有两条：第一，每隔一步动一次最小的圆盘；第二，最小圆盘每次都朝同一个方向巡回（片数为奇数时朝目标柱的方向，为偶数时反向转）。轮到不动最小圆盘的那一步，其实能走的只有一种，所以不会迷。只要守住这两条，就会自动描出最短步骤。由递归设计出的步骤，竟化成如此简单的反复规则，这一事实也是这道谜题隐藏的看点。

柱子变成四根会怎样

步数会剧减。比如 8 片时，三柱需要 255 步，而四柱只要 33 步。撤离场所只多一根，指数爆炸就大幅缓和。四柱的最优解长期以来被认为“大概是” 1941 年提出的分割法（弗雷姆–斯图尔特方法），可被严格证明为最优，则是到了 2014 年的事。也就是说，一件儿童玩具的彻底解明，让现代数学花了 130 年。

64 片传说的“5800 亿年”是怎么算的

2 的 64 次方减 1 是 18,446,744,073,709,551,615，约 1845 亿亿步。按一秒一步除下来约 5849 亿年，是宇宙年龄（约 138 亿年）的 40 倍以上。顺带一提，这个 2 的 64 次方减 1，与“在棋盘的 64 格上按倍数放米粒”这个著名小故事里的米粒总数是同一个数。要传达 64 次翻倍有多可怕，汉诺塔与棋盘上的米可谓双璧。