汉诺塔非递归算法研究

汉诺塔(Tower of Hanoi)问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).

NON-RECURSIVE ALGORITHMS FOR TOWER OF HANOI

Tower of Honoi problem as a classical instance of recursive programming was proved easy to overflow when run the algorithm with its time complexity lower limit being O(2n) and space complexity being O(n).Two non-recursive algorithms are discussed in this paper,they are Iterative Method and Tree Method of solution sets.Iterative Method was introduced just for the eduction of Tree Method because of its unpractical usage due to too large of its space complexity at O(2n),the same as its time complexity.Tree Met...