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

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

作　　者：宁爱兵[1] 黄明和[2] 

机构地区：[1]江西师范大学计算机科学技术学院,江西南昌330027 [2]江西师范大学计算中心,江西南昌330027

出　　处：《计算机工程与科学》2003年第3期66-68,共3页Computer Engineering & Science

摘　　要：本文从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.

关 键 词：递归程序设计 HANOI塔问题 非递归算法 堆栈技术 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]