分划递推法在Hanoi塔问题上的应用  

The Application of PAR Method in Solving the Problem of Tower of Hanoi

作　　者：孙凌宇[1] 冷明[2] 

机构地区：[1]井冈山学院计算机科学系,江西吉安343009 [2]上海大学计算机学院,上海200072

出　　处：《广西科学院学报》2006年第4期342-345,351,共5页Journal of Guangxi Academy of Sciences

摘　　要：采用分划递推法通过功能归约变换,形式化推导和证明H ano i塔问题中圆盘的移动规律,从而推导出结构清晰、可读性好、效率高、占用存储空间与圆盘个数无关的非递归算法,算法比较分析地显示出形式化推导在获得高效和正确性的算法程序中的作用.相关算法在UN IX平台下用C语言进行实现.The partition-and-recur method is used to derivate and prove the law of disk movement in the problem of Tower of Hanoi by transform of function specification and formalizing deduction. A non-recursive algorithm in which the occupied memory is unrelated with the number of disks is developed. The algorithm is readable, efficient and has clear structure. The comparison of algorithms shows the effect of the formalizing deduction in obtaining efficient and correct algorithm program. The related algorithm is implemented in UNIX platform with C language.

关 键 词：分划递推法 HANOI塔 归约 变换 形式化推导 算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]