河内塔问题.doc

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