递归—汉诺塔

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

1：如果A只有一个（A->C）

2：如果A有两个（A->B）,(A->C),(B->C)

3：如果A有三个（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).

可以发现每增加一步，其中的步骤会多很多。但是不妨这样想。当有N个要从A->C时，且已知移动方式。使用函数表示move（a->c）。如果要是N 1个该如何想呢。是不是先不看最底下的那个盘子呢，把剩下的N从A移到B上。突然发现最底下还有一个盘子，刚好C为空，把这个最大的放在C上，剩下的就是N个从B移到C的问题了。

再看上面的3：把最上面的盘子从A移到B，在把A 的最大移到C。再把2个盘子从B借助A移到C。

再看上面的2：把最上面的盘子移到B，把最底下移到C，就转化成B移到C一个盘子的问题了。这种递归要从每一步的关系找。把N个问题差成N-1移动和最底下移动的问题。

1. 如果A只有一个（A->C）
2. 如果A有两个（A->B）,(A->C),(B->C)
3. 如果A有三个（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).
4. 如果更多，那么将会爆炸式增长。

可以发现每增加一步，其中的步骤会多很多。但是不妨这样想：

• 当有1个要从A->C时，且已知移动方式。使用函数表示move（a->c）。同理其他move操作。
• -------省略中间若干步骤不看，用递归思想看问题

分析：n个从a—>c和n-1个a—>c有什么联系？(hannuo(n)—>hannuo(n-1)有啥关系)

假设有n个盘子

• hannuo(n-1)之后n-1个盘子从A—>C.

此时剩下底下最大的，只能移动到B，move(A,B)

那么你是否发现什么眉目了，只需原先的huannuo(n-1)相同操作从C—>B即可完成转移到B；那么我们的之前函数应该写成hannuo(n-1,A,C)但是又用到B，所以把B传进来hannuo(n-1,A,B,C)先表示为从n-1个从A(借助B执行若干操作)转到C。

• 这一系列操作使得将n个盘子从A—>B但是我们要的是A—>C才是需要的hannuo(n,A,B,C);那么我们只需要更改下hannuo(n-1,----)顺序就好啦！

代码如下：

package 递归;
public class hannuota {
  static void move(char a,char b)
  {
    System.out.println("移动最上层的"+ a+ "到"+ b+ "\t");
  }
  static void hannuota(int n,char a,char b,char c)//主要分析每一大步对于下一步需要走的。
  {
    if(n==1) {move(a,c);}//从a移到c
    else
    {
      hannuota(n-1,a,c,b);//将n-1个从a借助c移到b
      move(a,c); //将第n（最后一个）从a移到c。
      hannuota(n-1,b,a,c);//再将n-1个从b借助a移到c
    }
  }
  public static void main(String[] args)
  {
    hannuota(5,'a','b','c');
  }
}