１．汉诺塔问题描述
N阶汉诺塔：假设有３个分别命名为x,y,z的三个塔座，在x上有n个盘子，直径大小不同，有小到大按标号１,2,3．..n排列，要借助y将n个盘子转移到z上，期间不能让小盘子压在大盘子上。规则：
- 每次至移动一个盘子；
- 盘子可以插在x,y,z任意一个塔座上；
- 任何时候都不能将大盘压在小盘上。
２．解题思路
当n=1时，直接把盘子由x——>z;
当n>1时，需利用y,首先将(n-1)个盘子由x——>y,把第n个实现x——>z,然后把问题转换为实现(n-1)个盘子由y——>z,借助x;
实现n个盘子由x到z的时候，先把n-1个搬到y上，把第n个搬到z上；然后再借助z,把n-1个盘子搬回x.
循环实现(n-1)个盘子由x到z.
注意:最初递归中涉及到搬盘子都用move()实现一落盘子中最大的那一个，可以在此坐标记。
３．代码
package hanoi;
public class hanoi {
private int c=0;
public void hanoi(int n,char x,char y,char z){
if (n==1)
{
move(x,1,z);
}else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}
public void move(char x,int n,char z){
System.out.println("第"+ ++c +"次移动:"+n+"号盘子,"+x+"——>"+z);
}
public static void main(String[] args){
hanoi e=new hanoi();
e.hanoi(5, 'x', 'y', 'z');
}
}
n=4时，运行结果：
第1次移动:1号盘子,x——>y
第2次移动:2号盘子,x——>z
第3次移动:1号盘子,y——>z
第4次移动:3号盘子,x——>y
第5次移动:1号盘子,z——>x
第6次移动:2号盘子,z——>y
第7次移动:1号盘子,x——>y
第8次移动:4号盘子,x——>z
第9次移动:1号盘子,y——>z
第10次移动:2号盘子,y——>x
第11次移动:1号盘子,z——>x
第12次移动:3号盘子,y——>z
第13次移动:1号盘子,x——>y
第14次移动:2号盘子,x——>z
第15次移动:1号盘子,y——>z