递归解决汉诺塔问题解法java代码

落日映苍穹つ 2022-08-06 06:20 133阅读 0赞

汉诺塔问题简介：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

这里是用递归的方法，还算比较好理解。盘子=1是递归的出口，假设有三个柱子A、B、C，n个盘子从上到下编号为1~n，想要从A移动到C，就考虑先把n上面的前n-1个移动到B，然后再把第n个盘子移动到C，再把前n-1个从B移动到C。java实现代码如下

public class Hanoi {
    	public static void tower(int n, char fromDisk, char toDisk, char midDisk) {
    		if (n == 1) {
    			System.out.println("1号盘子从" + fromDisk + "移动到" + toDisk);
    			return;
    
    		}
    		tower(n - 1, fromDisk, midDisk, toDisk);
    		System.out.println(+n + "号盘子从" + fromDisk + "移动到" + midDisk);
    		tower(n - 1, midDisk, toDisk, fromDisk);
    	}
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		tower(4, 'A', 'B', 'C');
    	}
    }

void 方法中有return可以直接退出方法。

tower方法 四个参数，分别是盘子个数，开始移动的柱子，移动到的柱子，中间借助的柱子（变量名都写成盘子结尾的了。。意会）。

本文展示4个盘子的移动方法

运行结果如下

1号盘子从A移动到C  
2号盘子从A移动到C  
1号盘子从C移动到B  
3号盘子从A移动到B  
1号盘子从B移动到A  
2号盘子从B移动到A  
1号盘子从A移动到C  
4号盘子从A移动到C  
1号盘子从C移动到B  
2号盘子从C移动到B  
1号盘子从B移动到A  
3号盘子从C移动到A  
1号盘子从A移动到C  
2号盘子从A移动到C  
1号盘子从C移动到B