首頁‎ > ‎演算法‎ > ‎

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 塔為暫放區。

分析

金碟數 3 4 5 6 7 8 16
32
日數 10 22 46 94 190 382 98,302
2,147,483,646
在有生之年
都無法移動完畢

程式列表

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()); } }
ċ
HanoiTower.java
(3k)
李智,
2012年7月29日 上午12:42