汉诺塔问题的三种实现

《汉诺塔问题的三种实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、//test_project.cpp:定义控制台应用程序的入口点。//汉诺塔问题的//〃递归实现/*#include/zstdafx・h〃#includeusingnamespacestd;intcount=0;//记录移动到了多少步voidMove(intn,charFrom,charTo):voidHannoi(intn,charFrom,charPass,charTo)://把圆盘从From,经过pass,移动到Tointmain(){intn_count=0:cout«，z请输入圆盘个数:";cin>>n_count;Ha

2、nnoi(n_count,'A','B','C');}voidMove(intn,charFrom,charTo)count++;cout〈〈〃第〃〈〈count〈〈〃步：〃〈〈〃将第〃〈〈n〈〈〃个圆盘从z/«From«，z移动到/z«To«endl;}voidHannoi(intn,charFrom,charPass,charTo){if(n=l)Move(l,From,To);//哈哈，注意这里的From,已经不等于第一次调用Hannoi的from了,好好体会else{Hannoi(n-1,From,To,Pass);Move(n,From,T

3、o);Hannoi(nT,Pass,From,To);}}*/〃非递归实现//非递归实现的算法描述，要通过画图理解/*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放ABC；若n为奇数，按顺时针方向依次摆放ACBo（）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A,则把它移动到B；若圆盘在柱子B,则把它移动到C；若圆盘在柱子C,则把它移动到A。（）接着，把

4、另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯…的。（）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按照移动规则向一个方向移动金片：如阶汉诺塔的移动：A-C,A-B,C->B,A-C,B->A,B->C,A-C汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*//*#include"stdafx.h"#include

5、am>#includeusingnamespacestd;constintMAX二64;//圆盘的个数最多为//表示每根柱子的信息structst{ints[MAX];inttop;charname;intTop()〃取栈顶元素{returns[top];intPop()//出栈{returns[top--];}voidPush(intx)//入栈s[++top]=x;voidMy_Initial(stta[],longn);//给结构数组设置初始值voidHannoi(stta[],longMovcount);intmain(){in

6、tn;cout〈〈〃请输入圆盘个数：〃〈〈endl;cin»n;//输入圆盘的个数stta[3];//三根柱子的信息用数据结构数组存储My_Initial(ta,n);//初始化结构数组longMov_count=pow((double)2,n)-1;//移动的次数为-1Hannoi(ta,Movcount);return0;voidMy_Initial(stta[],longn)ta[O]・name二'A';ta[O].top=n-l;//开始时圆盘从大到小顺序放在柱子A上for(inti=0;i

7、子B,C上开始没有圆盘ta[l]・top二ta[2]・top=0;for(inti=0;i

8、方向把圆盘从现在的柱子移动到下//一根柱子ch=ta[i%3].Pop();ta[(i+l)%3].Push