Hanoi Tower 問題

場景：

• • 有 1 座金塔，由 8 層『由小至大』，『由上而下』擺放的金碟所組成，簡稱為 S 塔。

  • 另有 2 座金塔欲放地，分別簡稱為：T 塔與 B 塔，3 塔間彼此距離相等，成等邊三角形狀。

  • 祭司依神諭指示，要將 S 塔上金碟，移至 T 塔，移動過程中可暫用 B 塔位置，且小金碟必須置於大金碟之上。

  • 移動一次金碟，需要 1 天。

問題：

• • 要如何移動金碟？

  • 需要多久才能移動完畢？

想法：

• • 三金塔角色可為：(1) 被移動者，(2) 目的者，及 (3) 暫放者。

  • 當要移動的金碟為 1 時，自被移動者金塔取出，放至於目的金塔上。

  • 當要移動的金碟 N > 1 時：

    • 自 S 塔移動 N-1 個金碟至 B 塔，並使用 T 塔為暫放區。

    • 自 S 塔移動 1 個金碟至 T 金塔，並使用 B 塔為暫放區。

    • 自 B 塔移動 N-1 個金碟至 T 金塔，並使用 S 塔為暫放區。

分析：

程式列表：

package com.Emprogria; import java.util.Stack; public class HanoiTower { private Stack<Integer> sourceHanoiTower = null; private Stack<Integer> targetHanoiTower = null; private Stack<Integer> bufferHanoiTower = null; private int totalMove = 0; public HanoiTower() { this.sourceHanoiTower = new Stack<Integer>(); this.targetHanoiTower = new Stack<Integer>(); this.bufferHanoiTower = new Stack<Integer>(); } public void initiateHanoiTower(int numberOfDisk) { this.sourceHanoiTower.clear(); this.targetHanoiTower.clear(); this.bufferHanoiTower.clear(); this.totalMove = 0; for (int i = 0; i < numberOfDisk; i++) { this.sourceHanoiTower.push(i + 1); } } public void showHanoiTower(int typeOfTower) { switch (typeOfTower) { case 1: System.out.print("Source:\n"); for (int i = 0; i < this.sourceHanoiTower.size(); i++) { System.out.printf("\t%d ", this.sourceHanoiTower.get(i)); } System.out.print("\n"); break; case 2: System.out.print("Target:\n"); for (int i = 0; i < this.targetHanoiTower.size(); i++) { System.out.printf("\t%d ", this.targetHanoiTower.get(i)); } System.out.print("\n"); break; case 3: System.out.print("Buffer:\n"); for (int i = 0; i < this.bufferHanoiTower.size(); i++) { System.out.printf("\t%d ", this.bufferHanoiTower.get(i)); } System.out.print("\n"); break; } } public void moveHanoiTower() { moveHanoiTower(this.sourceHanoiTower,

this.targetHanoiTower, this.bufferHanoiTower, this.sourceHanoiTower.size()); } public void moveHanoiTower(Stack<Integer> source, Stack<Integer> target,

Stack<Integer> buffer, int numOfDisk) { if (numOfDisk == 1) { target.push(source.pop()); } else { moveHanoiTower(source, buffer, target, numOfDisk - 1); moveHanoiTower(source, target, buffer, 1); moveHanoiTower(buffer, target, source, numOfDisk - 1); } this.totalMove++; } public int getTotalMovesOfHanoiTower() { return this.totalMove; } /** * @param args the command line arguments */ public static void main(String[] args) { HanoiTower myHanoiTower = new HanoiTower(); int numberOfDisk = 8; if (args.length > 1) { try { numberOfDisk = Integer.parseInt(args[1]); } catch (Exception e) { System.err.print(e.fillInStackTrace()); } } myHanoiTower.initiateHanoiTower(numberOfDisk); myHanoiTower.showHanoiTower(1); myHanoiTower.moveHanoiTower(); myHanoiTower.showHanoiTower(1); myHanoiTower.showHanoiTower(2); System.out.printf("Total: %d\n", myHanoiTower.getTotalMovesOfHanoiTower()); } }