汉诺塔(hanoi)

汉诺塔的由来

传说一

开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小， 依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计 算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。

 

由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：            18，446，744，073，709，551，615

 

这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。

传说二

问题的提出:约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。

 

递归算法

首先，考虑A杆上只有一个盘子(这样是递归的终止条件)，任务变成：

   *将A杆上的唯一一个盘子移到C杆上；

 

然后，考虑A杆最下面的一个盘子而非上面的一些盘子，于是任务变成了：
   *将上面的63个盘子移到B杆上；
   *将A杆上剩下的盘子移到C杆上；
   *将B杆上的全部盘子移到C杆上。

将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子....的工作。

 

为了更清楚地描述算法，可以定义一个函数hanoi(n,a,b,c)。该函数的功能是将N个盘子从A杆上借助B杆移动到c杆上。这样移动N个盘子的工作就可以按照以下过程进行：
      1) hanoi(n-1,a,c,b);
      2) 将一个盘子从a移动到c上；

      3) hanoi(n-1,b,a,c)；
重复以上过程，直到将全部的盘子移动到位时为止。

 

汉诺塔算法的递归实现C++源代码

Please find the source file in attachement - hanoi_recursive.cpp

 

g++ -o hanoi_recursive hanoi_recursize.cpp

 

汉诺塔算法的递归实现C源代码

Please find the source file in attachement - hanoi_recursive.c

 

gcc -o hanoi_recursive1 hanoi_recursive.c

 

非递归算法

当盘子的个数为n时，移动的次数应等于2^n - 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。

（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。

所以结果非常简单，就是按照移动规则向一个方向移动金片，如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

 

汉诺塔算法的非递归实现C++源代码

 

Please find the source file in attachement - hanoi_non_recursive.cpp

 

g++ -o hanoi_non_recursive hanoi_non_recursive.cpp