c/c++蓝桥杯经典编程题100道（19）汉诺塔问题

汉诺塔问题

->返回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个盘子到dst hanoi(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到dst StackFrame 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道-目录