算法詳解--漢諾塔

天涯旅人【】 2013-01-21

展開全文

From Gossip@caterpillar

Algorithm Gossip: 漢諾塔算法詳解

說明

河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)于1883年從泰國帶至法國的，河內為越戰(zhàn)時北越的首都，即現在的胡志明市；1883年法國數學家 Edouard Lucas曾提及這個故事，據說創(chuàng)世紀時Benares有一座波羅教塔，是由三支鉆石棒（Pag）所支撐，開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤（Disc），并命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。

解法

如果柱子標為ABC，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤子，就將B當作輔助柱。

如果盤數超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A->B、A ->C、B->C這三個步驟，而被遮住的部份，其實就是進入程式的遞回處理。

事實上，若有n個盤子，則移動完畢所需之次數為2^n - 1，所以當盤數為64時，則所需次數為：

2⁶⁴- 1 = 18446744073709551615

為5.05390248594782e+16年，也就是約5000世紀，如果對這數字沒什么概念，就假設每秒鐘搬一個盤子好了，也要約5850億年左右。

演算法

Procedure HANOI(n, A, B, C) [
    IF(n == 1) [
        PRINT("Move sheet " n " from " A " to " C);
    ]
    ELSE [
        HANOI(n-1, A, C, B);
        PRINT("Move sheet " n " from " A " to " C);
        HANOI(n-1, B, A, C); 
    ]    
]

實作

#include <stdio.h>

void hanoi(int n, char A, char B, char C) {
    if(n == 1) {
        printf("Move sheet %d from %c to %c\n", n, A, C);
    }
    else {
        hanoi(n-1, A, C, B);
        printf("Move sheet %d from %c to %c\n", n, A, C);
        hanoi(n-1, B, A, C);
    }
}

int main() {
    int n;
    printf("請輸入盤數：");
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Java

import java.io.*;

public class Hanoi {
    public static void main(String args[]) throws IOException {
        int n;
        BufferedReader buf;
        buf = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("請輸入盤數：");
        n = Integer.parseInt(buf.readLine());

        Hanoi hanoi = new Hanoi();
        hanoi.move(n, 'A', 'B', 'C');
    }

    public void move(int n, char a, char b, char c) {
        if(n == 1)
            System.out.println("盤 " + n + " 由 " + a + " 移至 " + c);
        else {
            move(n - 1, a, c, b);
            System.out.println("盤 " + n + " 由 " + a + " 移至 " + c);
            move(n - 1, b, a, c);
        }
    }
}

解釋如下：【From：http://zhidao.baidu.com/question/10992444】

Hanoi塔問題, 算法分析如下，設A上有n個盤子。
如果n=1，則將圓盤從A直接移動到C。
如果n=2，則：
（1）將A上的n-1（等于1）個圓盤移到B上；
（2）再將A上的一個圓盤移到C上；
（3）最后將B上的n-1（等于1）個圓盤移到C上。
如果n=3，則：
A）將A上的n-1（等于2，令其為n`）個圓盤移到B（借助于C），步驟如下：
（1）將A上的n`-1（等于1）個圓盤移到C上。
（2）將A上的一個圓盤移到B。
（3）將C上的n`-1（等于1）個圓盤移到B。
B）將A上的一個圓盤移到C。
C）將B上的n-1（等于2，令其為n`）個圓盤移到C（借助A），步驟如下：
（1）將B上的n`-1（等于1）個圓盤移到A。
（2）將B上的一個盤子移到C。
（3）將A上的n`-1（等于1）個圓盤移到C。到此，完成了三個圓盤的移動過程。

從上面分析可以看出，當n大于等于2時， 移動的過程可分解為三個步驟：第一步 把A上的n-1個圓盤移到B上；第二步 把A上的一個圓盤移到C上；第三步 把B上的n-1個圓盤移到C上；其中第一步和第三步是類同的。 當n=3時，第一步和第三步又分解為類同的三步，即把n`-1個圓盤從一個針移到另一個針上，這里的n`=n-1。