思路

  1. 使用河內塔作為練習
  2. 拆解大問題 -> 小問題

實作

測試方法

public class DivideConquer_Hanoi2 {
    //創建三個柱子
    static Stack<Integer> pillar_A = new Stack<>();
    static Stack<Integer> pillar_B = new Stack<>();
    static Stack<Integer> pillar_C = new Stack<>();

    public static void main(String[] args) {
        /** initialization **/
        // 添加數字進去
        //[1,2,3,4,5]
        pillar_A.add(5);
        pillar_A.add(4);
        pillar_A.add(3);
        pillar_A.add(2);
        pillar_A.add(1);

        int layer = pillar_A.size(); //5

        /** Divide & Conquer **/
        hanoi(layer, pillar_A, pillar_B, pillar_C);

        System.out.println();
    }

具體

private static void hanoi(int layer, Stack<Integer> pillar_from, Stack<Integer> pillar_mid, Stack<Integer> pillar_to) { // 相對位置
    //改變觀看視角 不是以變數名稱作絕對位置 而是以當下傳入為主
    if (layer == 0) return; // 沒東西可以用了

    /** base case : when layer == 1, it's our base case **/

    /** step01: move the above plate to the pillar_mid, to clear the room for the plate below **/
    // 把上面盤子拿出來 把來源盤子移到中間
    hanoi(layer - 1, pillar_from, pillar_to, pillar_mid);

    /** step02: main target **/
    // 出現 base -> layer=1
    Integer plate = pillar_from.pop();
    pillar_to.push(plate);

    /** step03: move the original above plate back **/
    hanoi(layer -1 , pillar_mid, pillar_from, pillar_to);
}