动态规划（2）：熟悉尝试1——打印汉诺塔移动的全部过程_C

题目

打印 n 层汉诺塔从最左边移动到最右边的全部过程

分析

假设 n = 3，整个过程分为三步：

① 一大步：将上面两个圆盘移动到中间柱子（并不是一步到位的，过程：最小的先移动到最右，然后中大的盘子移动到中间，最小的从最右移动到中间，最左边的大盘子移动到最右柱子，最小的从中间移动到最左边，中间的移动到最右边，左边的移动到右边）

② 最下面的移动到最右边的柱子

③ 大步：将中间柱子上的两个圆盘移动到最右边柱子

实现解法1

//解法1：将上述的分析直接实现
public class Hanoi {
	public static void hanoi1(int n) {
		leftToRight(n);
	}
	
	// 请把1~N层圆盘 从左 -> 右
	public static void leftToRight(int n) {
		if (n == 1) {
			System.out.println("Move 1 from left to right");
			return ;
		}
		leftToMid(n - 1); //完成了第①步
		System.out.println("Move " + n + " from left to right");//完成第②步
		midToRight(n - 1);//第③步
	}
	
	// 请把1~N层圆盘 从左 -> 中
	public static void leftToMid(int n) {
		if (n == 1) {
			System.out.println("Move 1 from left to mid");
			return;
		}
		leftToRight(n - 1);
		System.out.println("Move " + n + " from left to mid");
		rightToMid(n - 1);
	}

	public static void rightToMid(int n) {
		if (n == 1) {
			System.out.println("Move 1 from right to mid");
			return;
		}
		rightToLeft(n - 1);
		System.out.println("Move " + n + " from right to mid");
		leftToMid(n - 1);
	}

	public static void midToRight(int n) {
		if (n == 1) {
			System.out.println("Move 1 from mid to right");
			return;
		}
		midToLeft(n - 1);
		System.out.println("Move " + n + " from mid to right");
		leftToRight(n - 1);
	}

	public static void midToLeft(int n) {
		if (n == 1) {
			System.out.println("Move 1 from mid to left");
			return;
		}
		midToRight(n - 1);
		System.out.println("Move " + n + " from mid to left");
		rightToLeft(n - 1);
	}

	public static void rightToLeft(int n) {
		if (n == 1) {
			System.out.println("Move 1 from right to left");
			return;
		}
		rightToMid(n - 1);
		System.out.println("Move " + n + " from right to left");
		midToLeft(n - 1);
	}
}

解法2

//解法二：对解法1的一些优化，可以用参数代替三个柱子，省去冗余代码
public class Hanoi {
	public static void hanoi2(int n) {
		if (n > 0) {
			func(n, "left", "right", "mid");
		}
	}
    //1~N 在 from
    //去：to
    //另一个 other
	//忘掉左中右柱子，假设1~n在from上，现在要移动到to上，另外一个叫做other（可能是左中右的任意一个）
    //所以前面的6个过程都可以用这三个可变参数来代替
	public static void func(int N, String from, String to, String other) {
		if (N == 1) { // base
			System.out.println("Move 1 from " + from + " to " + to);
		} else {
			func(N - 1, from, other, to);
			System.out.println("Move " + N + " from " + from + " to " + to);
			func(N - 1, other, to, from);
		}
	}
}

解法3

//解法3：迭代
public class Hanoi {
	public static class Record {
		public boolean finish1;
		public int base;
		public String from;
		public String to;
		public String other;

		public Record(boolean f1, int b, String f, String t, String o) {
			finish1 = false;
			base = b;
			from = f;
			to = t;
			other = o;
		}
	}

	public static void hanoi3(int N) {
		if (N < 1) {
			return;
		}
		Stack<Record> stack = new Stack<>();
		stack.add(new Record(false, N, "left", "right", "mid"));
		while (!stack.isEmpty()) {
			Record cur = stack.pop();
			if (cur.base == 1) {
				System.out.println("Move 1 from " + cur.from + " to " + cur.to);
				if (!stack.isEmpty()) {
					stack.peek().finish1 = true;
				}
			} else {
				if (!cur.finish1) {
					stack.push(cur);
					stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
				} else {
					System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
					stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
				}
			}
		}
	}
}