【演算】河內塔 - 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 層河內塔的最小移動次數恰好是 2ⁿ - 1。