1、河内塔问题 智力游戏 数学书上有一道河内塔的问题，这是一个流传很广的游戏：1.有三根杆子 A、B、C。A 杆上有三个碟子。2.每次移动一个碟子，大碟子不能移在小碟子上面。3.把 A 杆上的三个碟子移到 C 杆上需要多少步？如果 A 杆上有四个、五个碟子各需要多少步？河内塔问题的由来1883 年，一位法国的数学家 Edouard Lucas 教授在欧洲的一份杂志上介绍了一个相当吸引人的难题迷人的智力游戏。这个游戏名为河内塔(Tower of Hanoi)，它源自古印度神庙中的一段故事(也有人说是 Lucas 教授为增加此游戏之神秘色彩而捏造的)。传说在古老的印度，有一座神庙，据说它是宇宙的中心。
2、在庙宇中放置了一块上面插有三根长木钉的木板，在其中的一根木钉上，从上至下被放置了 64片直径由小至大的圆环形金属片。古印度教的天神指示他的僧侣们将 64 片的金属片移至三根木钉中的其中一根上。规定在每次的移动中，只能搬移一片金属片，并且在过程中必须保持金属片由上至下是直径由小至大的次序，也就是说不论在那一根木钉上，圆环形的金属片都是直径较小的被放在上层。直到有一天，僧侣们能将 64 片的金属片依规则从指定的木钉上全部移动至另一根木钉上，那么，世界末日即随之来到，世间的一切终将被毁灭，万物都将至极乐世界。 我们先测算一下按上述规则移完这 64 片金属盘所要花费的时间吧！要按上述规则移动这 64
3、片金属片至少要几次的搬移才能完成呢？ 设 an 表示当金属盘总共有 n 片时至少所需搬动的次数，则 a1=1.恰好是 21-1 a2=3.恰好是 22-1 a3=7.恰好是 23-1 a4=15.恰好是 24-1 a5=31.恰好是 25-1 a6=63.恰好是 26-1 于是我们得到一个递归的公式： a n=2n-1，假如这位僧侣每秒搬移一次金属盘的话，那么 64 片金属盘至少需要经过 264 -1=18,446,744,073,709,551,615 秒的搬移才能完成。按照这样的规律即使他日以继夜的不停地搬移金属盘，也需要 584,942,417,355 年之久才可移动完成。即对这 64
4、个盘子的搬移大约需要1.84x1019 次的搬移，在每秒可搬移一次的情况下，大概需要 5850 亿年才可搬移完成！可能那时便到世界之末日了。这就是 1883 年法国的数学家 Edouard Lucas 提出的河内塔问题(Tower of Hanoi)。也是一个非常吸引人的智力游戏和数学上的递归问题。有关这个问题的解决方法就是先假设我们已有 n-l 个盘子的解法。首先我们先来讨论几个数量较少的情形:(首先将盘子由小到大依序编号为 1,2,3.n)A. n=l 时，很简单。直接把盘子从 A 移到 C，次数只有一次。B. n=2 时，移动次序如下: (1)移动盘子 l 从木桩 A 到木桩 B。(2)
5、移动盘子 2 从木桩 A 到木桩 C。(3)移动盘子 l 从木桩 B 到木桩 C。 因此，总共须移动 22-1=3 次，次序为 1,2,1。C. n=3 时，移动次序如下: (1)移动盘子 1 从木桩 A 到木桩 C。(2)移动盘子 2 从木桩 A 到木桩 B。(3)移动盘子 1 从木桩 C 到木桩 B。(4)移动盘子 3 从木桩 A 到木桩 C。(5)移动盘子 1 从木桩 B 到木桩 A。(6)移动盘子 2 从木桩 B 到木桩 C。(7)移动盘子 l 从木桩 A 到木桩 C。因此，总共须移动 23-1=7 次，次序为 1,2,1,3,1,2,1。D. n=4 时，移动次序如下:(1)移动盘子
6、 1 从木桩 A 到木桩 B。(2)移动盘子 2 从木桩 A 到木桩 C。(3)移动盘子 l 从木桩 B 到木桩 C。(4)移动盘子 3 从木桩 A 到木桩 B。(5)移动盘子 1 从木桩 C 到木桩 A。(6)移动盘子 2 从木桩 C 到木桩 B。(7)移动盘子 l 从木桩 A 到木桩 B。(8)移动盘子 4 从木桩 A 到木桩 C。(9)移动盘子 l 从木桩 B 到木桩 C。(10)移动盘子 2 从木桩 B 到木桩 A。(11)移动盘子 1 从木桩 C 到木桩 A。(12)移动盘子 3 从木桩 B 到木桩 C。(13)移动盘子 l 从木桩 A 到木桩 B。(14)移动盘子 2 从木桩 A
7、到木桩 C。(15)移动盘子 1 从木桩 B 到木桩 C。因此，总共需移动 24-1=15 次，次序为 121312141213121。当任意 n 个盘子需搬移时，我们可以归纳出一套规则。1.先将 ln-l 号盘子从(from)A 经由(by)B 搬至(to)C。2.n:AB(将 n 号盘子由 A 搬至 B)。3.再将 ln-l 号盘子从 C 经由 A 搬至 B。我们把搬 n 个盘子的动作分解成三大步，第一和第三大步都是搬 n-l 个盘子，第二大步则是搬 1 个盘子。至于搬 n 个盘子共需几次搬动呢?我们假设 An 为搬 n 个盘子所需搬动次数，A n-1 则是搬 n-l 个盘子所需搬动次数。终止条件(边界条件)为 A1=l。所以：由前述规则可知，搬 n 个盘子可以分解成三大步。
