引言

《具体数学:计算机科学基础(第2版)》第1章递归问题的第1节中说:

我们首先探讨一个称为河内塔的精巧智力题,它是由法国数学家爱德华·卢卡斯于1883年发现的。给定一个由8个圆盘组成的塔,这些圆盘按照大小递减的方式套在三根桩柱中的一根上。(注:下面的图(只有7个圆盘)不是原书中的,是我在网上另外找的。另外,原书中的图只有两个桩柱分别被标为 A 和 B,第三个桩柱没有标号。为了后面说明方便,我给第三个桩柱标上标号 C)
HanoiABC
我们的目的是要将整个塔移动到另一根桩柱上,每次只能移动一个圆盘,且较大的圆盘在移动过程中不能放置在较小的圆盘上面。

在书中,称 Tn 是根据卢卡斯的规则将 n 个圆盘从一根桩柱移动到另一根桩柱所需要的最少移动次数。并得到递归式:

  • T0 = 0;
  • Tn = 2Tn-1 + 1, n > 0

以及相应的封闭形式:

  • Tn = 2n - 1, n ≥ 0

河内塔演示

HanoiGif

第1章作业题10

设 Qn 是将一个有 n 个圆盘的塔从 A 移动到 B 所需要的最小移动次数,要求所有的移动都必须是顺时针方向的,也就是说,从 A 到 B,从 B 到其他的桩柱,再从其他的桩柱到 A 。又设 Rn 是在这一限制下从 B 返回到 A 所需要移动的最小次数。证明:

        Q0 = 0
Qn = 2Rn-1 + 1, n > 0
                R0 = 0
Rn = Qn + Qn-1 + 1, n > 0

(无需解这些递归式,我们将在第 7 章里介绍怎样做。)

我的解答

首先求解 Qn,当 n > 0 时:

  1. 第 1~n-1 圆盘从 A 移到 C,需 Rn-1 步;
  2. 第 n 圆盘从 A 移到 B,需 1 步;
  3. 第 1~n-1 圆盘从 C 移到 B,需 Rn-1 步。

因此,Qn ≤ Rn-1 + 1 + Rn-1 = 2Rn-1 + 1 。还必须说明这是最优解,上式中取得等号。

然后求解 Rn,当 n > 0 时:

  1. 第 1~n 圆盘从 B 移到 C,需 Qn 步;
  2. 第 1~n-1 圆盘从 C 移到 B,需 Rn-1 步;
  3. 第 n 圆盘从 C 移到 A,需 1 步;
  4. 第 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 比较小时的具体数值:

n0123456
Qn0151543119327
Rn0272159163447
           
n0123456
Qn01521853411365
Rn0210421706822730

左边的表格中的数据是用作业题10中的递归式算出来的,右边的表格中的数据是用我的解答中的递归式算出来的。可见我的解答不是最优解。

书上的答案

该书附录 A 习题答案中给出:

首先证明,当 n > 0 时有 Rn = Rn-1 + 1 + Qn-1 + 1 + Rn-1 。附带指出,第 7 章的方法会告诉我们 Qn

再次解答

明白了,这就是说,求解 Rn 的步骤是(当 n > 0 时):

  1. 第 1~n-1 圆盘从 B 移到 A,需 Rn-1 步;
  2. 第 n 圆盘从 B 移到 C,需 1 步;
  3. 第 1~n-1 圆盘从 A 移到 B,需 Qn-1 步;
  4. 第 n 圆盘从 C 移到 A,需 1 步;
  5. 第 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 。


ConcreteMath