摘要訊息 : 一個僧侶完成六十四個金盤的移動, 世界就要毀滅了?

0. 前言

傳說越南河內某間寺院有三根銀棒, 上串 64 個金盤. 寺院裡的僧侶依照一個古老的預言 : 初始, 64 個金盤放置在第一根銀棒上, 僧侶每一次只能移動一個金盤, 要求移動到第三個銀棒上. 僧侶還必須遵守一個規則, 移動過程中金盤必須按照小到大排列, 即大盤不能疊在小盤上面. 預言說當這些盤子移動完畢 (也就是所有第一根銀棒上金盤被移動到第三個銀棒上), 世界就會滅亡.

更新紀錄 :

• 2022 年 4 月 24 日進行第一次更新和修正.

1. 傳說屬實?

假設僧侶每秒鐘可移動一個金盤, 並且 24 小時不間斷, 那麼預計需要 5849 億年才能完成. 而根據現代天文學的理論, 觀測與計算, 目前絕大多數人都認同宇宙現在的年齡介於 137 億年至 138 億年之間. 那麼如果傳說屬實, 到那個時候不要說地球了, 銀河系可能都不存在了... 這個傳說也就沒有人能夠考證了.

2. 移動次數

設移動次數滿足影射 m = \mathop {m}(n), 其中 n 為第一根銀棒上的金盤數量. 那麼顯然, 當 n = 0 的時候不需要移動, 自然也就有 \mathop {m}(0) = 0; 當 n = 1 的時候, 移動一次就可以達到目標, 那麼有 \mathop {m}(1) = 1; 當 n = 2 的時候, 首先要把第一個比較小的金盤移動到第二根銀棒上, 然後把較大的金盤移動到第三根銀棒上, 最後把第二根銀棒上的金盤移動到第三根銀棒上, 總共需要移動 \mathop {m}(2) = 3 次. 上面這三個情況都是比較簡單的, 接下來我們要討論比較複雜的情況, 並且分析為什麼 64 個金盤需要那麼長時間進行移動.

2.1 n = 3

初始時, 三個金盤都被放在了第一根銀棒上.

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

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

為了能夠將最大的金盤移動到第三根銀棒上, 我們移開第三根銀棒上的金盤, 能夠移動的位置只有一個, 就是將第三根銀棒上的金盤移動到第二根銀棒上.

將第一根銀棒上的金盤移動到第三根銀棒上, 最大的金盤就移動到了正確的位置上.

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

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

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

上面是最簡單的移動方式, 總共的移動次數是 \mathop {m}(3) = 7. 儘管只有三個金盤, 但是我們仍然可以總結出一些規律 : 要將最大的那個金盤移動到第三根銀棒上, 我們首先要將第一個金盤和第二個金盤移動到第二根銀棒上. 這樣, 第三個金盤才有機會移動到第三根銀棒上. 從全局的角度來看, 為了把最大的那個金盤移動到第三根銀棒上, 我們必須把最大的金盤上面的所有金盤移動到第二根銀棒上.

2.2 n > 3

現在我們考慮 n > 3 的情形.

通過第 2.1 節最後總結出來的方法, 從全局的角度來看, 為了把最大的金盤移動到第三根銀棒上, 首先要把前 n - 1 個金盤移動到第二根銀棒上.

為了把剩下第二根銀棒上最大的金盤移動到第三根銀棒上, 我們首先要將 n - 2 個金盤移動到第一根銀棒上.

剛才我們都是從全局出發, 但是我們清楚, 若要從第一根銀棒上把 n - 1 個金盤移動到第二根銀棒上 (Figure 2-2), 又或者從第二根銀棒上把前 n - 2 個金盤移動到第一根銀棒上 (Figure 2-3), 都不是一次就能夠完成的.

2.3 原始, 輔助與目標

為了更深刻地理解問題得到最終的解決方案, 我們引入三個概念 : 原始銀棒, 輔助銀棒和目標銀棒. 對於 Figure 2-1 來說, 要想將第 n 個金盤移動到第三根銀棒上, 我們必須把第 n 個金盤上面的 n - 1 個金盤移動到第二根銀棒上, 此時需要借助第三根銀棒作為輔助. 在這種情況下, 第一根銀棒就變成了原始銀棒, 第二根銀棒就變成了目標銀棒, 第三根銀棒變成了輔助銀棒. 然後我們把第二根銀棒上的 n - 1 個金盤移動到第三根銀棒即可, 以第一根銀棒為輔助. 那麼第一根銀棒是輔助銀棒, 第二根銀棒是原始銀棒, 第三根銀棒是目標銀棒. 對於 Figure 2-2 來說, 要把第二根銀棒上的第 n - 1 個金盤移動到第三根銀棒上, 我們必須把第 n - 1 個金盤上面的 n - 2 個金盤移動到第一根銀棒上. 這樣, 原始銀棒是第二根銀棒, 輔助銀棒是第三根銀棒, 目標銀棒是第一根銀棒. 然後我們再把第一根銀棒上面的 n - 2 個金盤移動到第三根銀棒上, 這樣又回到了 Figure 2-1 的情況. 我們不斷這樣交替, 直到原始銀棒上只剩下一個金盤, 那麼此時就可以直接把這個金盤移動到第三根銀棒上.

#include <iostream>

unsigned long long move_count {};
void move(char from, char to) {
    ++move_count;
}
void tower_of_hanoi(int n, char origin = '1', char auxiliary = '2', char target = '3') {
    if(n == 0) {
        return;
    }
    tower_of_hanoi(n - 1, origin, target, auxiliary);       // 把原始銀棒上面的 n - 1 個金盤移動到目標銀棒上
    move(origin, target);       // 把原始銀棒上的金盤移動到目標銀棒上
    tower_of_hanoi(n - 1, auxiliary, target, origin);       // 把第二根上剩下的金盤移動到第三根銀棒上
}
int main(int argc, char *argv[]) {
    tower_of_hanoi(16);
    std::cout << move_count << std::endl;       // 輸出結果 : 65535
}

2.4 再探 n > 3

我們還沒有計算對於任意的 n > 3, \mathop {m}(n) 的計算問題. 從 Code 1 和第 2 節中, 我們可以得到 :

• 當 n = 0 的時候, 移動次數為 0;
• 當 n = 1 的時候, 移動次數只需要一次;
• 當 n > 1 的時候, 移動次數是 2\mathop {m}(n - 1) + 1.

於是, 我們可以得到 \displaystyle {\mathop {m}(n) = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ 2\mathop {m}(n) + 1 & {n > 1}. \end {cases}} 根據《遞迴方程式 – 替代法與歸納法》, 我們可以證明 \displaystyle {\mathop {m}(n) = \begin {cases} 0 & {n = 0} \\ 2^{n} - 1 & {n > 1}. \end {cases}}

恆等式 1. \mathop {m}(n) = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ 2\mathop {m}(n) + 1 & {n > 1} \end {cases} = \begin {cases} 0 & {n = 0} \\ 2^{n} - 1 & {n > 1}. \end {cases}

證明 :

我們使用歸納法進行證明.

當 n = 1 的時候, 有 \mathop {m}(1) = 1 = 2^{1} - 1.

當 n = 2 的時候, 有 \mathop {m}(2) = 2\mathop {m}(1) + 1 = 3 = 2^{2} - 1.

不妨假設當 n < k 時, 都有 \mathop {m}(n) = 2^{n} - 1 成立.

當 n = k 的時候, \displaystyle {\begin {aligned} \mathop {m}(n) &= 2\mathop {m}(n - 1) + 1 \\ &= 2 \left ( 2^{n - 1} - 1 \right ) + 1 \\ &= 2^{n} - 2 + 1 \\ &= 2^{n} - 1. \end {aligned}} 因此, 當 n = k 時, 仍然有 \mathop {m}(n) = 2^{n} - 1.

綜上所述, \mathop {m}(n) = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ 2\mathop {m}(n) + 1 & {n > 1} \end {cases} = \begin {cases} 0 & {n = 0} \\ 2^{n} - 1 & {n > 1} \end {cases} 成立.

\blacksquare

3. 複雜度分析

通過第 2.4 節, 我們已經可以得到解決河內塔問題的時間複雜度為 \Theta(2^{n}). 現在, 我們來分析河內塔問題的空間複雜度. 很顯然, 河內塔問題的遞迴次數和第一根銀棒上的金盤數量 n 有關. 由恆等式 1 可以得到, 遞迴的次數是 2^{n} - 1, 因此河內塔問題的空間複雜度也是 \Theta(2^{n}).

4. 世界毀滅?

按照第 1 節中的設定, 僧侶移動一次金盤的時間為一秒, 那麼完成 64 個金盤的移動需要多少秒呢? 2^{64} - 1 = 18446744073709551615. 換算成年, 便是 5849 億年. 即便是僧侶一秒可以移動兩個金盤, 那世界毀滅會不會也成真?