资源描述：
《二级建造师《机电工程管理与实务》押题密卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Hanoi问题的非递归算法分析第6卷第2期20O6年6月兰州石化职业技术学院JournalofI.~OUPetrochemicalCollegeofTechnologyVo1.6No.2Jun.,20O6文章编号:1671—4067(2006)02—0038—03Hanoi问题的非递归算法分析孙泽宇,丁国强,舒云星(洛阳工业高等专科学校计算机系,河南洛阳471003)摘要:Hanoi(汉诺)塔问题作为一个古典的数学问题,一直以来都是数据结构中递归算法的经典案例,在对汉诺塔问题递归算法进行研究与分析后,提出一种占据内存更少,速度更快
2、且实现简单的非递归算法.关键词:汉诺塔;递归;非递归;时闻复杂性中图分类号:0141.3文献标识码:A主.在对递推算法和递归算法的研究与分析后,提O引言出了一种非递归算法.汉诺塔示意图如图1所示.长期以来,解决汉诺塔问题都是以递归算法为A1汉诺塔非递归算法思想BC图1Hanoi塔问题示意图1.1应考虑的四个问题对于在编写汉诺塔问题非递归算法时,应考虑到四个问题uJ:1)在每次移动一个盘的过程中尽可能移动直径大的盘,即两盘均可移动时优先移动直径大的盘.2)不允许将刚移到某针上的盘立即移回去,即不允许来回移动一个盘.3)直径最小的盘只
3、能从A针移到B针;由B针移到C针;由C针移到A针.4)保证小直径的盘一定在大直径的盘之上.'收稿日期:2O06—04—12作者简介:孙泽宇(1977一),男,吉林长春人,助教;舒云星(1962一),男,江苏南通人,教授.博士.在非递归算法中第1)条是为汉诺塔提供了结束的条件.第2)条是防止机器出现死循环.第3)条则把有序的C针变成了周而复始的C针,且每次只能移动一个确定的盘子.1.2解决问题的方案(1)设有N个盘子按照规则从第1针移动到第3针所需要的最少操作数为An,则根据汉诺塔的递归性和对称性可知,数列{A.}须满足:A=1时,
4、而当n≥2时有An=2A一1+1,由A=2A一1+1可得A川=2(A+1)这说明数列{A}以2为公比而以A.+1=2为首项的等比数列,所以+=2枣2(n≥1),即A.=2一1(n≥1).所以解决N个盘子的汉诺塔问题至少需要2一1步操作呤】.例如当N=4时,汉诺塔游戏过程如表1所示.孙泽宇,丁国强,舒云星.Hanoi问题的非递归算法分析?39?表1N=4时汉诺塔游戏移动过程表BCABCABCABCABCABCABCABC123(7)ABCABCABCABCABCABCABCAB123(8)2314(14)(15)可见,通过此表的移动
5、过程可以看出,当N=4时,共移动l5步才能完成上述操作.即当N个盘子时共要移动2一1步才能完成N个盘子的操作.2)根据汉诺塔的对称性原理可知处于中心位置的那一步的操作对象是N号盘,前一半操作和后一半操作的操作对象是关于中心对称,因此只要确定出前一半操作的操作对象,那么后一半操作的操作对象也就随之确定了.而前一半操作的操作对象又是解决前N一1个盘子的汉诺塔问题.因此处于这一半的中心位置的那一步的操作对象就应该是N一1号盘,如此继续下去,每一步的操作对象都可以确定下来.3)处于中心位置的那一步的操作对象是N号盘,起点是A针,终点是C针
6、,前一半操作是将前N一1个盘子从A针移到B针的.因此,处于这一半的中心位置的那一步的操作对象是N一1号盘,起点是A针,终点是B;后一半操作是将前N一1个盘子从B针移到C针的.因此,处于这一半的中心位置的那一步的操作对象是N一1号盘,起点是B针,终点是C针.按照这种方式,从中心位置开始,逐渐向两瑞扩展,最终能够确定所有操作步起点和终点.2算法的实现一6利用函数调用法来实现汉诺塔非递归算法voiddele(intm,inta);main(){intn,m=1,i;inta;prinff("pleaseinputthenumberofd
7、isks:");scanf("%d",&n);fl0r(i-2;i<=n;i++)m=m2+1;dele(m,a);m=2m;fl0r(i=1;i<=m;i++,i++)priIltf("%da%d",a[i],a[i+1]);}下面以N=4为例,写出汉诺塔问题非递归算法的完整程序1)上机测试程序#defineN4#defineM16main(){charS[M][3];intk,m,X,j;f0r(k=1;k<=N;k++)//确定移动次数{for(X=1,m=1;m<=k一1;m++)x
8、=x2;S[x][0]=k;S[x][1]='A';//设起点S[x][2]='C';//设终点for(j=1;j<=x一1;j++)lif(s[j][1]=='B')//比较盘大盘小并移盘S[j][1]='C';elseif(s[j][1]
