關鍵點 : 理解原始銀棒、目標銀棒和輔助銀棒的思想
傳說越南河內某間寺院有三根銀棒, 上串 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 個金盤移動到第三根銀棒上. 此時, 原始銀棒已經不再是第一根銀棒了, 而是第二根銀棒, 目標銀棒是第三根銀棒, 作為輔助銀棒的是第一根銀棒
現在又回到了原來的問題, 把第一根銀棒上的前 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
自創文章, 原著 : Jonny. 如若閣下需要轉發, 在已經授權的情況下請註明本文出處 :