暴力遞回——漢諾塔問題

列印n層漢諾塔從最左邊移動到最右邊的全部程序

暴力遞回就是嘗試

1）把問題轉化為規模縮小了的同類問題的子問題

2）有明確的不需要繼續進行遞回的條件(base case)

3）有當得到了子問題的結果之后的決策程序

4）不記錄每一個子問題的解

補充一點，如果記錄每一個子問題的解就是動態規劃，后續文章會講到，

遞回方法

假設有3跟柱子，左、中、右，我們細分為如下三個步驟：

1）將1~N-1層圓盤從左 -> 中（大問題，需要繼續劃分為小問題）

2）將第N層圓盤從左 -> 右（base case）

3）將1~N-1層圓盤從中 -> 右（大問題，需要繼續劃分為小問題）

遞回方法改進版

如果我們忘記柱子的左中右，將三根柱子標記為from、to、other，我們實作的是，將所有的圓盤（一共N層）從from -> to，同樣細分為3個步驟：

1）將1~N-1層圓盤從from -> other（大問題，需要繼續劃分為小問題）

2）將第N層圓盤從from -> to（base case，可以直接列印）

3）將1~N-1層圓盤從other -> to（大問題，需要繼續劃分為小問題）

貌似沒什么改進，因為還是細分這三步，同樣要遞回，但關鍵在于忘掉柱子的左中右順序，只需要三個變數，代碼可以少很多，

總結

漢諾塔問題還有非遞回的解法，因為任何遞回都可以改成非遞回，只需要自己設計壓堆疊，但是博主個人認為漢諾塔的遞回方法比非遞回更好容易理解和實作，非遞回自己去設計壓堆疊還比較麻煩，博主目前也還沒弄懂，所以就只附上代碼了，后面如果搞懂了在補充吧，😄

附上完整代碼

package com.harrison.class12;

import java.util.Stack;

public class Code01_Hanoi {
	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);
	}
	
	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 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);
	}
	
	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 hanoi1(int n) {
		leftToRight(n);
	}
	
	public static void f(int n,String from,String to,String other) {
		if(n==1) {
			System.out.println("move 1 from "+ from + " to " + to);
		}else {
			f(n-1, from, other, to);
			System.out.println("move " + n + " from " +from +" to "+to);
			f(n-1, other,to,from);
		}
	}
	
	public static void hanoi2(int n) {
		if(n>0) {
			f(n, "left", "right", "mid");
		}
	}
	
	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));
				}
			}
		}
	}
	
	public static void main(String[] args) {
		int n=3;
		hanoi1(n);
		System.out.println("=======================");
		hanoi2(n);
		System.out.println("=======================");
		hanoi3(n);
		System.out.println("=======================");
	}
}