自底向上记录式Hanoi塔非递归算法  

Non-Recursive Algorithm Based on Down-Up Record Method for Hanoi Tower

作　　者：戴莉萍[1] 黄龙军[1] 刘清华[1] 

机构地区：[1]江西师范大学软件学院,南昌330022

出　　处：《实验科学与技术》2016年第1期51-54,81,共5页Experiment Science and Technology

基　　金：江西省自然科学基金项目(20132BAB201031)

摘　　要：Hanoi塔问题的经典递归算法虽然代码量小,但时间复杂度却是指数级的,而且难以理解。该文基于Hanoi塔问题的递归思想,构造出Hanoi塔的树模型,仔细分析递归函数的调用参数和语句执行时盘子移动的顺序,巧妙地找到两者之间的对应关系,从而提出一种新的自底向上非递归算法。该算法逐一地记录下n从1开始时盘子从源柱到目标柱时经历过的移动轨迹,进而直接应用到n+1个盘子的移动问题。实验结果表明,该算法对应的代码易读且高效,时间复杂度降为O(n),是对Hanoi塔问题的非递归算法研究的进一步实践与探讨。The code of classical recursion algorithm for Hanoi tower problem is simple,but the time complexity is O（2-n） and the code is difficult to understand.Understanding recursive idea of Hanoi tower problem and constructing a tree model based on the function,two objectives of the function＇s parameters and the execution result are analyzed carefully.Then the relationship between them is obtained and used to design a new down-up non-recursive algorithm.This algorithm here records the moving paths of n plates（ n =1,2,…）,which could be applied to get the moving result of n ＋ 1 plates directly.The experimental results show that the corresponding code is very easy to read,and its time complexity is only O（ n）,which is further practice and study for the non-recursive research of Hanoi tower problem.

关 键 词：HANOI塔问题 自底向上记录式 非递归算法 目标柱 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]