一、汉诺塔问题基础定义
1. 问题描述
有 3 根柱子（记为 A、B、C）和 n 个大小不同的圆盘，初始时所有圆盘按从小到大的顺序叠在 A 柱（源柱），要求将所有圆盘移到 C 柱（目标柱），B 柱作为辅助柱，移动过程需满足：
- 每次只能移动最顶端的一个圆盘；
- 移动过程中，任意一根柱子上的圆盘都必须保持小圆盘在上、大圆盘在下；
- 仅能在 3 根柱子之间移动圆盘。
2. 核心规律
对于 n 个圆盘的汉诺塔问题，最少移动次数为 2^n - 1：
n=1 时，仅需 1 次移动（A→C） n=2 时，需 3 次移动（A→B、A→C、B→C） n=3 时，需 7 次移动 以此类推，每增加 1 个圆盘，移动次数翻倍加 1
3. 问题分解思想（递归核心）
汉诺塔的核心是分治思想，将 n 个圆盘的复杂问题分解为 3 个简单子问题：
- 将 A 柱上的前 n-1 个圆盘从 A 柱（源）移到 B 柱（辅助），以 C 柱为临时辅助；
- 将 A 柱上剩余的 **第 n 个圆盘（最大圆盘）**从 A 柱移到 C 柱（目标）；
- 将 B 柱上的n-1 个圆盘从 B 柱（源）移到 C 柱（目标），以 A 柱为临时辅助。
当 n=1 时，直接移动即可（递归终止条件），无需再分解。
二、递归实现汉诺塔（简洁优雅，易理解）
递归实现是汉诺塔最直观的写法，完全遵循'分治分解'的思想，代码量极少，核心是通过函数自身调用实现子问题的解决。
1. 递归思路
- 函数参数：
n（待移动的圆盘数）、A（起始盘）、B（中介盘）、C（目标盘）； - 终止条件：当
n == 1时，直接输出从源柱到目标柱的移动步骤，返回； - 递归调用：按'分解思想'依次调用自身，解决 n-1 个圆盘的移动问题。
- 首先 n=n 时，把 A 杆上的圆盘分为 1 与 n-1 两部分。
- 因为要把 n-1 那一部分放到 B 杆，1 那一部分放到 C 杆，所以，将 A 杆作为初始杆，B 杆作为目标杆，C 杆作为中介杆，进行递归。
- 当前 C 杆上有一个，B 杆上 n-1 个，A 杆为空，再次递归，将 B 杆作为起始杆，把 n-1 个放到 C 杆，A 杆作为中介杆。以此类推，不断递归下去。
2. 完整递归代码（带步骤打印）
#include <iostream>
using namespace std;
int n;
void hanoi(char a, char b, char c, int n) {
if (n > 0) {
hanoi(a, c, b, n - 1); // 将 A 盘分为两部分，n-1 与 1，把 n-1 放到 B 盘（修改为目标盘），c 盘作为中介盘
cout << n << " from: " << a << " to " << c << endl;
hanoi(b, a, c, n - 1); // 将 B 盘中的 n-1 作为起始盘移动到目标盘 C
// 不断递归
}
}
int main() {
cin >> n;
char a = 'A'; // A 盘
char b = 'B'; // B 盘
char c = 'C'; // C 盘
hanoi(a, b, c, n); // 将 A 作为起始盘，B 作为中介盘，C 作为目标盘，n 为移动目标数量
return 0;
}
三、非递归实现汉诺塔
递归的本质是'系统栈自动处理调用过程'，因此非递归实现的核心是栈系统实现递归栈，手动维护汉诺塔的移动状态（待移动的圆盘数、源柱、辅助柱、目标柱）。
非递归思路
一位美国学者发现：所有的汉诺塔移动可以总结为重复的两步。我们假设现在最小的圆盘在 A 杆上，杆为 A，B，C：
- 第一步：将最小圆盘移动到下一个杆上；
- 第二步：对剩下两个杆的顶上元素进行判断，把较小的那个圆盘移动到较大的那个圆盘上（如果有空杆则移在空杆上）。
重复上述两步就可以得到答案。
注意：这样得到的最后的答案不一定是摞在 C 杆上，如果 N 是奇数则将摞在 B 上。所以如果 N 是奇数我们把杆的摆放顺序设置为 A、C、B，这样就能保证盘子是从 A 杆全部移动到 C 杆。
1. 非递归思路
- 定义栈结构，初始化 A 盘，从大到小排序好；
- 判断 n 的奇偶性，做出对应的转化；
- 按照第一步：将最小圆盘移动到下一个杆上；第二步：对剩下两个杆的顶上元素进行判断，把较小的那个圆盘移动到较大的那个圆盘上（如果有空杆则移在空杆上）进行循环操作；
- 循环直至栈 B 或栈 C 全满，所有圆盘移动完成。
2. 代码实现
#include <iostream>
#include <stack>
using namespace std;
int n;
char s[5] = {'0', 'A', 'B', 'C'}; // 杆 A、B、C 名称
stack<int> a[5]; // 栈实现杆的存储
void move(int now, int next) {
a[next].push(a[now].top());
printf("%d from %c to %c\n", a[now].top(), s[now], s[next]); // 输出移动的起始目标
a[now].pop();
}
int main() {
cin >> n;
int count = 0;
for (int i = 0; i < n; i++) a[1].push(n - i); // 从大到小初始化 A 杆
if (n % 2 == 1) { // 如果是奇数个圆盘交换 B 盘与 C 盘的功能
s[2] = 'C';
s[3] = 'B';
}
while (1) {
int next;
for ( i = ; i <= ; i++) {
(!a[i].()) {
(a[i].() == ) {
(i == ) next = ;
next = i + ;
(i, next);
;
}
}
}
(a[].() == n || a[].() == n) ;
other1, other2;
(next) {
: {
other1 = ;
other2 = ;
;
}
: {
other1 = ;
other2 = ;
;
}
: {
other1 = ;
other2 = ;
;
}
}
(a[other1].()) (other2, other1);
(a[other2].()) (other1, other2);
{
(a[other1].() < a[other2].()) (other1, other2);
(other2, other1);
}
}
;
}
