汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。

游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

怎么做呢？

分析：对于这样一个问题，64个盘子，相信没有谁可以直接说出每一步的移动方法吧。但我们可以把大问题化解为小问题来慢慢解决。假如要移动盘子数为n，并设移动时盘子在哪个杆就表示为哪个字母。

• n=1时，直接把盘子从A移到C，即: A->C
• n=2时，先把一个盘子从A移到B，再把另一个盘子从A移到C，最后把B上的盘子移到C。这个过程可以表示为：A->B,A->C,B->C
• n=3时，可以这样移：A->C,A->B,C->B,A->C,B->A,B->C,A->C

观察上面的几个例子可以发现，在把最大的一个盘子从A移到C时，另外的所有盘子都在B上按从下往上，从大到小的顺序排列着。这意味着要把64个盘子从A移到C上，只需要先把63个盘子从A移到B上；而要把63个盘子从A移到B上只需要先把62个盘子从A移到C上。。。。。这样一层一层往下拆分问题，直到盘子为停止，这样就形成了递归。
所以把n个盘子从A移到C可以总结以下三步：

• 第一步以C盘为中介，从A杆将1至n-1号盘移至B杆；
• 第二步将A杆中剩下的第n号盘移至C杆；
• 第三步以A杆为中介；从B杆将1至n-1号盘移至C杆

代码实现

import java.util.Scanner;
public class TestDemo6 {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();     //输入要移动的盘子个数
        hanio(n,'A','B','C');     //调用hanio函数，并将三个杆分别定义为A,B,C
    }

    public static void move(char pil1,char pil2) {    //为了方便，在这写一个移盘子函数
        System.out.print(pil1+"->"+pil2+" ");        //表示把盘子从pil1杆移到pil2杆
    }

    public static void hanio(int n,char pil1,char pil2,char pil3) {   //总移盘子函数
        if(n==1) {          //递归结束的条件就是n=1，直接调用移盘子函数，从第一个杆移到第三个杆
            move(pil1,pil3);     
        }else {            //移动的盘子数不为1时
            hanio(n-1,pil1,pil3,pil2);      //调用自己，把n-1个盘子从第一个杆通过第三个杆移到第二个杆
            move(pil1,pil3);                //n-1个盘已经在第二个杆上了，直接把最后一个盘，从第一个杆移动到第三个杆
            hanio(n-1,pil2,pil1,pil3);   //最后把第二个杆上的n-1个盘子通过第一个杆移动到第三个杆
        }
    }
}

运行结果

• 盘子数为1时
  
• 盘子数为2时

• 盘子数为3时