企业官网建设流程全解析

对应《具体数学：计算机科学基础（第 2 版）》第 1 章 §1.1“河内塔”，书内第 1—4 页。本文沿用专栏的三级编号；“河内塔”和通常所说的“汉诺塔”指同一个问题。

汉诺塔的答案很容易记：n nn个圆盘至少需要移动2 n − 1 2^n-12n−1次。读这一节时，更值得弄清楚的是：递归式从哪里来，以及为什么我们得到的是“最少次数”。

1. 先把问题说清楚

有三根柱子A , B , C A,B,CA,B,C，n nn个大小不同的圆盘起初都放在A AA上，从上到下越来越大。目标是将整座塔搬到C CC，可以借助B BB，但要遵守两个限制：

• 每次只能移动一根柱子最上面的一个圆盘。
• 大圆盘不能放在小圆盘上。

定义T n T_nTn​为完成任务的最少移动次数。这里的“最少”很重要：某一种算法用了多少步，与所有合法方案至少要用多少步，是两个需要分别回答的问题。

先看小规模：

把n = 0 n=0n=0纳入定义并不多余。没有圆盘就不需要移动，T 0 = 0 T_0=0T0​=0正好给递归提供统一的终点。

2. 盯住最大的圆盘，得到一个可行方案

要把最大的圆盘从A AA搬到C CC，先得把上面的n − 1 n-1n−1个小圆盘挪开。因此可以分三步：

1. 将n − 1 n-1n−1个小圆盘从A AA搬到B BB，借助C CC，需要T n − 1 T_{n-1}Tn−1​次。
2. 将最大的圆盘从A AA搬到C CC，需要1 11次。
3. 将n − 1 n-1n−1个小圆盘从B BB搬到C CC，借助A AA，需要T n − 1 T_{n-1}Tn−1​次。

在第三步中，C CC上的大圆盘不会妨碍小圆盘的移动，它可以看作一个更高的底座。于是我们确实构造出了一个使用2 T n − 1 + 1 2T_{n-1}+12Tn−1​+1次移动的方案。

但此时严格来说，只能写：

T n ≤ 2 T n − 1 + 1. T_n\le 2T_{n-1}+1.Tn​≤2Tn−1​+1.

这是上界，因为还没有排除更快的方案。

3. 为什么任何方案都不可能更快？

考虑任意一个能够完成任务的合法方案，最大的圆盘至少要移动一次。

在它第一次移动之前，其余n − 1 n-1n−1个圆盘必须全部堆在第三根柱子上。否则，要么压住最大的圆盘，要么挡住它要去的柱子。仅完成这次小塔转移，就至少需要T n − 1 T_{n-1}Tn−1​次移动。

再看最大的圆盘最后一次移动。这次它一定移到目标柱C CC；当时所有小圆盘仍须在另一根柱子上。随后把小塔完整搬到C CC，还至少需要T n − 1 T_{n-1}Tn−1​次。

这两段移动不重叠，中间至少有一次最大圆盘的移动，所以：

T n ≥ T n − 1 + 1 + T n − 1 . T_n\ge T_{n-1}+1+T_{n-1}.Tn​≥Tn−1​+1+Tn−1​.

把上下界合起来，才能得到完整的递归式：

T 0 = 0 , T n = 2 T n − 1 + 1 ( n ≥ 1 ) . \boxed{T_0=0,\qquad T_n=2T_{n-1}+1\quad(n\ge1).}T0​=0,Tn​=2Tn−1​+1(n≥1).​

这里不需要假设最大的圆盘只移动一次。即使某个方案把它来回搬了很多次，下界依然成立。

4. 解递归式：为什么两边加 1？

由前几个值可以猜到T n = 2 n − 1 T_n=2^n-1Tn​=2n−1，但也可以直接通过代数变形得到它：

T n + 1 = 2 T n − 1 + 2 = 2 ( T n − 1 + 1 ) . T_n+1=2T_{n-1}+2=2(T_{n-1}+1).Tn​+1=2Tn−1​+2=2(Tn−1​+1).

令U n = T n + 1 U_n=T_n+1Un​=Tn​+1，就有：

U 0 = 1 , U n = 2 U n − 1 . U_0=1,\qquad U_n=2U_{n-1}.U0​=1,Un​=2Un−1​.

这是等比数列，因此U n = 2 n U_n=2^nUn​=2n，从而：

T n = 2 n − 1. \boxed{T_n=2^n-1.}Tn​=2n−1.​

“加 1”可以主动算出来。假设我们希望找到一个常数c cc，让T n + c = 2 ( T n − 1 + c ) T_n+c=2(T_{n-1}+c)Tn​+c=2(Tn−1​+c)，比较常数项便得到1 + c = 2 c 1+c=2c1+c=2c，所以c = 1 c=1c=1。

最后用归纳法核对：n = 0 n=0n=0时公式给出0 00；若T n − 1 = 2 n − 1 − 1 T_{n-1}=2^{n-1}-1Tn−1​=2n−1−1，则

T n = 2 ( 2 n − 1 − 1 ) + 1 = 2 n − 1. T_n=2(2^{n-1}-1)+1=2^n-1.Tn​=2(2n−1−1)+1=2n−1.

因此公式对所有非负整数n nn成立。

5. 用 Python 看见递归过程

下面的生成器依次给出移动步骤。返回的三元组是“圆盘编号、起点、终点”，编号越大，圆盘越大。

defhanoi(n:int,source="A",target="C",spare="B"):ifn<0:raiseValueError("n 必须是非负整数")ifn==0:returnyieldfromhanoi(n-1,source,spare,target)yieldn,source,targetyieldfromhanoi(n-1,spare,target,source)fordisk,source,targetinhanoi(3):print(f"圆盘{disk}:{source}->{target}")

输出为：

圆盘 1: A -> C 圆盘 2: A -> B 圆盘 1: C -> B 圆盘 3: A -> C 圆盘 1: B -> A 圆盘 2: B -> C 圆盘 1: A -> C

三盘恰好需要7 77步，八盘需要255 255255步。每增加一个圆盘，总步数几乎翻倍。

这里也要区分两个计算任务：求步数可以直接计算2 n − 1 2^n-12n−1；列出全部移动则必须输出2 n − 1 2^n-12n−1条记录。在通常把单步操作视为常数时间的分析中，列举的时间复杂度是Θ ( 2 n ) \Theta(2^n)Θ(2n)，递归栈深度是O ( n ) O(n)O(n)。若将所有步骤存入列表，列表本身还需要指数规模的空间。大整数的实际运算成本则另算。

6. 自测：不看公式再想一遍

问题一：为什么只有“三步递归算法”的说明还不够？

因为它只证明了某个步数足够，还没有证明更少的步数不可能。

问题二：若T n = 2 T n − 1 + 1 T_n=2T_{n-1}+1Tn​=2Tn−1​+1，但没有给出初始值，能唯一确定数列吗？

不能。例如把初始值改成T 0 = a T_0=aT0​=a，同样变形可得T n = 2 n ( a + 1 ) − 1 T_n=2^n(a+1)-1Tn​=2n(a+1)−1。边界条件是递归定义的一部分。

问题三：从5 55个圆盘增加到6 66个，最少步数增加了多少？

从31 3131增至63 6363，增加32 3232。一般有T n + 1 − T n = 2 n T_{n+1}-T_n=2^nTn+1​−Tn​=2n。

这一节最值得留下的做法是：先明确所求的量，再分别证明可行方案和不可突破的下界，最后求解递归式。这样得到的公式，才同时回答了“怎么算”和“为什么”。

参考：Ronald L. Graham、Donald E. Knuth、Oren Patashnik 著，张明尧、张凡译，《具体数学：计算机科学基础（第 2 版）》，人民邮电出版社，§1.1。本文的解释、程序和自测为阅读后的整理。

专栏目录 · 下一篇：平面上的直线