金盘梵塔

📖 梵塔传说 · 汉诺塔的历史

贝拿勒斯的神庙传说。相传大梵天创造世界时，在神庙里立了三根金刚石柱，第一根柱子上从下往上、由大到小摞着 64 片黄金圆盘。僧侣们日夜不息地移盘：一次只能移动一片，小盘上不能放大盘，把整塔搬到另一根柱子上。传说当 64 片金盘全部移完之时，世界将在一声霹雳中化为尘埃。

「当 64 片金盘归位，梵塔、庙宇和众生，都将同归于尽。」——传说无从考证，但算法可以算出「末日」的时刻。

末日还有多久？按最优走法，移完 n 个盘需要 2ⁿ−1 步。64 个盘就是 2⁶⁴−1 ≈ 1.84×10¹⁹ 步——就算僧侣一秒移一片、片刻不停，也要 5800 多亿年才能移完，是宇宙现今年龄（约 138 亿年）的 40 多倍。世界末日？排在宇宙热寂后面很远很远。

1883 年，玩具登场。法国数学家爱德华·卢卡斯（Édouard Lucas）发明了这款玩具，并配上了上面那个印度传说——「汉诺塔」（Tower of Hanoi）之名由此传开。他把难题装进木头玩具里卖到世界各地，也让「递归」第一次成为千家万户手里的游戏。今天的算法教材几乎无一例外地从它讲起：数据结构的递归、算法设计的分治，都拿它当第一课。

一百多年的接力。三柱汉诺塔在卢卡斯手里已有完美解答；但只多加一根柱子，问题陡然变难——四柱汉诺塔的最优解 1941 年由 Frame 与 Stewart 给出算法猜想，此后数学家们接力了七十多年，直到 2014 年才被严格证明其最优性。一座小小的塔，牵动了三个世纪的数学（详见下一页「算法故事」）。

🧭 算法故事 · 从 2ⁿ−1 到 Frame–Stewart

故事一：拆到底的智慧。要把 n 个盘从甲搬到丙（三柱），想最大的一盘：它必须独自搬到丙——所以先把上面 n−1 盘让到乙柱，再搬最大盘，最后把 n−1 盘从乙让到丙。设 f(n) 为最少步数，就有递推式：

f(n) = 2·f(n−1) + 1，f(1) = 1  ⇒  f(n) = 2ⁿ−1

两边同除以 2ⁿ（或构造相邻差），正好落回课本里的等比数列：f(n)+1 = 2·(f(n−1)+1)，是首项为 2、公比为 2 的等比数列。一盘玩具，把「递归」与「数列」串成了一条线。

故事二：多一根柱子的化归。四柱汉诺塔只多一根柱，难了整整一个量级。1941 年，Frame 与 Stewart 先后提出同一套算法，如今叫 Frame–Stewart 算法，核心是一步漂亮的化归——把四柱问题拆回三柱：

① 挑上面 t 个盘，用四根柱挪到缓冲柱（四柱递归）；
② 把底下 n−t 个盘用三根柱搬到目标柱（经典递归）；
③ 再把 t 个盘用四根柱挪回目标柱。
总步数 = 2·FS(t) + (2^n−t−1)，对 t = 1…n−1 挨个试，取最小。

试出最合算的「切法」t，是整套算法里最妙的一步：它不硬算，而是让算法自己挑最快的分法。对比上表可见四柱的省力：8 个盘从 255 步直落到 33 步。

故事三：73 年的悬案。算法好使，可它真的最优吗？这一问悬了七十多年：1994 年 Stockmeyer 给出四柱步数的通项公式；2003–2004 年，中国学者杨锴、刘铎等先后给出证明思路；直到 2014 年法国数学家 Bousch 才严格证明 Frame–Stewart 算法就是四柱汉诺塔的最优解——从猜想立案到结案，整整 73 年。更多柱子（五柱、六柱……）的最优解至今仍是在递归近似中摸索的开放问题。

更多的柱子，更深的迷宫。下表摘录广义汉诺塔的最少步数（盘数 1–10）：柱子越多，同一盘数所需步数越少；但每加一根柱，最优策略的证明都更难一层。

主要参考：J. S. Frame, Amer. Math. Monthly, 1941；P. K. Stockmeyer, Congressus Numerantium, 1994；T. Bousch, La quatrième tour de Hanoï, 2014；薛兴元《汉诺塔问题及其推广》（本工坊算法演示与表格的核对依据）。