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

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

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.