c++中如何使用递归解决汉诺塔问题_c++递归汉诺塔方法-C++-PHP中文网

c++中如何使用递归解决汉诺塔问题_c++递归汉诺塔方法

下次还敢

发布： 2025-09-29 15:46:01

原创

644人浏览过

汉诺塔问题通过递归实现分治思想，将n个圆盘从A移动到C：先递归将前n-1个圆盘从A经C移至B，再将第n个圆盘从A移至C，最后递归将n-1个圆盘从B经A移至C；当n=1时直接移动。该过程共需2^n−1步，体现递归函数拆解问题、依赖终止条件的核心机制。

c++中如何使用递归解决汉诺塔问题_c++递归汉诺塔方法

汉诺塔问题是递归思想的经典应用。问题描述为：有三根柱子 A、B、C，A 上从上到下按大小顺序叠放了 n 个圆盘，目标是将所有圆盘移动到 C 柱，过程中每次只能移动一个圆盘，且不能将大盘放在小盘之上。

递归思路解析

解决汉诺塔的关键在于分治思想：

若只有一个圆盘，直接从 A 移动到 C。
若有 n 个圆盘，可以分解为：
- 先将前 n-1 个圆盘从 A 借助 C 移动到 B。
- 再将第 n 个（最大的）圆盘从 A 移动到 C。
- 最后将 n-1 个圆盘从 B 借助 A 移动到 C。

这个过程不断递归，直到只剩一个圆盘。

C++ 实现代码

#include <iostream>
using namespace std;
<p>// 参数说明：
// n: 当前要移动的圆盘数量
// from: 起始柱
// to: 目标柱
// aux: 辅助柱
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
cout << "Move disk 1 from " << from << " to " << to << endl;
return;
}
// 将前 n-1 个盘从 from 移动到 aux（借助 to）
hanoi(n - 1, from, aux, to);</p><pre class='brush:php;toolbar:false;'>// 将第 n 个盘从 from 移动到 to
cout << "Move disk " << n << " from " << from << " to " << to << endl;

// 将 n-1 个盘从 aux 移动到 to（借助 from）
hanoi(n - 1, aux, to, from);

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

塔猫ChatPPT

塔猫官网提供AI一键生成 PPT的智能工具，帮助您快速制作出专业的PPT。塔猫ChatPPT让您的PPT制作更加简单高效。

查看详情

int main() { int n; cout << "Enter number of disks: "; cin >> n; hanoi(n, 'A', 'C', 'B'); // A为起始柱，C为目标柱，B为辅助柱 return 0; }

运行示例

当输入 n = 3 时，输出如下：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

登录后复制

总共需要 2^n - 1 步，即 7 步完成。