河內塔

關鍵點 : 理解原始銀棒、目標銀棒和輔助銀棒的思想

傳說越南河內某間寺院有三根銀棒, 上串 64 個金盤. 寺院裡的僧侶依照一個古老的預言 :

每一次只能移動一個金盤
金盤必須按照小到大排列, 即大盤不能疊在小盤上面
初始, 64 個金盤放置在第一根銀棒上, 要求移動到第三個銀棒上

預言說當這些盤子移動完畢 (也就是所有第一根銀棒上金盤被移動到第三個銀棒上), 世界就會滅亡. 這個問題起源於法國數學家愛德華·盧卡斯

我們首先給出這個問題的答案 : 若傳說屬實, 假設僧侶每秒鐘可移動一個金盤, 並且 24 小時不間斷, 那麼預計需要 5849 億年才能完成. 而根據現代天文學的理論、觀測與計算, 目前絕大多數人認同宇宙現在的年齡介於 137 億年至 138 億年之間

我們首先對於比較簡單的情況進行講解 (設移動次數滿足影射 $m = m(n)$ , 其中 $n$ 為第一根銀棒上的金盤數量) :

1. 第一根銀棒上沒有金盤

對於這種情況, 根本無需移動. 此時移動次數為 0, 即有

$m(0) = 0$

2. 第一根銀棒上僅有一個金盤

當只有一個金盤的時候, 直接將這一個金盤移動到第三根銀棒上即可. 此時移動次數為 1, 即有

$m(1) = 1$

3. 第一根銀棒上有兩個銀盤

將較小的金盤移動到第三根銀棒上

然後只能將第一根銀棒最頂上的金盤移動到第二根銀棒上

如果不走剛才步驟的逆向步驟, 那麼同樣只有一條路可以走, 就是將第三根銀棒上的金盤移動到第二根銀棒上

將第一根銀棒上的金盤移動到第三根銀棒上, 那麼就完成了最後一個金盤的排列

現在有兩個選擇, 一是將第二根銀棒上的金盤移到第三根銀棒上, 二是將第二根銀棒上的金盤移動到第一根銀棒上. 顯然, 如果移動到第三根銀棒上, 那麼為了將第二根銀棒上的金盤移動到第三根銀棒上, 就要將這個金盤重新移動到第一根銀棒上. 因此, 第二根銀棒上的金盤要移動到第一根銀棒上

接下來很顯然, 首先將第二根銀棒上的金盤移動到第三根銀棒上

最後將第一根銀棒上的金盤移動到第三根銀棒上就完成了

可以計算, 總共的移動次數為 7 次, 即

$m(3) = 7$

上述移動方式是最簡的移動方式, 其它移動方式雖然可以成功, 但是移動次數可能會比上述移動方式要大

4. 第一根銀棒上有 n 個金盤

我們不再考慮第一根銀棒上有 4 個金盤、5 個金盤、...、64 個金盤、... 等等的情況. 我們直接考慮第一根銀棒上有 n 個金盤的情況

不難想像, 要想完成這個預言, 必須首先將最大的盤首先移動到第三根銀棒. 而要實現這個, 必須把前 n - 1 個金盤移動到第二根銀棒上才行. 於是, 這裡出現了三個概念 : 原始銀棒、輔助銀棒和目標銀棒. 非常好理解, 現在要把 n 個銀盤移動到第三根銀棒, 就要把第三根銀棒作為目標銀棒, 而因為每一次只能移動一個金盤, 因此要把前 n - 1個銀盤移動到第二根銀棒上面, 也就是把第二根銀棒作為輔助銀棒. 而第一根銀棒就是原始銀棒

Tip : 如果你無法理解, 那麼不要管這裡為什麼直接把 n - 1個金盤作為整體移動, 接著往下看

接下來, 要把 n - 1 個金盤移動到第二根銀棒上, 就要把第二根銀棒作為目標銀棒, 把第三根銀棒作為輔助銀棒

以此類推...

不妨設此時, 第一根銀棒上沒有金盤, 第二根銀棒上是前 n - 1 個金盤, 第三根銀棒上是第 n 個銀盤, 也就是此時有

接下來的任務顯然是把第二根銀棒上的 n - 1 個金盤移動到第三根銀棒上. 但是這無法一次性完成, 需要把第二根銀棒上的前 n - 2 個金盤移動到第一根銀棒上, 然後再將第 n - 1 個金盤移動到第三根銀棒上. 此時, 原始銀棒已經不再是第一根銀棒了, 而是第二根銀棒, 目標銀棒是第三根銀棒, 作為輔助銀棒的是第一根銀棒

</span>

現在又回到了原來的問題, 把第一根銀棒上的前 n - 3 個金盤移動到第三根銀棒上. 這一次的原始銀棒、目標銀棒和輔助銀棒和第一次的一樣

我們重新回到第一次移動, 雖然我們說把前 n - 1 個金盤移動到第二根銀棒上, 但是實際上根據限制, 是沒有辦法一次性進行移動的. 因此, 我們還是使用上面原始銀棒、目標銀棒和輔助銀棒的手法進行移動. 此時, 第三根銀棒變成了輔助銀棒, 目標銀棒是第二根, 借助第三根銀棒, 把第一根銀棒上的金盤移動到第二根銀棒上. 第二根銀棒就作為了目標銀棒

再根據限制, 實際上這 n - 1 個金盤也是沒有辦法一次性移動的, 因此還要再用類似的方法

...

直接剩下最後一個金盤, 不管它位於哪個銀棒上, 只要移動到第三根銀棒上即可

這個思想, 我們稱之為遞迴 (recursion). 在《C++ 學習筆記》中, 我對遞迴僅作了應用, 並未介紹. 簡單地來說, 遞迴就是某一個函式呼叫自己的過程

在給出河內塔的程式碼之前, 我首先簡單介紹一下遞迴. 我們拿費氏數列作為舉例 :

$f(n)= \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f(n - 1) + f(n - 2) & n \geq 2 \end{cases}$

將其寫成 C++ 程式碼, 我們會這樣簡單地去處理 :

int fibonacci(int n) {

    if(n == 0) {

        return 0;

    }else if(n == 1) {

        return 1;

    }

    return fibonacci(n - 1) + fibonacci(n - 2);

}

如果你無法理解遞迴, 你可能需要拿出紙和筆手動會函式進行展開計算. 手動計算一次, 將會加深你的理解. 此處不再展開

對於河內塔, 雖然比較複雜, 但是如果運用遞迴, 那麼程式碼將會非常簡單 :

#include <iostream>



using std::cout;

using std::endl;



auto count {0};

void move(char from, char to) {

    cout << "Move " << from << " to " << to << endl;

    ++count;

}

void hanoi(int n, char X = 'X', char Y = 'Y', char Z = 'Z') {

    if(n == 0) {

        return;

    }

    hanoi(n - 1, X, Y, Z);

    move(X, Z);

    hanoi(n - 1, Y, Z, X);

}

int main(int argc, char *argv[]) {

    hanoi(10);

    cout << count << endl;      //輸出結果 : 1023

}

在上述程式碼中 : 變數 count 用於計算移動次數; 使用 n == 0 作為遞迴結束的標誌; 函式 hanoi 的參數 n 表示金盤個數, X 表示原始銀棒, Y 表示輔助銀棒, Z 表示目標銀棒

如若將引數 10 改為 64, 結果是什麼呢? 將會是長久的遞迴等待, 因為要移動 18446744073709551615 次才行. 而且這個數遠遠地超出了 int 型別可以容納的範圍

這也就解釋了, 為什麼當僧侶完成了移動, 世界末日就到了

我們可以得到, 對於任意給定的 $n$ , $n$ 個金盤的移動次數為

$m(n)=\begin{cases} 0 & {n = 0} \\ 2m(n - 1) - 1 & {n \geq 1} \end{cases} = 2^{n} - 1$