-
- /*
- TowerOfHanoi.java 遞迴版 及 模擬呼叫堆疊版 求解河內塔
-
- > java TowerOfHanoi
- Hanoi Tower by Implicit Call Stack 遞迴版
- A:[3, 2, 1], B:[], C:[] 1: Move disk 1 from A to C
- A:[3, 2], B:[], C:[1] 2: Move disk 2 from A to B
- A:[3], B:[2], C:[1] 3: Move disk 1 from C to B
- A:[3], B:[2, 1], C:[] 4: Move disk 3 from A to C
- A:[], B:[2, 1], C:[3] 5: Move disk 1 from B to A
- A:[1], B:[2], C:[3] 6: Move disk 2 from B to C
- A:[1], B:[], C:[3, 2] 7: Move disk 1 from A to C
- A:[], B:[], C:[3, 2, 1]
-
- Hanoi Tower by Explicit Stack 模擬呼叫堆疊版
- A:[3, 2, 1], B:[], C:[] 1: Move disk 1 from A to C
- A:[3, 2], B:[], C:[1] 2: Move disk 2 from A to B
- A:[3], B:[2], C:[1] 3: Move disk 1 from C to B
- A:[3], B:[2, 1], C:[] 4: Move disk 3 from A to C
- A:[], B:[2, 1], C:[3] 5: Move disk 1 from B to A
- A:[1], B:[2], C:[3] 6: Move disk 2 from B to C
- A:[1], B:[], C:[3, 2] 7: Move disk 1 from A to C
- A:[], B:[], C:[3, 2, 1]
- */
- import java.util.Stack;
-
- public class TowerOfHanoi
- {
- static Stack stackA = new Stack<>(); // 柱A
- static Stack stackB = new Stack<>(); // 柱B
- static Stack stackC = new Stack<>(); // 柱C
- static int nDisks = 5; // Number of disks 盤數
- static int count = 0; // 步數
- static boolean printGoal = false; // 列印目標否
- static boolean printOperation = true; // 列印步驟否
- static boolean printStack = false; // 列印模擬呼叫堆疊否
- // 印n格空白
- public static void printSpaces(int n)
- {
- for(int i=0; i <= n -1; i++) System.out.print(" ");
- }
-
- // 印柱A,柱B,柱C堆疊,前面n層內縮
- public static void printStacks(int n)
- {
- StringBuilder sb = new StringBuilder();
- sb.append("A:" + stackA);
- sb.append(", B:" + stackB);
- sb.append(", C:" + stackC);
- System.out.println();
- printSpaces(n*8); // 每層內縮8格
- System.out.print(sb.toString());
- }
-
- // 搬移柱from頂一個盤子到柱to
- public static void transfer(char from, char to)
- {
- if(from=='A' && to=='B') stackB.push(stackA.pop());
- if(from=='A' && to=='C') stackC.push(stackA.pop());
- if(from=='B' && to=='A') stackA.push(stackB.pop());
- if(from=='B' && to=='C') stackC.push(stackB.pop());
- if(from=='C' && to=='A') stackA.push(stackC.pop());
- if(from=='C' && to=='B') stackB.push(stackC.pop());
- }
-
- // 遞迴版解河內塔，將n個盤子從柱sourc，搬到柱target，透過柱auxiliary
- public static void solveHanoi(int n, char source, char auxiliary, char target)
- {
- if(printGoal)
- {
- System.out.println();
- printSpaces((nDisks - n)*8);
- System.out.print(String.format("hanoi(n:%d,s:%c -> t:%c)",n,source,target));
- }
- if (n == 1)
- {
- if(printOperation)
- System.out.print(String.format("\t\t%d: Move disk 1 from %c to %c", ++count, source, target));
- transfer(source, target);
- }
- else
- {
- solveHanoi(n - 1, source, target, auxiliary);
- printStacks(nDisks - n);
- if(printOperation)
- System.out.print(String.format("\t\t%d: Move disk %d from %c to %c", ++count, n, source, target));
- transfer(source, target);
- printStacks(nDisks - n);
- solveHanoi(n - 1, auxiliary, source, target);
- }
- }
- // 模擬呼叫記錄
- static class HanoiCallRecord
- {
- int num;
- char source;
- char auxiliary;
- char target;
- int stage; // 0 for moving n-1 disks from source to auxiliary rods;
- // 1 for moving the disk n from source to target rods
- // and moving n-1 disks from auxiliary to target rods
- // 2 for backtracking to the previous call record
-
- // 建構子
- public HanoiCallRecord(int num, char source, char auxiliary, char target)
- {
- this.num = num;
- this.source = source;
- this.auxiliary = auxiliary;
- this.target = target;
- this.stage = 0; // 預設從階段0開始
- }
-
- // 列印呼叫記錄
- public String toString()
- {
- return String.format("(n:%d,s:%c,a:%c,t:%c,s:%d)",
- num, source, auxiliary, target, stage);
- }
- }
-
- // 模擬呼叫堆疊，解河內塔，將n個盤子從柱sourc，搬到柱target，透過柱auxiliary
- public static void hanoiUsingStacks(int num, char src, char aux, char tgt)
- {
- Stack stack = new Stack<>();
-
- HanoiCallRecord initial = new HanoiCallRecord(num, src, aux, tgt);
- stack.push(initial); // 壓入第1層呼叫記錄
- while (stack.isEmpty()==false)
- {
- if(printStack) System.out.print("\n" + stack);
-
- HanoiCallRecord current = stack.peek(); // 檢視本層呼叫記錄
- int n = current.num;
- char source = current.source;
- char auxiliary = current.auxiliary;
- char target = current.target;
- int stage = current.stage;
-
- if (n == 1) // 執行特別任務，然後退回上一層任務
- {
- if(printOperation)
- System.out.print(String.format("\t\t%d: Move disk 1 from %c to %c", ++count, source, target));
- transfer(source, target);
- stack.pop(); // 彈出本層呼叫記錄,
- }
- else if(stage == 0) // 階段0, 執行本層第0階段任務
- {
- // solveHanoi(n - 1, source, target, auxiliary);
- HanoiCallRecord next = new HanoiCallRecord(n - 1, source, target, auxiliary);
- stack.push(next); // 壓入下層呼叫記錄
- current.stage++; // 更新本層呼叫記錄的階段欄位
- }
- else if(stage == 1) // 階段1, 執行本層第1階段任務
- {
- printStacks(nDisks - n);
- if(printOperation)
- System.out.print(String.format("\t\t%d: Move disk %d from %c to %c", ++count, n, source, target));
- transfer(source, target);
- printStacks(nDisks - n);
- // solveHanoi(n - 1, auxiliary, source, target);
- HanoiCallRecord next = new HanoiCallRecord(n - 1, auxiliary, source, target);
- stack.push(next); // 壓入下層呼叫記錄
- current.stage++; // 更新本層呼叫記錄的階段欄位
- }
- else if(current.stage == 2) // 階段2,本層任務完成,退回上一層任務
- {
- stack.pop(); // 彈出本層呼叫記錄,
- }
- }
- }
- // 測試主程式
- public static void main(String[] args)
- {
- nDisks = 3; // Number of disks
- count = 0;
- for(int i=nDisks; i >= 1; i--) stackA.push(i);
-
- System.out.print("Hanoi Tower by Implicit Call Stack 遞迴版");
- printStacks(0);
- solveHanoi(nDisks, 'A', 'B', 'C');
- printStacks(0);
-
- // ===================================
-
- count = 0;
- stackA.clear();
- stackB.clear();
- stackC.clear();
- for(int i=nDisks; i >= 1; i--) stackA.push(i);
-
- System.out.print("\n\nHanoi Tower by Explicit Stack 模擬呼叫堆疊版");
-
- printStacks(0);
- hanoiUsingStacks(nDisks, 'A', 'B', 'C');
- printStacks(0);
- }
- }