- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
汉诺塔算法的分析与设计.doc
汉诺塔算法的分析与设计
摘 要: 为了提升学生的编程能力,从解决计算机科学和应用中经典的汉诺塔问题入手,分析了分治算法与递归算法的关系,分别给出了分治算法、递归算法的设计步骤,给出了分治法的时间复杂度计算公式和求解方法。深入分析了汉诺塔问题的简化过程、分解步骤,设计了汉诺塔算法,给出了完成汉诺塔搬迁需要移动盘子次数的计算公式和求解方法。使学生能够把所学的方法用于解决具体问题,并对算法进行比较分析,从而将理论和实际应用切实结合起来。
关键词: 汉诺塔; 时间复杂度; 递归方法; 分治算法
中图分类号:TP302 文献标志码:A 文章编号:1006-8228(2015)08-49-03
Analysis and design of Hanoi tower algorithm
Ma Jianzhe
(School of Information Engineering, Taiyuan University of Technology, Taiyuan, Shanxi 030024, China)
Abstract: In order to improve the students ability of programming, starting with the classic Hanoi tower problem in computer science and application, this paper analyzes the relationship between the divide-and-conquer algorithm and the recursive algorithm, gives the design steps of the divide-and-conquer algorithm and the recursive algorithm respectively, gives the calculation formula and the solving method of the time complexity for the divide-and-conquer algorithm, deeply analyzes the simplification process and the decomposition steps of Hanoi tower problem, designs the algorithm for Hanoi tower problem, and gives the calculation formula and the solving method to work out the number of movements required to complete relocation of Hanoi tower. Student can use the method learnt to solve the specific problems, thereby combine theory with practical application.
Key words: Hanoi tower; time complexity; recursive method; divide-and-conquer algorithm
0 引言
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小,解题所需的计算时间往往也越少,计算也越容易。要解决一个较大的问题,有时是相当困难的。分治策略是应用最多的一种有效方法,它的基本思想是将问题分解成若干个子问题,然后求解子问题。子问题较原问题无疑是会容易些,由此得出原问题的解,就是所谓的“分而治之”的意思。分治策略还可以递归,即子问题仍然可以用分治策略来处理,最后的问题非常基本而且简单[1-2]。
分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。找出各部分的解,然后把各部分的解组合成整个问题的解。实现算法的同时,需要估计算法所需时间。分治算法在每一层递归上分为三个步骤。
⑴ 分:将原问题分解成一系列子问题。
⑵ 治:递归地解各子问题,若子问题足够小,则直接解之。
⑶ 合:将子问题的结果合并成原问题的解。
分治算法的时间由解决各个子问题所需的时间(由子问题的个数、解决每个子问题的时间决定)确定。
由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出
您可能关注的文档
- 水利施工中滑模技术的应用价值研究.doc
- 水利施工中碾压混凝土施工技术研究.doc
- 水利施工中软土地基的处理技术分析.doc
- 水利施工技术在应用中存在的问题和相应的.doc
- 水利施工管理体制模式的构建与应用研究.doc
- 水利普查数据处理研究.doc
- 水利机电设备安装工程常见问题.doc
- 水利枢纽工程项目分标和管理方式分析与阐述.doc
- 水利水库施工质量影响因素及改进措施分析.doc
- 水利水库施工质量控制中的常见问题及处理对策.doc
- “共和国勋章”获得者张富清事迹作文7篇(精选).docx
- “学海导航”中学语文课堂教学设计.docx
- “我和我的家乡”征文范本7篇(精选).docx
- 《木兰诗》翻译及原文.docx
- 湖南省衡阳市衡阳县长宁金山区2025届高三数学上学期12月联考试题文含解析.doc
- 2024年高考生物二轮复习核心考点专项突破人体的稳态与免疫调节练习含解析.docx
- 2024_2025学年高中数学第一章统计1.3统计图表学案含解析北师大版必修3.doc
- 二年级语文下册课文311我是一只小虫子教案新人教版.doc
- 2024_2025学年新教材高中历史第二单元中古时期的世界第4课中古时期的亚洲习题含解析新人教版必修中外历史纲要下.docx
- 2024_2025学年新教材高中地理第4章地球上水的运动与能量交换第2节世界洋流的分布与影响课后练习含解析中图版选择性必修1.doc
文档评论(0)