递归----经典问题:汉诺塔游戏

时间:2022-04-30 09:53:56

题目:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。这里假设最开始放盘子的柱子为A,最终要到到达的柱子为B,另一根柱子也就是一根辅助柱子为C,假设黄金圆盘从上到下依次编号1-N。

思路:题目要求,将1-N从A移动到B,C作为辅助
   1:1~N-1从A移动到C,B为辅助,A作为源
   2:把N移动到B
   3:把1~N-1从C移动到B,A为辅助

代码:

public class TowerOfHanoi {

	public static void main(String[] args) {
		printHanoiTower(3, "A", "B", "C");
	}
	/**
	 * 将N个盘子从source移动到target的路径的打印
	 * 
	 * @param N	初始的N个从小到大的盘子,N是最大编号
	 * @param from 原始柱子
	 * @param to 目标柱子
	 * @param help 辅助柱子
	 */
	
	static void printHanoiTower(int N,String from,String to,String help){
		if (N==1) {
			System.out.println("move "+N+" from "+from+" to "+to);
			return ;
		}
		printHanoiTower(N-1, from, help, to);  // 先把前N-1个盘子挪到辅助空间上去
		System.out.println("move "+N+" from "+from+" to "+to);		// N 可以顺利到达目标盘子
		printHanoiTower(N-1, help, to, from);			// 让N-1从辅助空间回到源空间上去
	}

}

结果:

  递归----经典问题:汉诺塔游戏