汉诺塔问题（用栈替代递归）

墨蓝 2022-06-10 13:20 148阅读 0赞

视频地址：[点击打开链接][Link 1] 图片来源：[点击打开链接][Link 2]  
![这里写图片描述][20160606001737172]   
![这里写图片描述][20160606001744813]

![这里写图片描述][20160606001752785]

#include<iostream>
    using namespace std;
    void Hanoi(int n,char src,char mid,char dest)//将src座的n个盘子，以mid为中转，移动到dest座
    {
    	if(n==1)//只需移动一个盘子 
    	{
    		cout<<src<<"->"<<dest<<endl;//直接将盘子从src移动到dest即可
    		return ;//递归终止 
    	}
    	Hanoi(n-1,src,dest,mid);//如果有多个盘子，先将src上的前n-1个盘子移动到mid
    	cout<<src<<"->"<<dest<<endl;//再将src上剩余的最后一个盘子移动到dest上
    	Hanoi(n-1,mid,src,dest);//最后将mid上的n-1个盘子移动到dest上
    	return ; 
    } 
    int main()
    {
    	char a,b,c;
    	int n;
    	cin>>n;//输入需要移动的盘子数
    	cin>>a>>b>>c;//3个杆的编号 
    	Hanoi(n,a,b,c);
    	return 0; 
    }

汉诺塔问题非递归解法（栈）

#include<iostream>
    #include<stack>
    using namespace std;
    struct Problem{
    	int n;
    	char src,mid,dest;
    	Problem(int nn,char s,char m,char d):n(nn),src(s),mid(m),dest(d){ }
    }; //一个Problem变量代表一个子问题，将src上的n个盘子以mid为中介移动到dest上
    stack<Problem> stk;//用来模拟信封堆的栈，一个元素代表一个信封
                       //若有n个盘子，则栈的高度不超过n*3
    int main()
    {
    	int n;
    	cin>>n;
    	stk.push(Problem(n,'a','b','c'));//初始化第一个信封
    	while(!stk.empty())//只要还有信封就继续处理 
    	{
    		Problem curPrb=stk.top();//取最上面的一个信封，即当前问题
    		stk.pop();//丢弃最上面的信封
    		if(curPrb.n==1) cout<<curPrb.src<<"->"<<curPrb.dest<<endl;
    		else//分解为子问题，后进栈的先解决 
    		{
    			stk.push(Problem(curPrb.n-1,curPrb.mid,curPrb.src,curPrb.dest));
    			stk.push(Problem(1,curPrb.src,curPrb.mid,curPrb.dest));
    			stk.push(Problem(curPrb.n-1,curPrb.src,curPrb.dest,curPrb.mid)); 
    		} 
    	} 
    	return 0;
    }

汉诺塔问题移动次数（递归）

#include<iostream>
    using namespace std;
    int f(int n)//n个盘子的移动次数
    {
    	if(n==1) return 1;//递归终止条件；
    	else return 2*f(n-1)+1;
    } 
    int main()
    {
    	int n;
    	cin>>n;
    	cout<<f(n)<<endl;
    	return 0;
    }

[Link 1]: https://www.bilibili.com/
[Link 2]: http://blog.csdn.net/nnnnnnnnnnnny/article/details/51592686
[20160606001737172]: /images/20220610/8d15b0aea0564ac68fa3a14e10c08607.png
[20160606001744813]: /images/20220610/d3cc143f12a443689114843e5831388e.png
[20160606001752785]: /images/20220610/047be4bcb7084dafa90bcf785fa184fb.png