尧图网站建设 
《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 按鈕即可逐步觀察每一行指令的執行過程cumulativefalsecurInstr12等參數控制了起始停留的指令位置。這種「點開即視覺化」的設計正是《Hello 演算法》「動畫圖解、一鍵運行」理念在程式碼層面的落地。漢諾塔問題問題定義與三條鐵律題目背景如下給定三根柱子A、B、C起始時柱子A上套著n個圓盤從上到下按從小到大排列。任務是把這n個圓盤全部移到柱子C並保持原有順序移動過程中必須遵守三條規則圓盤只能從一根柱子的頂部拿出放入另一根柱子的頂部每次只能移動一個圓盤小圓盤必須時刻位於大圓盤之上。從分治視角我們將「規模為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頂部的兩個圓盤看作一個整體執行三步令B為目標柱、C為緩衝柱將兩個圓盤從A移至B即子問題f(2)將A中剩下的一個圓盤直接從A移至C即子問題f(1)令C為目標柱、A為緩衝柱將兩個圓盤從B移至C即子問題f(2)。本質上問題f(3)被劃分為兩個子問題f(2)與一個子問題f(1)且這些子問題相互獨立、解可以合併——這正是分治Divide and Conquer的典型特徵。推廣到一般情況f(n)的分解策略如下圖所示將n-1個圓盤借助C從A移至B將剩餘 1 個圓盤從A直接移至C將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(fA {A}) print(fB {B}) print(fC {C}) solve_hanota(A, B, C) print(圓盤移動完成後) print(fA {A}) print(fB {B}) print(fC {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使用ListInteger與remove(size()-1)/add()透過靜態方法dfs完成遞迴。C以vectorint的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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 《Hello 演算法》漢諾塔問題分治解法：從 PythonTutor 互動視覺化到多語言程式實作
《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 按鈕即可逐步觀察每一行指令的執行過程cumulativefalsecurInstr12等參數控制了起始停留的指令位置。這種「點開即視覺化」的設計正是《Hello 演算法》「動畫圖解、一鍵運行」理念在程式碼層面的落地。漢諾塔問題問題定義與三條鐵律題目背景如下給定三根柱子A、B、C起始時柱子A上套著n個圓盤從上到下按從小到大排列。任務是把這n個圓盤全部移到柱子C並保持原有順序移動過程中必須遵守三條規則圓盤只能從一根柱子的頂部拿出放入另一根柱子的頂部每次只能移動一個圓盤小圓盤必須時刻位於大圓盤之上。從分治視角我們將「規模為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頂部的兩個圓盤看作一個整體執行三步令B為目標柱、C為緩衝柱將兩個圓盤從A移至B即子問題f(2)將A中剩下的一個圓盤直接從A移至C即子問題f(1)令C為目標柱、A為緩衝柱將兩個圓盤從B移至C即子問題f(2)。本質上問題f(3)被劃分為兩個子問題f(2)與一個子問題f(1)且這些子問題相互獨立、解可以合併——這正是分治Divide and Conquer的典型特徵。推廣到一般情況f(n)的分解策略如下圖所示將n-1個圓盤借助C從A移至B將剩餘 1 個圓盤從A直接移至C將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(fA {A}) print(fB {B}) print(fC {C}) solve_hanota(A, B, C) print(圓盤移動完成後) print(fA {A}) print(fB {B}) print(fC {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使用ListInteger與remove(size()-1)/add()透過靜態方法dfs完成遞迴。C以vectorint的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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考