引言
《具体数学:计算机科学基础(第2版)》第1章递归问题
的第1节中说:
我们首先探讨一个称为河内塔的精巧智力题,它是由法国数学家爱德华·卢卡斯于1883年发现的。给定一个由8个圆盘组成的塔,这些圆盘按照大小递减的方式套在三根桩柱中的一根上。(注:下面的图(只有7个圆盘)不是原书中的,是我在网上另外找的。另外,原书中的图只有两个桩柱分别被标为 A 和 B,第三个桩柱没有标号。为了后面说明方便,我给第三个桩柱标上标号 C)
我们的目的是要将整个塔移动到另一根桩柱上,每次只能移动一个圆盘,且较大的圆盘在移动过程中不能放置在较小的圆盘上面。
在书中,称 Tn 是根据卢卡斯的规则将 n 个圆盘从一根桩柱移动到另一根桩柱所需要的最少移动次数。并得到递归式:
- T0 = 0;
- Tn = 2Tn-1 + 1, n > 0
以及相应的封闭形式:
- Tn = 2n - 1, n ≥ 0
河内塔演示
第1章作业题10
设 Qn 是将一个有 n 个圆盘的塔从 A 移动到 B 所需要的最小移动次数,要求所有的移动都必须是顺时针方向的,也就是说,从 A 到 B,从 B 到其他的桩柱,再从其他的桩柱到 A 。又设 Rn 是在这一限制下从 B 返回到 A 所需要移动的最小次数。证明:
Q0 = 0
Qn = 2Rn-1 + 1, n > 0R0 = 0
Rn = Qn + Qn-1 + 1, n > 0(无需解这些递归式,我们将在第 7 章里介绍怎样做。)
我的解答
首先求解 Qn,当 n > 0 时:
- 第 1~n-1 圆盘从 A 移到 C,需 Rn-1 步;
- 第 n 圆盘从 A 移到 B,需 1 步;
- 第 1~n-1 圆盘从 C 移到 B,需 Rn-1 步。
因此,Qn ≤ Rn-1 + 1 + Rn-1 = 2Rn-1 + 1 。还必须说明这是最优解,上式中取得等号。
然后求解 Rn,当 n > 0 时:
- 第 1~n 圆盘从 B 移到 C,需 Qn 步;
- 第 1~n-1 圆盘从 C 移到 B,需 Rn-1 步;
- 第 n 圆盘从 C 移到 A,需 1 步;
- 第 1~n-1 圆盘从 B 移到 A,需 Rn-1 步。
因此,Rn ≤ Qn + Rn-1 + 1 + Rn-1 = Qn + 2Rn-1 + 1 = Qn + Qn = 2Qn 。这个答案和作业题10中给出的不同,应该不是最优解。(我想,当 n 比较大时,Qn 应该远大于 Qn-1 + 1)
小的情形
我们来看看当 n 比较小时的具体数值:
|
|
左边的表格中的数据是用作业题10中的递归式算出来的,右边的表格中的数据是用我的解答中的递归式算出来的。可见我的解答不是最优解。
书上的答案
该书附录 A 习题答案
中给出:
首先证明,当 n > 0 时有 Rn = Rn-1 + 1 + Qn-1 + 1 + Rn-1 。附带指出,第 7 章的方法会告诉我们 。
再次解答
明白了,这就是说,求解 Rn 的步骤是(当 n > 0 时):
- 第 1~n-1 圆盘从 B 移到 A,需 Rn-1 步;
- 第 n 圆盘从 B 移到 C,需 1 步;
- 第 1~n-1 圆盘从 A 移到 B,需 Qn-1 步;
- 第 n 圆盘从 C 移到 A,需 1 步;
- 第 1~n-1 圆盘从 B 移到 A,需 Rn-1 步。
因此,Rn ≤ Rn-1 + 1 + Qn-1 + 1 + Rn-1 = 2Rn-1 + 1 + Qn-1 + 1 = Qn + Qn-1 + 1 。
卢卡斯给这个玩具赋予了一个罗曼蒂克的传说,说的是一个大得多的婆罗贺摩塔(Tower of Brahma),它由 64 个纯金的圆盘堆放在三座钻石做成的方尖塔上。他说,上帝一开始把这些金圆盘放到了第一座方尖塔上,并命令一组牧师按照上面的规则把它们移动到第三座方尖塔上。据说牧师们夜以继日地工作,当他们完成任务时,那座塔就将坍塌,世界也将毁灭。