漢諾塔問題
->返回c/c++藍橋杯經典編程題100道-目錄
目錄
漢諾塔問題
一、題型解釋
二、例題問題描述
三、C語言實現
解法1：遞歸法（難度★）
解法2：迭代法（難度★★★）
四、C++實現
解法1：遞歸法（使用STL容器記錄步驟，難度★☆）
解法2：面向對象封裝（難度★★）
五、總結對比表
六、特殊方法與內置函數補充
1. C語言中的結構體棧
2. C++的?std::vector
3. 漢諾塔數學公式
一、題型解釋
漢諾塔（Tower of Hanoi）是經典的遞歸問題，描述如下：
-
三根柱子：A（起點）、B（輔助）、C（終點）。
-
若干盤子：初始時所有盤子按大小順序疊放在A柱，大的在下，小的在上。
-
目標：將所有盤子從A柱移動到C柱，每次只能移動一個盤子，且任何時候大盤子不能放在小盤子上。
常見題型：
-
基礎問題：計算移動步驟或最少步數（n個盤子需移動?
2^n - 1?次）。 -
多柱擴展：四根或多根柱子的變種問題（如Frame-Stewart算法）。
-
路徑限制：限制某些移動規則（如只能從A→B、B→C、C→A）。
二、例題問題描述
例題1：輸入盤子數?n=3，輸出移動步驟：
A → C
A → B
C → B
A → C
B → A
B → C
A → C例題2：輸入?n=4，輸出最少移動次數?15。
例題3：驗證移動序列?[A→B, A→C, B→C]?是否是?n=2?的有效解（輸出?true）。
三、C語言實現
解法1：遞歸法（難度★）
通俗解釋：
-
將問題分解為三步：
-
將前?
n-1?個盤子從A移動到B（借助C）。 -
將第?
n?個盤子從A移動到C。 -
將?
n-1?個盤子從B移動到C（借助A）。
-
c
#include <stdio.h>// 遞歸函數：將n個盤子從src移動到dst，使用aux作為輔助
void hanoi(int n, char src, char aux, char dst) {if (n == 1) { // 基線條件：只剩一個盤子直接移動printf("%c → %c\n", src, dst);return;}hanoi(n - 1, src, dst, aux); // 將n-1個盤子從src移動到aux（借助dst）printf("%c → %c\n", src, dst); // 移動第n個盤子到dsthanoi(n - 1, aux, src, dst); // 將n-1個盤子從aux移動到dst（借助src）
}int main() {int n = 3;hanoi(n, 'A', 'B', 'C');return 0;
}代碼邏輯：
-
基線條件：當?
n=1?時，直接移動盤子。 -
遞歸分解：
-
第一步：將?
n-1?個盤子從起點移動到輔助柱（遞歸調用）。 -
第二步：移動最大的盤子到目標柱。
-
第三步：將?
n-1?個盤子從輔助柱移動到目標柱（遞歸調用）。
-
-
時間復雜度：O(2^n)，因為每一步分解為兩個子問題。
解法2：迭代法（難度★★★）
通俗解釋：
-
用棧模擬遞歸過程，手動管理每一步的狀態（當前盤子數、源柱、輔助柱、目標柱）。
c
#include <stdio.h>
#include <stdlib.h>// 定義棧結構體，存儲每一步的狀態
typedef struct {int n;char src, aux, dst;
} StackFrame;void hanoiIterative(int n, char src, char aux, char dst) {StackFrame stack[100]; // 假設n不超過100層int top = -1; // 棧頂指針// 初始狀態：移動n個盤子從src到dst，使用aux輔助StackFrame init = {n, src, aux, dst};stack[++top] = init;while (top >= 0) {StackFrame current = stack[top--]; // 彈出當前任務if (current.n == 1) {printf("%c → %c\n", current.src, current.dst);} else {// 分解為三個子任務（注意順序與遞歸相反）// 子任務3：移動n-1個盤子從aux到dst，使用src輔助StackFrame task3 = {current.n - 1, current.aux, current.src, current.dst};stack[++top] = task3;// 子任務2：移動第n個盤子從src到dstStackFrame task2 = {1, current.src, current.aux, current.dst};stack[++top] = task2;// 子任務1：移動n-1個盤子從src到aux，使用dst輔助StackFrame task1 = {current.n - 1, current.src, current.dst, current.aux};stack[++top] = task1;}}
}int main() {hanoiIterative(3, 'A', 'B', 'C');return 0;
}代碼邏輯：
-
棧模擬遞歸：顯式管理待處理的任務（類似遞歸調用棧）。
-
任務分解順序：由于棧是后進先出，子任務需按相反順序入棧。
-
優勢：避免遞歸的棧溢出風險，適合大規模n。
四、C++實現
解法1：遞歸法（使用STL容器記錄步驟，難度★☆）
通俗解釋：
-
使用?
vector?存儲移動步驟，方便后續處理或輸出。
cpp
#include <iostream>
#include <vector>
using namespace std;vector<string> steps; // 存儲移動步驟void hanoi(int n, char src, char aux, char dst) {if (n == 1) {steps.push_back(string(1, src) + " → " + dst);return;}hanoi(n - 1, src, dst, aux);steps.push_back(string(1, src) + " → " + dst);hanoi(n - 1, aux, src, dst);
}int main() {hanoi(3, 'A', 'B', 'C');for (const string& step : steps) {cout << step << endl;}return 0;
}代碼邏輯：
-
與C語言遞歸邏輯相同，但使用?
vector<string>?動態存儲步驟。 -
輸出靈活性：可隨時訪問或修改步驟記錄。
解法2：面向對象封裝（難度★★）
通俗解釋：
-
將漢諾塔問題封裝為類，支持多種操作（如統計步數、驗證步驟）。
cpp
#include <iostream>
#include <vector>
using namespace std;class HanoiSolver {
private:vector<string> steps;void move(int n, char src, char aux, char dst) {if (n == 1) {steps.push_back(string(1, src) + " → " + dst);return;}move(n - 1, src, dst, aux);steps.push_back(string(1, src) + " → " + dst);move(n - 1, aux, src, dst);}
public:void solve(int n) {steps.clear();move(n, 'A', 'B', 'C');}void printSteps() {for (const string& step : steps) {cout << step << endl;}}
};int main() {HanoiSolver solver;solver.solve(3);solver.printSteps();return 0;
}代碼邏輯：
-
封裝性：將步驟記錄和求解邏輯封裝在類中。
-
擴展性：可添加方法統計步數、驗證移動序列等。
五、總結對比表
| 方法 | 時間復雜度 | 空間復雜度 | 優點 | 缺點 |
|---|---|---|---|---|
| 遞歸法 | O(2^n) | O(n) | 代碼簡潔，易理解 | 棧溢出風險 |
| 迭代法 | O(2^n) | O(n) | 避免遞歸棧溢出 | 代碼復雜，需手動管理棧 |
| STL容器記錄 | O(2^n) | O(2^n) | 靈活處理步驟 | 內存占用高 |
| 面向對象封裝 | O(2^n) | O(2^n) | 擴展性強，易于維護 | 代碼稍長 |
六、特殊方法與內置函數補充
1. C語言中的結構體棧
-
作用：手動實現棧結構，存儲遞歸狀態（需注意棧大小限制）。
2. C++的?std::vector
-
動態數組：自動擴展容量，適合存儲不定長的移動步驟。
3. 漢諾塔數學公式
-
最少步數：
2^n - 1，可通過位運算快速計算（如?(1 << n) - 1）。
->返回c/c++藍橋杯經典編程題100道-目錄
?
)
