【数据结构与算法】汉诺塔问题（C++）
目录
汉诺塔（Hanoi Tower）是经典的递归算法入门问题，源于古印度的数学传说，其核心是通过有限次移动，将一根柱子上的所有圆盘按 “小圆盘在上、大圆盘在下” 的规则移到另一根柱子，且移动过程中始终遵守 “一次仅移一个圆盘、大圆盘不能压小圆盘” 的规则。本文将从问题原理出发，详细讲解汉诺塔的递归实现（核心思路，简洁优雅）和非递归实现（基于栈模拟，深入理解递归本质），并提供完整可运行的 C++ 代码，附详细注释和测试案例。一文带你搞懂汉诺塔问题。
一、汉诺塔问题基础定义
1. 问题描述
有 3 根柱子（记为 A、B、C）和 n 个大小不同的圆盘，初始时所有圆盘按从小到大的顺序叠在 A 柱（源柱），要求将所有圆盘移到 C 柱（目标柱），B 柱作为辅助柱，移动过程需满足：
- 每次只能移动最顶端的一个圆盘；
- 移动过程中，任意一根柱子上的圆盘都必须保持小圆盘在上、大圆盘在下；
- 仅能在 3 根柱子之间移动圆盘。
2. 核心规律
对于 n 个圆盘的汉诺塔问题，最少移动次数为 2n−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 个圆盘的移动问题。
1.首先n=n时，把A杆上的圆盘分为1与n-1两部分
2.因为要把n-1那一部分放到B杆，1那一部分放到C杆，所以，将A杆作为初始杆，B杆作为目标杆，C杆作为中介杆，进行递归。
3.当前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(int i=1;i<=3;i++){//循环移动判断三个杆 if(!a[i].empty()){//如果不为空 if(a[i].top()==1){//且最上面是最小的盘 if(i==3)next=1;//若是最后一个杆，它的下一个杆是A杆 else next=i+1;//否则正常i+1是下一个 move(i,next);//当前杆的盘移动到下一个杆 break; } } } if(a[2].size()==n||a[3].size()==n)break;//如果都在一个杆上了就完成了，判断a[2]与a[3]因为奇数的目标杆是2号杆，偶数的目标杆是3号杆 int other1,other2; switch(next){//对剩下的两个杆进行第二步操作 case 1:{//如果此次对1号杆进行了操作 other1=2;//剩下两个杆就是2号3号杆 other2=3; break; } case 2:{//依次类推 other1=3; other2=1; break; } case 3:{ other1=1; other2=2; break; } } if(a[other1].empty())move(other2,other1);//如果other1为空，那它是最小的一个杆，将other2移动到other1 else if(a[other2].empty())move(other1,other2);//如果other2为空，那它是最小的一个杆，将other1移动到other2 else{ if(a[other1].top()<a[other2].top())move(other1,other2);//否则判断大小，将小的移动到大的杆上 else move(other2,other1); } } } 四、写在最后
本文的 C++ 非递归实现基于栈递归的核心思想，结合 C++ 面向对象和标准库的优势，实现了内存安全、无栈溢出、高效率、易维护的汉诺塔解法，相比 C 语言版和 C++ 递归版更适合实际工程应用。
通过学习该实现，不仅能掌握汉诺塔的非递归解法，更能理解递归的本质（系统栈的自动调用）和递归转非递归的通用方法（自定义栈模拟状态），这一思路可推广到所有递归问题（如二叉树遍历、深度优先搜索 DFS、归并排序等）的 C++ 非递归实现中。
执笔至此，感触彼多，全文将至，落笔为终。
