汉诺塔问题

向右看齐 2022-04-17 05:12 294阅读 0赞

问题描述：

相传在[古印度][Link 1]圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

![20181113152912984.png][]

问题分析：

先假设除最下面的盘子之外，我们已经成功地将上面的63个盘子移到了b柱，此时只要将最下面的盘子由a移动到c即可。如图：

![23101623-8d8b7e4a0b8644a180276d1f8d504754.png][]

当最大的盘子由a移到c后，b上是余下的63个盘子，a为空。因此现在的目标就变成了将这63个盘子由b移到c。这个问题和原来的问题完全一样，只是由a柱换为了b柱，规模由64变为了63。因此可以采用相同的方法，先将上面的62个盘子由b移到a，再将最下面的盘子移到c……对照下面的过程，试着是否能找到规律：

1.  将b柱子作为辅助，把a上的63个圆盘移动到b上
2.  将a上最后一个圆盘移动到c
3.  将a作为辅助，把b上的62个圆盘移动到a上
4.  将b上的最后一个圆盘移动到c
5.  .....

三个盘子：

![702782-20161114211933513-1127552732.gif][]

四个盘子：

![702782-20161114212352576-1869972276.gif][]

也许你已经发现规律了，即每次都是先将其他圆盘移动到辅助柱子上，并将最底下的圆盘移到c柱子上，然后再把原先的柱子作为辅助柱子，并重复此过程，这个过程称为递归。

伪代码实现：

hanoi(n,A,B,C){
      //n个盘子，柱子A，B，C
      if(n==1) move(A,C);  //只有一个盘子时，直接将A柱上的盘子移动到C柱上
      else{
           hanoi(n-1,A,C,B);//将n-1个盘子由a移动到b，以c为辅助柱子（注意参数顺序）
           move(A,C);//将a上的最后一个盘子移动到c
           hanoi(n-1,B,A,C);//将n-1个盘子由b移动到c，以a为辅助柱子
          }
    }

递归算法：

void hanoi(int n,char x,char y,char z){
            if(n == 1)
                    move(x,1,z);
            else{
                    hanoi(n-1,x,z,y);
                    move(x,n,z);
                    hanoi(n-1,y,x,z);
            }
    }

[Link 1]: https://baike.baidu.com/item/%E5%8F%A4%E5%8D%B0%E5%BA%A6
[20181113152912984.png]: /images/20220417/5d252eb6047d456b8bc741a83c461ee8.png
[23101623-8d8b7e4a0b8644a180276d1f8d504754.png]: /images/20220417/01b7a9ba27924e92b92b6dc05427fce6.png
[702782-20161114211933513-1127552732.gif]: /images/20220417/3f2031af4d5c4af291db760564bc0c48.png
[702782-20161114212352576-1869972276.gif]: /images/20220417/f473826d2df74880aed0d6817e2fc77f.png