《汉诺塔问题算法分析及C语言实现.pdf》由会员分享，可在线阅读，更多相关《汉诺塔问题算法分析及C语言实现.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、、吣计算机教学与教育信息化本栏目责任编辑：王力汉诺塔问题算法分析及C 语言实现刘军。张志峰(莱芜职业技术学院计算机系，山东莱芜2 7 11 0 0)摘要：文章对“汉诺塔”问题进行了详细的分析，给出了一种实现的算法，并用C 语言实现。通过该问题的c 实现，可使学习者清晰地观测到解决该问题的全过程。关键词：汉诺塔；算法；递归中图分类号：T P 3 1 1文献标识码：A文章编号：1 0 0 9-3 0 4 4(2 0 0 6)1 7-2 1 4 9 6-0 2A l g o r i t h mA n a l y s i sa n dJ a v aR e a l i z a t i o no fB a
2、 n j oI s s u eL I UJ u l l，Z H A N GZ h i f e n g(D e p a r t m e n to fC o m p u t e rS c i e n c e。I a i w uV o c a t i o n a l&T e c h n o l o g yC o l l e g e，L a i w u2 7 11 0 0，C h i n a)A b s t r a c t：T h i st e x tc a r r i e so i ld e t a i l e da n a l y s i sa b o u tH a n i oi s s u ea
3、 n dp r o v i d e so n er e a l i z a t i o no fa l g o r i t h mi np m 舢C R e a l i z i n gt h i si s s u et I l m u g hp r o g r a mC，C a nm a k el e a r n e r so b s e r v ec l e a r l yt h ew h o l ec o u r s ew h i c hs o l v e st h i si s s u e K e yw o r d s：H a n i o；A l g o r i t h m；R e c
4、u r s i v el 问题描述问题提出：有三个塔(分别为A 号，B 号和C 号)。开始时，有n 个圆形盘以从下到上、从大到小的次序叠置在A 塔上。现要将A塔上的所有圆形盘，借助B 搭，全部移动到c 搭上，且仍按照原来的次序叠置。移动的规则：这些圆形盘只能在3 个塔间进行移动，一次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比它小的盘子的上面。要求：从键盘输入初始圆形盘子个数n，用C 语言实现n 个盘子最佳移动的全过程。2 算法分析题目实现的是设计一个盘子移动的方案。使得A 号塔上的所有盘子借助于B 号塔按照原来的次序移动到C 号塔上，并且给出完整的最佳的盘子移动的方案。从实际的、具
5、体的盘子的移动过程来分析，找出问题内在的规律。经分析无论盘子的个数有多少，是1、2、3 或n 个，也不管怎么去移动盘子(当然是按一定规则移动)，但在移动的过程中，将始终会出现这样的状态情况：(驴1)个盘子将会以从下到上、从大到下的次序叠置在B 塔上，这时，A 塔上第n 个盘子就能被轻而易举叠放到c 塔上；接着，我们再把B 塔上的共(n 一1)个盘子移动到C 塔上，问题好像已经解决。但，B 塔上f n 1)个盘子怎么移动到c 塔上呢?这是要解决的第二个问题。同样，不管怎么移动，也将会出现这样的状态情况：(n 一2)个盘子将会以从上到下、从大到小的次序叠置在A 塔上，这时，B 塔上第(n 1)个盘
6、子就能被轻而易举放到c 塔上；接着，把A塔上的共(n 一2)个盘子移动到C 塔上。这样，不断深入，不断细小化。最终。将到达仅有一个盘的情形，这时，递归也就终止了，问题也得到了解决。通过以上分析，这里有很明显递归关系。由此，想到了采用递归算法来解决该问题，因为递归算法有这样特征描述：为了求解出规模为n 的问题的解，我们先设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的方法分解，分解成规模更小的问题。并能从这些更小的问题的结构造出规模稍大问题的解。特别地是，当规模n=l 时，能直接得到解。现在，严格按照递归算法来解决问题。先定义
7、递归方法H a n i o(i n tn,c h l l l-A，c h a rB,c h a rC)，按如下步骤进行解题(设初始盘子个数为N)：若A 塔上仅仅只有一个盘子(n=1)，则直接从A 移动到c，问题完全解决。若A 塔上有一个以上的盘子(n 1)，则需要考虑以下三个步骤。第一步：把(n l 价盘子从A 塔经过移动，叠放到B 塔上。在不违反规则情况下，所有(n 一1)个盘子不能作为一个整体一起移动，而是要符合要求地从一个塔移到另一个塔上。用H a n i o(n l，A，c，B)调用递归方法，注意：这里是借助于c 塔，将(n l 价盘子从A 塔移动到B 塔，A 是源塔，B 是目标塔。第
8、二步：将剩下的第1 1 个盘子(也就是最底下的一个)直接从A 塔叠放到空着的C 塔上。第二三步：用第一步的方法，再次将B 塔七的所有盘子叠放到c 塔上。同样，这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。用H a n i o(n l，B，A，c)调用递归方法，注意：这里是借助于A 塔，将(n 一1 价盘子从B 塔移动到c 塔，B 是源塔，c 是目标塔。这个算法达到了预期的目标。即在C 塔上按正确的次序叠放了所有的圆形盘子。有了前面问题算法分析的基础，继而，可以用c 语言来实现算法。3C 语言实现3 1 说明(1)n 为A 塔初始盘子个数；(2)A 塔上盘子从上到下、从小到大编号
9、依次为l，2，3；(3)H a n i 0 0 方法采用递归算法，实现盘子移动的最佳方案。收稿日期：2 0 0 7-0 4 1 5作者简介：刘军(1 9 8 1-)，莱芜职业技术学院计算机系教师，助教；张志峰(1 9 8 0 一)，幕芜职业技术学院计算机系教师，助教。1 4 母蚺嬲与技木 本栏目责任编辑：王力计算机教学与教育信息化3 2 编程#i n c l u d e v i o dH a n i o(u n s i g n e dn,e h a rA，c h a rC，c h a rB)；i n t i O：v o i dm 且i n 0Iu n s i g n e dn：p r i n
10、f f(”p l e a s e,e n t e rt h en u m b e ro f d i s c：飞s c a n f(”d，&n)；产输入N 值，p r i n f f(”t n e e d l e：t a tb tc、n”)；H a n i o(n，。a，c，吣产从A 上借助B 将N 个盘子移动到c 上，p r i n t f(”、tT o t a l：d、I l”，i)；v o i dH a n i o(u n s i g n e dn,c h a rA，c h a rC，c h a rB)(珥n 堋fH a n i o(n 一1，A，B，C)；严从A 上借助C 将N 一1 个
11、盘子移动到B 上+，+i：s w i t c I I(A)严将A 上的一个盘子移到c 上，fc a s e a l：s w i t c h(C、fc 蛳I b：p r i n f f(”、t【d】：、t 2 d 2 d r I”，i，n，n)；b r e a k；勰C I：p,i n t f(”、t【d】：6 2 d 2 d、I I”，i，I I n)b r e a k；b r e a k；c a s e。b。：w i t c h(C)l勰a g：p r i n f f(”、t【d】：慨2 d 2 d U”，i，n 神；b r e a k；c 眦C I-p r i n f f(”、t【d】：、
12、t 2 d 2 d”，i，n n)；b r e a k；b r e a k；c a 船。c：s w i t c h(C 1c 雠。a：p r i n f f(”、l【d】：、t 2 d 2 d、I l”，i，n，n)；b r e a k；c a s e|b：p r i n f f(M d】：t 2 d 2 d、I I”，i，n 神；b r e a k；b r e a k；H a n i o(n 一1，B，C，A)；产从B 上借助A 将N 1 个盘子移动到C 上，)4 总结：。递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较为复杂的问题(如规模为n)的求解推到比原问题简单一些的问题(规
13、模小于n)的求解，例如上面分析过程中。为求解H a n i o(n，A，B，c)，推到计算H a n i o(n 一1，A，C，B)。在回归阶段，当获得最简单情况的解后，逐级返回，依次获得稍复杂问题的解。在这里的“汉诺塔”问题中。有它的特别的地方，回归的过程当中，还要涉及到递推。另外，在编写递归方法时要注意：每次调用递归方法，方法中的参数只是局限于当前调用层的，当递推进入“简单问题”层时，原来层次上的参数便被隐藏起来。在一系列“简单问题”层它们各有自己的参数。最后，通过经典“汉诺塔”问题移动过程的分析、解决以及最后c 编程实现，使我们能够掌握解决此类问题的方法，也使我们对递归算法能有个更加深刻
14、的理解。参考文献：【1】严蔚敏数据结构(C 语言版)【M】清华大学出版社，2 0 0 7【2】王春森程序员教程【M J 清华大学出版社，2 0 0 1【3】h t t p：b l o g c s d n n e“f i s h e r _ j i a n g c a t e g o r y 1 8 5 5 3 5 a s p x 1 4 h t t p-w w w d i y b|c o n d c o u r s e 3 _ p r o g r a m c c s u a n f a 2 0 0 7 2 1 3 2 1 4 9 9 h t r a l 汉诺塔问题算法分析及C语言实现汉诺塔问题
15、算法分析及C语言实现作者：刘军，张志峰，LIU Jun，ZHANG Zhi-feng作者单位：莱芜职业技术学院,计算机系,山东,莱芜,271100刊名：电脑知识与技术英文刊名：COMPUTER KNOWLEDGE AND TECHNOLOGY年，卷(期)：2008，2(17)引用次数：1次 参考文献(4条)参考文献(4条)1.严蔚敏 数据结构 20072.王春森 程序员教程 20013.查看详情4.查看详情 相似文献(10条)相似文献(10条)1.期刊论文 张宏梅.鲁邦定.ZHANG Hong-mei.LU Bang-ding 汉诺塔问题的算法分析及JAVA实现-电脑知识与技术（学术交流）20
16、07,1(1)本文对经典的汉诺塔问题进行了详细的分析,给出了实现的算法,并用JAVA实现.通过该问题的JAVA实现,可使学习者清晰地观测到解决该问题的全过程.2.期刊论文 陈文.CHEN Wen 汉诺塔非递归算法-电脑编程技巧与维护2009,(14)分析汉诺塔递归算法的特点,由递归算法,结合二叉树的中序遍历算法,提出汉诺塔二叉树的概念及创建方法,并证明汉诺塔二叉树特点.由此进一步导出兼顾时间效率与空间效率的非递归算法.最后,提供实现算法的C语言程序.3.期刊论文 赵东跃.Zhao Dong-yue 汉诺塔非递归算法研究-计算机应用与软件2008,25(5)汉诺塔(Tower of Hanoi)
17、问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).4.期刊论文 李玉华.崔凤云.刘晓庆.LI Yu-hua.CUI Feng-yun.LIU Xiao-qing 汉诺塔问题的层次迭代算
18、法-计算机工程与应用2008,44(35)汉诺(Hanoi)塔是程序算法设计的一个比较经典问题,目前已有大量的相关文献对其进行了研究.为进一步加快汉诺塔问题的求解速度,通过对汉诺塔问题抽象解树的分析,发现其可以划分为不同层次相同结构的子树,通过对子树层次化控制即可迭代出整个问题的解.基于此,提出了一种用已知子树分层次迭代汉诺塔问题的非递归算法.运行时间测试表明,该算法进一步提高了求解的速度.5.期刊论文 朱玲.ZHU Ling 汉诺塔问题非递归算法的实现-农业网络信息2007,(9)汉诺塔问题这一古典的数学问题是一个典型的递归问题,其递归算法由于简洁清晰,为大家所熟悉,编写出来的程序也比较简单
19、.相比之下,大家对汉诺塔问题的非递归算法比较陌生,本文采用JAVA语言编程实现了汉诺塔问题非递归算法.6.期刊论文 周敏 汉诺塔问题的算法分析及C语言实现-电脑学习2009,(5)本文对经典的汉诺塔问题进行了详细的分析,给出了实现的算法,并用C语言实现.通过诙问题的C语言实现,可使学习者清晰地观测到解决该问题的全过程.7.期刊论文 杨楷.徐川 四柱汉诺塔之初步探究-北京大学学报(自然科学版)2004,40(1)1941年,J.S.Frame在上提出了一种解决四柱汉诺塔问题的算法,但未给出最终公式的证明.本文按照这种算法总结出完成四柱汉诺塔游戏之最少步数的公式,并用数学归纳法证明了它.8.期刊论
20、文 肖琳 从汉诺塔问题再谈递归算法-电脑知识与技术（经验技巧）2003,(32)递归(Recursion)是一种有效的算法设计方法.简单地说,递归就是自调用.递归算法就是指包含有调用算法本身语句的算法.这种算法的目的就是用一种普遍的统一的规律来解决步骤繁多的问题.也正因为如此,它是数据结构中一个杀伤力很大的算法,而且其他一些数据结构问题(比如树状结构和链表等)也离不开它.下面笔者就汉诺塔问题的c语言实现来探讨一下如何用数学归纳法思想解决一般递归算法.9.期刊论文 张洪庆.ZHANG Hong-qiang 由汉诺塔游戏想到的汉诺塔简单非递归算法-农业网络信息2008,(6)汉诺塔问题是一个古典的
21、数学问题,也是程序设计中的经典递归问题,其递归算法由于简洁清晰,为大家所熟悉,编写出来的程序也比较简单,缺点是占用太多的内存空间.本文对汉诺塔问题进行了数学建模,并用几个简单的判断条件,对问题迅速求解,程序用C语言实现.10.期刊论文 邱宁.QIU Ning 汉诺塔问题的非递归算法分析-浙江树人大学学报2005,5(2)Hanoi(汉诺)塔问题作为一个古典的数学问题,一直以来都是数据结构中递归算法的经典案例,几乎没有介绍过其他的方法来解决此问题.文章分析讨论了一种非递归算法.引证文献(1条)引证文献(1条)1.卜奎昊.韦相和 扑克牌猜牌魔术及C+实现期刊论文-电脑知识与技术 2009(17)本文链接：http:/