c++ 汉诺塔递归代码 c++汉诺塔算法图解

汉诺塔问题通过递归实现，将n个盘子从A移动到C，需借助B辅助。首先将前n-1个盘子从A移到B，再将最大盘从A移到C，最后将n-1个盘子从B移到C。每次移动遵循大盘不压小盘原则。递归终止条件为只剩一个盘子时直接移动。算法体现分治思想，通过不断分解问题规模直至可直接求解。

汉诺塔问题是递归算法的经典例子，通过将问题分解为更小的子问题来解决。下面给出 C++ 实现代码，并附上算法执行过程的图解说明。

汉诺塔问题描述

有三根柱子 A、B、C，A 上有 n 个大小不同的圆盘，按从小到大的顺序叠放（大盘在下）。目标是把所有圆盘从 A 移动到 C，移动过程中遵守以下规则：

一次只能移动一个圆盘
每次移动的是某根柱子最上面的圆盘
大盘不能放在小盘之上

C++ 递归实现代码

#include 
using namespace std;
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
cout << "将盘子 " << n << " 从 " << from << " 移动到 " << to << endl;
return;
}
hanoi(n - 1, from, aux, to);  // 先把上面 n-1 个移到辅助柱
cout << "将盘子 " << n << " 从 " << from << " 移动到 " << to << endl;
hanoi(n - 1, aux, to, from);  // 再把 n-1 个从辅助柱移到目标柱
}
int main() {
int n;
cout << "输入盘子数量：";
cin >> n;
hanoi(n, 'A', 'C', 'B');
return 0;
}

输出示例（n=3）：

将盘子 1 从 A 移动到 C
将盘子 2 从 A 移动到 B
将盘子 1 从 C 移动到 B
将盘子 3 从 A 移动到 C
将盘子 1 从 B 移动到 A
将盘子 2 从 B 移动到 C
将盘子 1 从 A 移动到 C

算法图解与执行逻辑

以 n = 3 为例，三步递归策略如下：

第1步：将前2个盘子从 A → B（借助 C）

把最上面两个盘子看作一个整体，先移到辅助柱 B
这需要递归调用 hanoi(2, A, B, C)

第2步：将最大盘子从 A → C

此时 A 上只剩最大盘（第3个），直接移动到目标柱 C

第3步：将2个盘子从 B → C（借助 A）

递归地把 B 上的两个盘子移到 C，完成最终目标

整个过程体现“分治”思想：要移动 n 层塔，先移上面 n-1 层让路，再移动底层，最后把 n-1 层盖上去。

递归调用结构图（简化表示）

hanoi(3, A→C)
├─ hanoi(2, A→B)
│  ├─ hanoi(1, A→C): A→C
│  ├─ A→B
│  └─ hanoi(1, C→B): C→B
├─ A→C
└─ hanoi(2, B→C)
   ├─ hanoi(1, B→A): B→A
   ├─ B→C
   └─ hanoi(1, A→C): A→C

每层递归都在缩小问题规模，直到只剩一个盘子时直接处理，这是递归终止条件。

基本上就这些。理解关键在于相信递归能处理好 n-1 的情况，你只需专注当前一层的操作逻辑。不复杂但容易忽略细节。

# ai # c++ # ios # stream # 递归 # 算法 # 移到 # 只剩 # 汉诺 # 的是 # 这是 # 放在 # 都在 # 结构图 # 只需

返回目录在线咨询

上一篇：node.js中EJS 模板快速入门教程
下一篇：选择建站高防服务时，哪些功能是应对CC攻击的关键？

您的项目需求