首页 > 信息学奥赛> 详细内容
汉诺塔的图解递归算法
日期:2020-03-06 
一.起源:
  汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

二.抽象为数学问题:
  如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数



解:(1)n == 1

             第1次  1号盘  A---->C       sum = 1 次

       (2)  n == 2

             第1次  1号盘  A---->B

             第2次  2号盘  A---->C

             第3次  1号盘  B---->C        sum = 3 次

  (3)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次  1号盘  A---->C        sum = 7 次

 

不难发现规律:1个圆盘的次数 2的1次方减1

       2个圆盘的次数 2的2次方减1

                         3个圆盘的次数 2的3次方减1

                         。  。   。    。   。 

                         n个圆盘的次数 2的n次方减1

 故:移动次数为:2^n - 1

三.算法分析(递归算法):
       我们在利用计算机求汉诺塔问题时,必不可少的一步是对整个实现求解进行算法分析。到目前为止,求解汉诺塔问题最简单的算法还是同过递归来求。

       实现这个算法可以简单分为三个步骤:

    (1)     把n-1个盘子由A 移到 B;

    (2)     把第n个盘子由 A移到 C;

    (3)     把n-1个盘子由B 移到 C;

从这里入手,在加上上面数学问题解法的分析,我们不难发现,移到的步数必定为奇数步:

    (1)中间的一步是把最大的一个盘子由A移到C上去;

    (2)中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,

    (3)中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;

public class Hanoilmpl {
 
    public static void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            move(A, C);
        } else {
            hanoi(n - 1, A, C, B);//将n-1个盘子由A经过C移动到B
            move(A, C);             //执行最大盘子n移动
            hanoi(n - 1, B, A, C);//剩下的n-1盘子,由B经过A移动到C
        }
    }
 
    private static void move(char A, char C) {//执行最大盘子n的从A-C的移动
        System.out.println("move:" + A + "--->" + C);
    }
 
    public static void main(String[] args) {
        System.out.println("移动汉诺塔的步骤:");
        hanoi(3, 'a', 'b', 'c');
    }
}