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柱，每次只能移动一个盘子，且任何时候大盘子不能放在小盘子上。

常见题型：

1. 基础问题：计算移动步骤或最少步数（n个盘子需移动 2^n - 1 次）。

2. 多柱扩展：四根或多根柱子的变种问题（如Frame-Stewart算法）。

3. 路径限制：限制某些移动规则（如只能从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：递归法（难度★）

通俗解释：

• 将问题分解为三步：

  1. 将前 n-1 个盘子从A移动到B（借助C）。

  2. 将第 n 个盘子从A移动到C。

  3. 将 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;
}

代码逻辑：

1. 基线条件：当 n=1 时，直接移动盘子。

2. 递归分解：

   • 第一步：将 n-1 个盘子从起点移动到辅助柱（递归调用）。

   • 第二步：移动最大的盘子到目标柱。

   • 第三步：将 n-1 个盘子从辅助柱移动到目标柱（递归调用）。

3. 时间复杂度：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;
}

代码逻辑：

1. 栈模拟递归：显式管理待处理的任务（类似递归调用栈）。

2. 任务分解顺序：由于栈是后进先出，子任务需按相反顺序入栈。

3. 优势：避免递归的栈溢出风险，适合大规模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;
}

代码逻辑：

1. 封装性：将步骤记录和求解逻辑封装在类中。

2. 扩展性：可添加方法统计步数、验证移动序列等。

---

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
递归法	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道-目录