Java递归求解汉诺塔问题

汉诺塔问题

规则：

1.每次只能移动一个圆盘。

2.圆盘可以插在X,Y,Z中的任一塔座上。

3.任何时刻都不能让一个大的圆盘落在小的圆盘上面。

算法：

1.当X塔只有1个盘子时，将编号为1的圆盘从X移到Z处。（编号自上而下，由小到大）

2.当X塔有2个盘子时，将编号为1的圆盘从X移动到Y处，接着将编号为2的圆盘从X移动到Z处，最后将编号为1的圆盘从Y移到Z处。

3.当X塔有3个盘子时，将X塔上编号1至2的盘子（共2个）移动到Y塔上（需借助Z塔），接着将X塔上的3号最大的盘子移动到Z塔，最后将Y塔上的两个盘子借助X塔移动到Z塔上。

4.当X塔有n个盘子时，需要借助Y塔作为辅助塔，将X塔上编号1到n-1的盘子从X塔借助Z为辅助塔移动到Y塔，接着将X塔上编号为n的圆盘从X移动到Z塔。最后将Y塔上的n-1个圆盘借助A为辅助塔移动到Z塔。

因此可采用递归算法

public class Hanoi {
 private static int i = 1;//记录执行的次数
 public static void main(String[] args) {
  int num;//盘子的个数
  try {
   System.out.print("请输入盘子的个数：");
   Scanner input = new Scanner(System.in);
   num = input.nextInt();
   String x="A",y="B",z="C";//定义三座塔
   hanoi(num,x,y,z);
  } catch (Exception e) {
   System.out.println("请输入正整数！");
  }
 }
 /**
  * 
  * @param n 盘标号
  * @param x 源位置
  * @param z 目的位置
  */
 public static void move(int num,String x, String z){
  System.out.println("第"+i+++"步，将"+num+"号盘子从"+x+"移动到"+z);
 }
 
 /**
  * 
  * @param num   盘标号
  * @param x   ”A“
  * @param y  ”B“
  * @param z   ”C“
  */
 public static void hanoi(int num,String x, String y, String z){
  if(num == 1){
   move(1,x,z);   //一个盘子时，直接从x移动z
  }else{
   hanoi(num-1,x,z,y);//将num-1个盘子从x移动y，借助z
   move(num,x,z);   //将当前最大的盘子num从x移动到z
   hanoi(num-1,y,x,z);//将num-1个盘子从y移动z，借助x
  }
 }
}

输出结果示例：