c++ 汉诺塔递归代码 c++汉诺塔算法图解_石家庄创泽智能科技有限公司

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-12-06

浏览次数：次

返回列表

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

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

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

汉诺塔问题描述

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

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

C++ 递归实现代码

#include <iostream>
using namespace std;
<p>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 个从辅助柱移到目标柱
}</p><p>int main() {
int n;
cout << "输入盘子数量：";
cin >> n;
hanoi(n, 'A', 'C', 'B');
return 0;
}</p>

输出示例（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

Moshi Chat

法国AI实验室Kyutai推出的端到端实时多模态AI语音模型，具备听、说、看的能力，不仅可以实时收听，还能进行自然对话。

160 查看详情 Moshi Chat

此时 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