分享程序员开发的那些事...
更新时间：2022-08-22 08:46:13
3.4 在经典问题汉诺塔中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自底向上从大到小依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时有以下限制：
每次只能移动一个盘子；
盘子只能从柱子顶端滑出移到下一根柱子；
盘子只能叠在比它大的盘子上。
请运用栈，编写程序将所有盘子从第一根柱子移到最后一根柱子上。
使用递归的方法实现如下：
#include<iostream> #include<stack> using namespace std; struct op { int begin; int end; char A; char B; char C; op(int start,int end,int A,int B,int C):begin(start),end(end),A(A),B(B),C(C) {} }; void hanoi(int start,int end,char A,char B,char C) { stack<op> st; op tmp(start,end,A,B,C); st.push(tmp); while(!st.empty()) { tmp=st.top(); st.pop(); if(tmp.begin!=tmp.end) { st.push(op(tmp.begin,tmp.end-1,tmp.B,tmp.A,tmp.C)); st.push(op(tmp.end,tmp.end,tmp.A,tmp.B,tmp.C)); st.push(op(tmp.begin,tmp.end-1,tmp.A,tmp.C,tmp.B)); } else cout<<"move "<<tmp.begin<<" from "<<tmp.A<<" to "<<tmp.C<<endl; } } int main() { hanoi(1,6,'A','B','C'); }
汉诺塔的递归解法讲完了，可是这并不是题目要求的。题目要求用栈来解决这个问题。 递归解法其实也是用到了栈的，在每次递归调用自己的时候， 将中间的状态参数压入栈中。不过这些操作都是系统隐式进行的， 所以你不用去关心它具体是怎么压栈出栈的。如果我们要用栈自己来实现这个过程， 就不得不考虑这其中的细节了。
接下来，我们就显式地用栈来实现递归过程中，这些状态参数的压栈出栈过程。首先， 我们需要定义一个数据结构来保存操作过程中的参数。
struct op{ int begin, end; char src, bri, dst; op(){ } op(int pbegin, int pend, int psrc, int pbri, int pdst):begin(pbegin), end(pend), src(psrc), bri(pbri), dst(pdst){ } };
其中的5个参数表示，在柱子src上有一叠圆盘，标号从begin到end， 要将它们从src移动到dst，中间可借助柱子bri。end其实相当于递归解法中的n， src，bri，dst与递归解法中的对应。那为什么还要定义begin这个变量呢？ 为了判断柱子上是否只剩下一个盘子。如果begin等于end， 说明柱子上只剩下“最后”一个圆盘，可以进行移动。当然了， 用另外一个布尔变量来表示是否只剩下一个圆盘也是可以的，效果一样。 讲递归方法的时候，说到从初始状态到最终状态一共要经过以下几个状态：
(1~n, 0, 0) (n, 1~n-1, 0) (0, 1~n-1, n) (0, 0, 1~n)
这些过程我们现在需要自己压栈出栈处理。压栈的时候不做处理，出栈时进行处理。因此， 压栈的时候需要与实际要操作的步骤相反。一开始，我们将最终想要完成的任务压栈。 听起来怪怪的，其实就是往栈中压入一组参数：
stack<op> st; st.push(op(1, n, src, bri, dst));
这组参数表示，柱子src上有1~n个圆盘，要把它移动到dst上，可以借助柱子bri。 当栈st不为空时，不断地出栈，当begin和end不相等时，进行三个push操作 (对应上面四个状态，相邻状态对应一个push操作，使状态变化)， push与实际操作顺序相反(因为出栈时才进行处理，出栈时顺序就正确了)， 如果，begin与end相等，则剩下当前问题规模下的“最后”一个圆盘，直接打印移动方案， hanoi代码如下：
C++实现代码：
#include<iostream> #include<stack> using namespace std; struct op { int begin; int end; char A; char B; char C; op(int start,int end,int A,int B,int C):begin(start),end(end),A(A),B(B),C(C) {} }; void hanoi(int start,int end,char A,char B,char C) { stack<op> st; op tmp(start,end,A,B,C); st.push(tmp); while(!st.empty()) { tmp=st.top(); st.pop(); if(tmp.begin!=tmp.end) { st.push(op(tmp.begin,tmp.end-1,tmp.B,tmp.A,tmp.C)); st.push(op(tmp.end,tmp.end,tmp.A,tmp.B,tmp.C)); st.push(op(tmp.begin,tmp.end-1,tmp.A,tmp.C,tmp.B)); } else cout<<"move "<<tmp.begin<<" from "<<tmp.A<<" to "<<tmp.C<<endl; } } int main() { hanoi(1,5,'A','B','C'); }
运行结果：