公司网站备案怎么弄,网站建设选择本地,wordpress获取自定义字段的值,基础建设图片汉诺塔问题
-返回c/c蓝桥杯经典编程题100道-目录 目录
汉诺塔问题
一、题型解释
二、例题问题描述
三、C语言实现
解法1#xff1a;递归法#xff08;难度★#xff09;
解法2#xff1a;迭代法#xff08;难度★★★#xff09;
四、C实现
解法1#xff1…汉诺塔问题
-返回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输入盘子数 n3输出移动步骤
A → C
A → B
C → B
A → C
B → A
B → C
A → C
例题2输入 n4输出最少移动次数 15。 例题3验证移动序列 [A→B, A→C, B→C] 是否是 n2 的有效解输出 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借助dstprintf(%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;
}
代码逻辑 基线条件当 n1 时直接移动盘子。 递归分解 第一步将 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;vectorstring 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语言递归逻辑相同但使用 vectorstring 动态存储步骤。 输出灵活性可随时访问或修改步骤记录。 解法2面向对象封装难度★★
通俗解释 将汉诺塔问题封装为类支持多种操作如统计步数、验证步骤。
cpp
#include iostream
#include vector
using namespace std;class HanoiSolver {
private:vectorstring 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道-目录
