汉诺塔实现(非递归)
教材上对汉诺塔的问题的编程手段大都以递归方式实现,代码通常比较简洁,一目了然。其实不用递归也有不用的优势。很多递归程序在改为迭代或stack之后,代码加长了,但空间复杂度也有一定程度的降低——至少递归调用需要在内存中开辟的函数指针省下来了。思考过一段时间,发现汉诺塔的递归版经过改写,也可以用栈解决。还是那个特点,代码长一些,空间开支小一些。(没有实际测试,但感觉应该小一些)
#include<iostream>
#include<stack>
using namespace std;
struct status
{
char from;//来源
char idle;//中转站
char to;//去向
int num;//当前要移动的个数
};
void Move(char a,char b,char c,int n)//b为中转站,从a移动n个盘子到c
{
stack<status> s;
status pre,mid,rear;
status current={a,b,c,n};
s.push(current);
while(!s.empty())
{
current=s.top();s.pop();
if(current.num==1)
cout<<"从"<<current.from<<"柱移一个到"<<current.to<<"柱。\n";
else/*将弹出的元素分解为三个元素*/
{
/*对pre赋值*/
pre.from=current.from;
pre.idle=current.to;
pre.to=current.idle;
pre.num=current.num-1;
/*对mid赋值*/
mid.from=current.from;
mid.idle=current.idle;
mid.to=current.to;
mid.num=1;
/*对rear赋值*/
rear.from=current.idle;
rear.idle=current.from;
rear.to=current.to;
rear.num=current.num-1;
/*入栈*/
s.push(rear);s.push(mid);s.push(pre);
}
}
}
int main()
{
Move('A','B','C',8);
return 0;
}