汉诺塔算法的分析与设计

《汉诺塔算法的分析与设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、汉诺塔算法的分析与设计摘要：为了提升学生的编程能力，从解决计算机科学和应用中经典的汉诺塔问题入手，分析了分治算法与递归算法的关系，分别给出了分治算法、递归算法的设计步骤，给出了分治法的时间复杂度计算公式和求解方法。深入分析了汉诺塔问题的简化过程、分解步骤，设计了汉诺塔算法，给出了完成汉诺塔搬迁需要移动盘子次数的计算公式和求解方法。使学生能够把所学的方法用于解决具体问题，并对算法进行比较分析，从而将理论和实际应用切实结合起来。关键词：汉诺塔；时间复杂度；递归方法；分治算法中图分类号：TP302文献标志码：A文章编号：1006-8228(2015)08-49-03An

2、alysisanddesignofHanoitoweralgorithmMaJianzhe(SchoolofInformationEngineering，TaiyuanUniversityofTechnology，Taiyuan，Shanxi030024，China)Abstract：Inordertoimprovethestudents1abilityofprogramming,startingwiththeclassicHanoitowerproblemincomputerscienceandapplication，thispaperanalyzesthere

3、lationshipbetweenthedivide-and-conqueralgorithmandtherecursivealgorithm,givesthedesignstepsofthedivide-and-conqueralgorithmandtherecursivealgorithmrespectively，givesthecalculationformulaandthesolvingmethodofthetimecomplexityforthedivide-and-conqueralgorithm，deeplyanalyzesthesimplifica

4、tionprocessandthedecompositionstepsofHanoitowerproblem，designsthealgorithmforHanoitowerproblem,andgivesthecalculationformulaandthesolvingmethodtoworkoutthenumberofmovementsrequiredtocompleterelocationofHanoitower.Studentcanusethemethodlearnttosolvethespecificproblems，therebycombinethe

5、orywithpracticalapplication.Keywords：Hanoitower；timecomplexity；recursivemethod；divide-and-conqueralgorithm0引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解题所需的计算时间往往也越少，计算也越容易。要解决一个较大的问题，有时是相当困难的。分治策略是应用最多的一种有效方法，它的基本思想是将问题分解成若干个子问题，然后求解子问题。子问题较原问题无疑是会容易些，由此得出原问题的解，就是所谓的“分而治之”的意思。分治策略还可以递归，即子

6、问题仍然可以用分治策略来处理，最后的问题非常基本而且简单［1-2］。分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。实现算法的同时，需要估计算法所需时间。分治算法在每一层递归上分为三个步骤。⑴分：将原问题分解成一系列子问题。⑵治：递归地解各子问题，若子问题足够小，则直接解之。⑶合：将子问题的结果合并成原问题的解。分治算法的时间由解决各个子问题所需的时间（由子问题的个数、解决每个子问题的时间决定）确定。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提

7、供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。在C语言中，重复性操作可以通过循环结构或者递归结构完成。递归结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便［3-5］。从递归算法的结构来分析，设计递归算法时，无非要解决两个问题：递归出口和递归体。即要确定何时到达递归出口，何时执行递归体，执行什么样的递归体。递归算法设计的关键是保存每一

8、层的局部变