反覆運算式與遞迴式河內塔演算法之間的根本差異,在於它們管理狀態的方式:遞迴方法是將整個謎題拆解成較小的子問題,讓子問題自行呼叫本身來求解;反覆運算式則是透過迴圈和一組確定性的規則來移動盤片,而無需維護呼叫堆疊。兩種方法最終都需要相同的最少移動次數才能解開這個經典的三柱謎題,其計算公式為 2^n - 1,其中 n 代表盤片的總數。例如,三片盤子的遊戲恰好需要 7 步,四片盤子的遊戲需要 15 步,五片盤子的遊戲則需要 31 步。電腦科學家經常比較這兩種典範來研究空間複雜度,因為遞迴解法會產生 O(n) 的堆疊深度,而反覆運算式版本則可在 O(1) 的輔助空間下執行。不論選擇哪種演算法,要達到絕對的數學最少步數,合法的盤片移動順序仍然完全相同。親手練習這些序列,有助於建立對兩種演算法方式的直覺理解。親自嘗試這個謎題,您就能視覺化地理解呼叫堆疊是如何對應到實體移動的。
河內塔的演算法典範
遞迴演算法經常因其數學上的優雅與簡潔而備受推崇。它仰賴數學歸納法的原理來解開這個謎題。若要使用輔助柱,將 n 片盤子從來源柱移到目標柱,遞迴函式會執行三個概念上的步驟。首先,它會以遞迴方式將頂端的 n-1 片盤子從來源柱移到輔助柱。其次,它會將最大的一片盤子直接從來源柱移到目標柱。第三,它再以遞迴方式將那 n-1 片盤子從輔助柱移到目標柱。這個優雅的定義是電腦科學中的經典教學工具,例如在 Stony Brook University — Recursion and Towers of Hanoi 指南中便有記載。
相較之下,反覆運算式演算法並不仰賴自我引用的函式。它改用一個會持續執行到謎題解開為止的迴圈。對於三柱的謎題,反覆運算式方法可以使用簡單、確定性的規則來執行。如果盤子總數為偶數,演算法會依序在 A 柱與 B 柱之間、A 柱與 C 柱之間,以及 B 柱與 C 柱之間輪流移動。如果盤子數為奇數,柱配對的順序則改為 A 與 C、A 與 B,最後是 B 與 C。在每一步中,只執行指定柱配對之間唯一合法的移動。這種方法完全避免了呼叫堆疊的額外負擔,在記憶體使用上極為有效率。
數學證明與最少步數
解開河內塔所需的最少步數是一個嚴格的數學事實。如 NIST Dictionary of Algorithms and Data Structures — Towers of Hanoi 所定義的,這個遞迴關係式是絕對的。在三個柱子上,n 片盤子最少步數的一般公式為 2 的 n 次方減 1。
為了理解這個規模是如何增長的,讓我們看看一到八片盤子的具體期望數值。下表列出了這些經數學驗證的最少步數:
| 盤片數量 (n) | 數學公式 | 驗證後的最少步數 |
|---|---|---|
| 1 | 2^1 - 1 | 1 |
| 2 | 2^2 - 1 | 3 |
| 3 | 2^3 - 1 | 7 |
| 4 | 2^4 - 1 | 15 |
| 5 | 2^5 - 1 | 31 |
| 6 | 2^6 - 1 | 63 |
| 7 | 2^7 - 1 | 127 |
| 8 | 2^8 - 1 | 255 |
讓我們以一個使用該公式的具體演算範例來說明。假設您正在玩一局恰好有五片盤子的遊戲。若要找出將整個盤堆移到目標柱所需的合法最少步數,您可以將 n = 5 代入公式:
步數 = 2^5 - 1
步數 = 32 - 1 = 31
這顯示出五片盤子的設定恰好需要 31 步。任何偏離或回溯都會使步數增加,但在經典規則下,要在更少的步數內完成搬移在物理上是辦不到的。
反覆運算式與遞迴式執行的比較
在分析這兩種方法時,開發者會考量多項標準,包括時間複雜度、輔助空間複雜度,以及人類可讀性。在分析不同策略時,追蹤巢狀步驟所帶來的認知負荷,類似於比較不同的記憶力任務,例如 Corsi block test vs digit span。雖然遞迴方法在撰寫與理解上都容易得多,但由於使用中的呼叫堆疊,它對系統記憶體的需求也較高。
| 指標 / 特性 | 遞迴方法 | 反覆運算式方法 |
|---|---|---|
| 時間複雜度 | O(2^n) | O(2^n) |
| 空間複雜度 | O(n),來自呼叫堆疊 | O(1) 輔助空間 |
| 實作風格 | 自我呼叫的函式 | 條件式迴圈 |
| 人類理解度 | 高(非常直覺) | 低(需要追蹤狀態) |
兩種演算法擁有相同的指數時間複雜度,因為解開謎題所需的實體步數以相同的速率增長。然而,在堆疊記憶體極為有限的系統中,反覆運算式方法特別受到青睞,因為在這些系統中,深度遞迴可能會觸發堆疊溢位。
如何在線上解開河內塔
理解這些執行路徑差異的最佳方式,就是親自練習這個序列。您可以直接在瀏覽器中暢玩經典的 Tower of Hanoi 遊戲。這個互動版本會強制執行所有合法移動、追蹤您的進度,並讓您將自己的表現與數學上的最少步數進行比較。
- 選擇三、四或五片盤子,查看顯示的最少步數,然後開始解題。
- 選擇來源柱以取起其頂端盤片,然後選擇一個為空或頂端盤片較大的目的地;按鍵 1–3 也使用相同的操作路徑。
- 將整個盤堆移到目標柱,並且只將您的移動次數與該盤片數量下經驗證的謎題最少步數進行比較。
這個線上版本中可選擇的範圍最多只到五片盤子,如此一來,完整的人工瀏覽器路線仍保持實用性,讓玩家得以證明這個遊戲確實可以獲勝,而不至於變得枯燥乏味。如果您執行了不合法的移動,遊戲會立即拒絕該擺放動作並保留目前的盤面狀態,使其成為一個安全的沙盒,可用來測試反覆運算式與遞迴式兩種心智模型。
遊戲規則、計分與無障礙設計
這個瀏覽器版本的謎題被設計得高度無障礙且透明。盤堆從來源柱開始,最大的盤片在最底部,最小的盤片在最頂端。您的目標是將整個盤堆移到目標柱。一次只能移動一片頂端盤片,且絕對不能將較大的盤片放在較小的盤片之上。若要執行移動,您需選擇一根至少有一片盤子的柱子,然後選擇一個目的地柱。第一次的選擇只會選取頂端盤片,且不會增加移動計數。再次選擇同一根柱子會取消選取,而選擇一個空的來源柱時,系統會提示沒有盤片可取。若目的地的頂端盤片較小,遊戲會拒絕該擺放動作,保留所有柱子狀態與移動計數,並維持原本的來源柱選取狀態,讓您能重新選擇合法的目的地。
本遊戲設有一套休閒性質的計分系統。達到驗證後的最少步數可獲得 1,000 分。每多一步合法移動會扣減 20 分,最低分數為 100 分。這些分數僅作為娛樂用途的產品規則,並非對規劃能力的臨床評分。這純粹是一項娛樂練習,而非臨床、IQ 或認知能力的評量。它不會診斷規劃能力,也不會衡量智力。移動次數不具有任何健康、教育或專業上的解讀意義。請將本頁面視為一個透明的謎題,用來欣賞演算法的數學之美。
在無障礙設計方面,介面採用三個有標籤的原生按鈕,而非拖放操作。這使得移動模型可供鍵盤、觸控、指標、縮放及輔助科技的使用者操作。盤片的寬度為視覺呈現,但每片盤片同時也具備文字標籤。柱名、盤片數量、選取狀態、移動次數、最少步數、拒絕回饋以及最終結果,皆可在不依賴顏色的情況下取得。此外,內建一個雙 Escape 老闆鍵畫面,用於在關閉前阻擋隱藏的柱子變更與重置動作;而一個簡單的重置按鈕則可隨時讓您回到預設的三片盤子設定。
若想進一步深入了解,請參閱 Digital vs Paper Trail Making: A Browser Version Compared。