APP下载

汉诺塔算法的分析与设计

2015-05-30马健喆

计算机时代 2015年8期

马健喆

摘 要: 为了提升学生的编程能力,从解决计算机科学和应用中经典的汉诺塔问题入手,分析了分治算法与递归算法的关系,分别给出了分治算法、递归算法的设计步骤,给出了分治法的时间复杂度计算公式和求解方法。深入分析了汉诺塔问题的简化过程、分解步骤,设计了汉诺塔算法,给出了完成汉诺塔搬迁需要移动盘子次数的计算公式和求解方法。使学生能够把所学的方法用于解决具体问题,并对算法进行比较分析,从而将理论和实际应用切实结合起来。

关键词: 汉诺塔; 时间复杂度; 递归方法; 分治算法

中图分类号: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个规模较小的子问题,这些子问题互相独立且与原问题相同。找出各部分的解,然后把各部分的解组合成整个问题的解。实现算法的同时,需要估计算法所需时间。……

登录APP查看全文