首页 / 算法 / 算法题--汉诺塔问题的递归和非递归解法
算法题--汉诺塔问题的递归和非递归解法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法题--汉诺塔问题的递归和非递归解法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1349字,纯文字阅读大概需要2分钟。
内容图文
![算法题--汉诺塔问题的递归和非递归解法](/upload/InfoBanner/zyjiaocheng/839/052f8288f4ec43a58e7cf1a406aab309.jpg)
讲解传送门 https://www.bilibili.com/video/av10046345/?p=9
老师讲的非常好
//汉诺塔问题
#include <iostream>
#include <stack>
using namespace std;
//递归解法
void Hanoi(int n, char src, char mid, char dest){
//将src上的n个盘子,以mid为中转,转移到dest上
if(n==1){
cout<<src<<"->"<<dest<<endl;
return; //递归终值
}
//先将n-1个盘子从src移动到dest
Hanoi(n-1, src, dest, mid);
cout<<src<<"->"<<dest<<endl;
//最后将n-1个盘子从mid移动到src
Hanoi(n-1, mid, src, dest);
return;
}
//用栈来替代递归
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{ //分解子问题
//先把分解得到的第3个子问题放入栈中
stk.push(Problem(curPrb.n-1, curPrb.mid, curPrb.src, curPrb.dest));
//再把第二个子问题放入栈中
stk.push(Problem(1, curPrb.src, curPrb.mid, curPrb.dest));
//最后放第1个子问题,后放入栈的子问题先被处理
stk.push(Problem(curPrb.n-1, curPrb.src, curPrb.dest, curPrb.mid));
}
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的算法题--汉诺塔问题的递归和非递归解法全部内容,希望文章能够帮你解决算法题--汉诺塔问题的递归和非递归解法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。