6月 21, 2008

【演算】河內塔 - Tower of Hanoi

@
  河內塔問題(Tower of Hanoi)是由法國數學家盧卡斯(Édouard Lucas)引進的數學謎題:在 3 根桿子中,有 1 桿上有 N 個從下數起由大而小的穿孔圓盤。在每次只能移動一個圓盤,且大盤不能疊在小盤之上的規則之下,你需要以最少的次數將這 N 個圓盤全部移到另一根桿子上。




  這個遊戲乍看起來有點複雜,其實解法相當簡單(為了方便起見,我們分別將三根桿子標記成 A, B, C,且都是將圓盤由 A 桿移向 C 桿)。

  假設現在 A 桿上有 1 個圓盤,則直接將之移到 C 桿上。若是有 A 桿上有兩個圓盤,則先將第 1 個(最小的)圓盤移到 B 桿上,再將 A 桿剩下的第 2 個圓盤移到 C 桿上,最後將剛剛移到 B 桿上的第 1 個圓盤移到 C 桿第 2 個圓盤之上即可。


  若是 3 個圓盤的情況呢?這時我們需要先忽略第 3 個圓盤,先把前 2 個圓盤以上述的方式移到 B 桿,再將第 3 個圓桿移到 C 桿之後,最後將 B 桿上的 2 個圓盤循同樣的方式移到 C 桿第 3 個圓盤之上即可。

  所以同樣的,若是 4 個圓盤,就將前 3 層以一樣的方式移到 B 桿,再將第 4 個圓盤移到 C 桿上,最後再把 B 桿上的圓盤全部移到 C 桿上。

  至於更多圓盤的情況,其實也都是運用這種規律解開。以下是 3 層與 4 層河內塔的最少移動解法圖例:






  而這種河內塔解法,其實就類似程式的遞迴(recursion)

  怎麼說呢?假設現在你需要將一個 N 層河內塔由 A 桿移到 C 桿。依照上面的解法,我們需要先將前 N - 1 層的圓盤先移到 B 桿,再將第 N 層的圓盤移到 C 桿,最後將 B 桿上的圓盤全部移到 C 桿。

  而要怎麼將前 N - 1 層的圓盤由 A 桿移到 B 桿呢?也是運用同樣的方式:將前 N - 2 層的圓盤先移到 A 桿,再將第 N 層的圓盤移到 B 桿,最後將 A 桿上的圓盤全部移到 B 桿。

  就這樣下去,直到變成最簡易的移動 1 層圓盤為止。也就是說,遞迴的終止條件為移動的圓盤數 n = 1。


  以下是解河內塔謎題的虛擬碼:

void Hanoi(Index n, char A, char B, char C)
{
    if (n = 1)
    {
        print "將第" n "個圓盤由" A "移到" C;
    }
    else
    {
        Hanoi(n - 1, A, C, B);
        print "將第" n "個圓盤由" A "移到" C;
        Hanoi(n - 1, B, A, C);
    }
}


  最後,附上 C 語言的程式實作:

#include <stdio.h>
#include <stdlib.h>

void hanoi(int, char, char, char);

int time = 0;

int main(void)
{
    int n;

    printf("請輸入河內塔的高度:");
    scanf("%d", &n);

    hanoi(n, 'A', 'B', 'C');

    printf("移動 %d 層河內塔共需移動 %d 次\n", n, time);

    system("pause");
}

void hanoi(int n, char A, char B, char C)
{
    if (n == 1)
    {
        printf("%d: 將第 %d 個圓盤由 %c 移到 %c\n", ++time, n, A, C);
    }
    else
    {
        hanoi(n - 1, A, C, B);
        printf("%d: 將第 %d 個圓盤由 %c 移到 %c\n", ++time, n, A, C);
        hanoi(n - 1, B, A, C);
    }
}


  小小的補充一下,假如用以上的程式去試看看,可以發現 N 層河內塔的最小移動次數恰好是 2n - 1。

0 回覆:

張貼留言