一、汉诺塔问题基础定义
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 << << a << << c << endl;
(b, a, c, n - );
}
}
{
cin >> n;
a = ;
b = ;
c = ;
(a, b, c, n);
;
}
