汉诺塔实现

最近闲来无事外加心血来潮小小的写个汉诺塔程序，复习下递归

 

从左到右依次编号A,B,C栏。

 

当只有一个盘的时候是最简单的，直接移动到目的地即可。

if (n == 1) {
      move(n, A, C);
  }

       

        当有两个盘的时候也很简单，把第一个移到B，接着把最下面的移到C，最后把中间的移到C，结束。

 

        当有N个盘的时候可以这样理解，先把上面的N-1个盘从起点A移动到B，然后把最下的那个盘移动到C，最后把B上的全移动到C，（即以A为起点，B为辅助栏,C为终点进行移动）结束。

        而那N-1个盘的从A移动到B可以理解为是以A为起点，B为终点，C为辅助栏的移动。当然移动方法就是先把上面的N-2个盘以A为起点，B为终点，C为辅助栏进行移动。

        以此类推，每次移动就是先移动上面的N-1个到辅助栏，然后把最下的那个移动到终点，最后把上面的N-1个移动到终点。起点终点辅助栏每次都不一样。

        然后可以开始递归，代码如下：

public static void hanoi(int n, char A, char B, char C) {
  if (n == 1) {
      move(n, A, C);
  } else {
      hanoi(n - 1, A, C, B);//把上面N-1个从起点A移动到辅助栏B，即把A到起点，B当终点，C当辅助栏
      move(n, A, C);//把最下面的盘子从起点A，移动到终点C
      hanoi(n - 1, B, A, C);//把B上的N-1块盘子以B为起点，C为终点,A为辅助栏移动
  }
    }

    public static void move(int x, char now, char dest) {
  System.out.println(count++ + ". move " + x + " from " + now + " to "
    + dest);
    }