Hanoi塔问题非递归算法的形式推导

The Formal Derivation of a Nonrecursive Algorithm for the Tower-of-Hanoi Puzzle

本文从Hanoi塔本身的简要说明出发,深刻剖析了该问题的递归解法,揭示了其本质特性,形式化地找出了圆盘的移动规律,从而推导出一种全新的、逻辑结构非常清晰的、与递归解在圆盘移动上完全等效的非递归算法,彻底解决了递归解中由于圆盘数增加使空间用量迅速膨胀而导致的死机问题。

From the simple description of the Tower of Hanoi, the paper first analyses the recursive algorithm for the puzzle profoundly and unveils its essence. Then the paper uses a formal method to find the law of disk moving. In addition, the paper gives a complete new nonrecursive algorithm which has a very clear logical structure and is equavalent to the law. The algorithm completely solves the problem of computer breakdown because of a sharp increase in memory space ocupation the caused by increase of the number of disks.