汉诺塔非递归算法研究

• 作者: 赵东跃
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 汉诺塔 递归算法 非递归算法
• 年，卷（期）: 2008,（5）
• 所属期刊栏目: 算法
• 页码范围: 241-243
• 页数: 3页
• 分类号: TP3
• 字数: 2649字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2008.05.096

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵东跃	福州大学工程技术学院	1	5	1.0	1.0