1 / 3
文档名称:

汉诺塔问题非递归算法详解.doc

格式:doc   大小:28KB   页数:3页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

汉诺塔问题非递归算法详解.doc

上传人:mh900965 2018/3/3 文件大小:28 KB

下载得到文件列表

汉诺塔问题非递归算法详解.doc

文档介绍

文档介绍:Make By
思路介绍:
首先,可证明,当盘子的个数为n时,移动的次数应等于2^n - 1。
然后,把三根桩子按一定顺序排成品字型(如:),再把所有的圆盘按至上而下是从小到大的顺序放在桩子A上。
接着,根据圆盘的数量确定桩子的排放顺序:
若n为偶数,按顺时针方向依次摆放;
若n为奇数,按顺时针方向依次摆放。
最后,进行以下步骤即可:
(1)首先,按顺时针方向把圆盘1从现在的桩子移动到下一根桩子,即当n为偶数时,若圆盘1在桩子A,则把它移动到B;若圆盘1在桩子B,则把它移动到C;若圆盘1在桩子C,则把它移动到A。
(2)接着,把另外两根桩子上可以移动的圆盘移动到新的桩子上。
即把非空桩子上的圆盘移动到空桩子上,当两根桩子都非空时,移动较小的圆盘。
(3)重复(1)、(2)操作直至移动次数为2^n - 1。
#include<iostream>
#include<cmath>
using namespace std;
#define Cap 64
class Stake //表示每桩子上的情况
{
public:
Stake(int name,int n)
{
this->name=name;
top=0;
s[top]=n+1;/*假设桩子最底部有第n+1个盘子,即s[0]=n+1,这样方便下面进行操作*/
}
int Top()//获取栈顶元素
{
return s[top];//栈顶
}
int Pop()//出栈
{
return s[top--];
}
void Push(int top)//进栈
{
s[++this->top]=top;
}
void setNext(Stake *p)
{
next=p;
}
Stake *getNext()//获取下一个对象的地址
{
return next;
}
int getName()//获取当前桩子的编号
{
return name;
}
private:
int s[Cap+1];//表示每根桩子放盘子的最大容量
int top,name;
Stake *next;
};
void main()
{
int n;
void hanoi(int,int,int,int);
cout<<"请输入盘子的数量:";
cin>>n;
if(n<1)
cout<<"输入的盘子数量错误!!!"<<endl;
else
{
cout<<"移动"<<n<<"个盘子的步骤如下:"<<endl;
if(n%2)
hanoi(n,1,3,2);
else
hanoi(n,1,2,3);
}
}
void hanoi(const int n,int A,int B,int C)
{
Stake a(A,n),b(B,n),c(C,n);
Stake *p,

最近更新

云南省2018年保育员四级能力考试试题试题(附答.. 12页

2025年度委托招聘合同(含绩效考核) 8页

2025年度夫妻财产约定及子女权益保障协议书 7页

2025年度夫妻共同财产投资与收益分配合同协议.. 8页

2025年度天然气入户安装与用户燃气器具维修服.. 9页

2025年度大数据并购交易合同或协议 9页

2025年度大学生实习实训项目实习实训基地建设.. 9页

2025年度多功能挖机租赁及操作培训合同 9页

2025年度外籍专家技术指导与咨询合同 9页

2025年度外卖平台外卖配送区域外卖小哥培训与.. 9页

2025年度培训服务合作协议:明确离职条件与职.. 8页

2025年度城市物流配送运输服务合同 8页

2025年度城市快送服务外包合作协议书 8页

2025年度城市公园及绿地保洁管理服务协议范本.. 9页

2025年度地质灾害防治资质借用投标合作意向书.. 9页

2025年度土方车辆运输合同(含车辆安全性能检.. 9页

2025年度土地流转服务平台建设合同 9页

2025年度土地储备项目投资中介居间服务协议 8页

2025年度国际安全保卫出国劳务合同 9页

2025年度国家股股权托管与国有企业混合所有制.. 9页

2025年度园林景观园林景观项目后期维护合同 9页

2025年度商铺转让合同协议书:繁华地段商业资.. 8页

2025年度商铺租赁合同到期续租前租赁物使用规.. 8页

2025年度商铺买卖合同协议书:商务中心区商铺.. 8页

2025年四川省拟任县处级领导干部模拟试题第1套.. 38页

《中华人民共和国道路交通安全法》题库题库(3.. 56页

2025年度混凝土搅拌机设计说明书 58页

节后复工复产安全生产培训记录 6页

核电知识竞赛试题及答案 7页

(LARS)评价量表 1页