企业官网建设流程全解析

《Hello 演算法》漢諾塔問題分治解法：從 PythonTutor 互動視覺化到多語言程式實作

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

漢諾塔（Tower of Hanoi）是分治思想最經典的入門問題之一：把n個圓盤從柱子A借助緩衝柱移到目標柱C，看似複雜，卻能被優雅地拆解為兩個規模為n-1的子問題與一個規模為1的基本情況。本篇文章以《Hello 演算法》倉庫中的 pythontutor 互動視覺化檔案 為入口，結合同步收錄於 章節文件 與 Python 原始碼 的完整實作，帶你掌握漢諾塔問題的數學建模、遞迴分解策略、O(2^n)時間複雜度分析，以及如何在 6 種以上程式語言中一鍵執行同一套演算法。

這個檔案是什麼：一鍵互動的 PythonTutor 視覺化入口

在《Hello 演算法》倉庫的zh-hant/codes/pythontutor/目錄下，每個章節都對應一組 Markdown 檔案，它們是互動式演算法視覺化的入口。以chapter_divide_and_conquer/hanota.md為例，其結構非常精簡，卻承載了完整資訊：

<!-- [file]{hanota}-[class]{}-[func]{solve_hanota} -->

這行註解是倉庫的程式碼引用標記：它指明本篇對應的原始碼檔案為hanota（即codes/python/chapter_divide_and_conquer/hanota.py），核心函式為solve_hanota。檔案其餘部分是一個指向 PythonTutor 線上執行環境的長連結，連結的 URL 參數中完整編碼了漢諾塔問題的 Python 原始碼（包含move、dfs、solve_hanota三個函式與 Driver Code），因此打開連結即可直接看到逐步執行的動畫效果，無需在本機配置任何環境。

使用方式很簡單：將該連結貼到瀏覽器開啟，PythonTutor 會載入程式碼；點擊 "Forward" 按鈕即可逐步觀察每一行指令的執行過程，cumulative=false&curInstr=12等參數控制了起始停留的指令位置。這種「點開即視覺化」的設計，正是《Hello 演算法》「動畫圖解、一鍵運行」理念在程式碼層面的落地。

漢諾塔問題：問題定義與三條鐵律

題目背景如下：給定三根柱子A、B、C，起始時柱子A上套著n個圓盤，從上到下按從小到大排列。任務是把這n個圓盤全部移到柱子C，並保持原有順序，移動過程中必須遵守三條規則：

1. 圓盤只能從一根柱子的頂部拿出，放入另一根柱子的頂部；
2. 每次只能移動一個圓盤；
3. 小圓盤必須時刻位於大圓盤之上。

從分治視角，我們將「規模為i的漢諾塔問題」記作f(i)，例如f(3)表示把 3 個圓盤從A移至C。n個圓盤時共需2^n - 1次移動，這正是問題指數複雜度的來源。

分治策略：從基本情況到子問題分解

基本情況f(1)與f(2)

• 對於f(1)（只有一個圓盤）：直接把它從A移到C即可，這是遞迴的終止條件。
• 對於f(2)（兩個圓盤）：由於必須時刻滿足「小圓盤在大圓盤之上」，需要借助B完成三步：先將小圓盤A → B，再將大圓盤A → C，最後將小圓盤B → C。

解決f(2)的過程可總結為「將兩個圓盤借助B從A移至C」，其中C是目標柱、B是緩衝柱。

子問題分解f(3)與一般化f(n)

已知f(1)、f(2)的解後，f(3)可以這樣思考：把A頂部的兩個圓盤看作一個整體，執行三步：

1. 令B為目標柱、C為緩衝柱，將兩個圓盤從A移至B（即子問題f(2)）；
2. 將A中剩下的一個圓盤直接從A移至C（即子問題f(1)）；
3. 令C為目標柱、A為緩衝柱，將兩個圓盤從B移至C（即子問題f(2)）。

本質上，問題f(3)被劃分為兩個子問題f(2)與一個子問題f(1)，且這些子問題相互獨立、解可以合併——這正是分治（Divide and Conquer）的典型特徵。推廣到一般情況，f(n)的分解策略如下圖所示：

1. 將n-1個圓盤借助C從A移至B；
2. 將剩餘 1 個圓盤從A直接移至C；
3. 將n-1個圓盤借助A從B移至C。

兩個子問題f(n-1)再以相同方式遞迴劃分，直至抵達最小子問題f(1)。

程式碼實作：三個函式層層遞進

在 hanota.py 中，演算法由三個函式構成，與上述分解策略一一對應：

def move(src: list[int], tar: list[int]): """移動一個圓盤""" # 從 src 頂部拿出一個圓盤 pan = src.pop() # 將圓盤放入 tar 頂部 tar.append(pan) def dfs(i: int, src: list[int], buf: list[int], tar: list[int]): """求解漢諾塔問題 f(i)""" # 若 src 只剩下一個圓盤，則直接將其移到 tar if i == 1: move(src, tar) return # 子問題 f(i-1) ：將 src 頂部 i-1 個圓盤借助 tar 移到 buf dfs(i - 1, src, tar, buf) # 子問題 f(1) ：將 src 剩餘一個圓盤移到 tar move(src, tar) # 子問題 f(i-1) ：將 buf 頂部 i-1 個圓盤借助 src 移到 tar dfs(i - 1, buf, src, tar) def solve_hanota(A: list[int], B: list[int], C: list[int]): """求解漢諾塔問題""" n = len(A) # 將 A 頂部 n 個圓盤借助 B 移到 C dfs(n, A, B, C)

逐函式解讀：

• move(src, tar)：pop()取出src頂部（列表尾部）的圓盤，append()放入tar頂部，對應「一次移動一個圓盤」的基本操作。
• dfs(i, src, buf, tar)：遞迴主體。注意三根柱子的角色是動態互換的——第一次遞迴呼叫dfs(i-1, src, tar, buf)把原來的tar當作緩衝柱；最後一次呼叫dfs(i-1, buf, src, tar)則把原來的src當作緩衝柱。這是整個演算法最精妙也最容易被忽略的地方：緩衝柱不是固定的B，而是「當前子問題中未被使用的第三根柱子」。
• solve_hanota(A, B, C)：對外入口，取A的圓盤數n並啟動遞迴，將n個圓盤借助B移到C。

Driver Code：可直接複製執行的驗證樣例

"""Driver Code""" if __name__ == "__main__": # 列表尾部是柱子頂部 A = [5, 4, 3, 2, 1] B = [] C = [] print("初始狀態下：") print(f"A = {A}") print(f"B = {B}") print(f"C = {C}") solve_hanota(A, B, C) print("圓盤移動完成後：") print(f"A = {A}") print(f"B = {B}") print(f"C = {C}")

執行後輸出應為：初始時A = [5, 4, 3, 2, 1]、B = []、C = []；求解完成後A = []、B = []、C = [5, 4, 3, 2, 1]。一個重要的實作慣例是**「列表尾部代表柱子頂部」**：圓盤從A的尾部被pop()出、從C的尾部被append()入，因此C最終保持了與初始A完全一致的從小到大的排列順序。在 PythonTutor 中逐步播放這段 Driver Code，可以直觀看到每次move前後三根柱子內容的變化。

複雜度分析：指數時間的代價

漢諾塔問題形成一棵高度為n的遞迴樹，每個節點代表一個子問題，對應一次開啟的dfs()呼叫：

• 時間複雜度為O(2^n)：f(n)被分解為兩個f(n-1)，呼叫次數按指數增長，總移動次數為2^n - 1。
• 空間複雜度為O(n)：遞迴深度最多為n，呼叫棧占用的空間與圓盤數成線性關係，而非指數關係。

正因如此，傳說中「64 個圓盤」的漢諾塔即使每秒移動一次，也需要約2^64 ≈ 1.84 × 10^19秒（約 5850 億年），遠超目前對宇宙年齡的估計——這既是故事的趣味所在，也是指數複雜度的生動警示。

多語言實作對照：同一演算法，多種寫法

《Hello 演算法》將同一份邏輯同步實作於多種程式語言。以漢諾塔為例，倉庫中可直接對照以下實作（資料結構選型因語言而異）：

• Python：用list.pop()/list.append()模擬柱頂操作，最貼近「列表尾部是柱頂」的抽象。
• Java：使用List<Integer>與remove(size()-1)/add()，透過靜態方法dfs完成遞迴。
• C++：以vector<int>的back()/pop_back()/push_back()實現。
• C：最貼近底層，用裸陣列加上srcSize、tarSize兩個指標管理「棧頂」位置，並在移動時將原位置清零。
• Go：採用標準庫container/list雙向鏈結串列，用Back()取棧頂、PushBack()入棧。
• Swift：以inout [Int]參數傳遞引用，用popLast()!/append()完成移動。

對照閱讀可以發現：分治分解的遞迴結構在所有語言中完全一致，差異僅在於容器操作語法——這也體現了《Hello 演算法》「一份演算法思路，多語言平行呈現」的組織方式（倉庫同時提供 Python、Java、C++、C、C#、JS、Go、Swift、Rust、Ruby、Kotlin、TS、Dart 等語言版本）。你可以挑選熟悉的語言，直接運行其 Driver Code 驗證「A清空、C按序填滿」的結果。

小結：從視覺化到實作的分治學習閉環

回顧本篇，漢諾塔問題的完整學習路徑是：先透過 PythonTutor 互動連結 逐步觀察圓盤移動，再對照 章節文件 理解f(n) → f(n-1) + f(1) + f(n-1)的分解骨架，最後在 hanota.py 中確認「三柱角色互換」的遞迴寫法。掌握這三個層次，你便同時理解了分治的「分解—解決—合併」三步驟、遞迴樹與指數複雜度的直觀來源，以及「基本情況是遞迴的錨點」這一貫穿全書的編程要領——這些能力可直接遷移到歸併排序、構建二元樹等其他分治問題的學習中。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo