一、汉诺塔传说

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

二、汉诺塔规则

1、有三根相邻的柱子，标号为a,b,c。

2、a柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。

3、要求把所有a柱子上的圆盘按大小顺序重新摆放在c柱子上。并且规定，在小圆盘上不能放大圆盘，在三个塔之间一次只能移动一个圆盘。

三、题解步骤

1、当n=1时

将1号从A移动到C即可

2、当n=2时

第一步：将1号从A移动到B

第二步：将2号从A移动到C

第三步：将1号从B移动到C

3、当n=3时

第一步：将1号从A移动到C

第二步：将2号从A移动到B

第三步：将1号从C移动到B

第四步：将3号从A移动到C

第五步：将1号从B移动到A

第六步：将2号从B移动到C

第七步：将1号从A移动到C

......

由上述可以看出，每次都会有将最大的一个从A移动到C的步骤。假如有n（n>1）个需要移动的盘子，我们可以将这些步骤分为3步：

1、将n-1个圆盘从a->b

a>b  a起始柱 b目标柱 c辅助柱

2、将1个圆盘从a->c

a>c  a起始柱 c目标柱

3、将n-1个圆盘从2->3

b>c  b起始柱 a辅助柱 c目标柱

四、解题代码

public class Test {
//移动的次数
private static int num=0;
public static void main(String[] args) {
   move(3,'a','b','c');
}
public static void print(int no,char from,char to) {
   System.out.printf("第%d次移动，把%d号盘子从%c移动到%c\n",++num,no,from,to);
}
public static void move(int no,char a,char b,char c) {
   if(no==1) {
   print(no,a,c);
      return;
   }
   move(no-1,a,c,b);
   print(no,a,c);
   move(no-1,b,a,c);
}
}

运行结果：

五、如何理解代码中的递归调用

所谓递归调用就是通过不断调用自己来解决问题的方法。如果无法理解，我们可以将递归所调用的自己的方法写成一个一样的方法进行调用。如此题中的汉诺塔。

当n==1时，只需要直接将1号盘从a移动到c

当n==2时，先将n==2，a,b,c代入test()方法,经过判断号再次调用test()方法，此时n==1，a,c,b，所以将1号从A移动到B，再执行print(n, a, c); move2(n - 1, b, a, c);

将2号从A移动到C，将1号从B移动到C。

当n==3时，递归的次数更多，我们可以再写一个方法来便于理解

public class Test {
//移动的次数
private static int num=0;
public static void main(String[] args) {
   move(2,'a','b','c');
}
public static void print(int no,char from,char to) {
   System.out.printf("第%d次移动，把%d号盘子从%c移动到%c\n",++num,no,from,to);
}
public static void move(int no,char a,char b,char c) {
   if(no==1) {
      print(no,a,c);
      return;
   }
   move2(no-1,a,c,b);
   print(no,a,c);
   move2(no-1,b,a,c);
}
public static void move2(int no,char a,char b,char c) {
   if(no==1) {
      print(no,a,c);
      return;
   }
   move2(no-1,a,c,b);
   print(no,a,c);
   move2(no-1,b,a,c);
}
}

此时我们不采用递归调用，只需要调用move2()方法，move2()方法重复n==2时的动作。此调用与递归的结果相同。

总结：在代码的运行过程中如果不理解调用的过程，主要原因是a，b，c在move()方法中一直会变化位置。每次选取的过渡柱子不一样