自底向上记录式 Hanoi 塔非递归算法

• 作者: 刘清华 戴莉萍 黄龙军
• 来源期刊: 实验科学与技术
• 学科: 工学
• 关键词: Hanoi 塔问题 自底向上记录式 非递归算法 目标柱
• 年，卷（期）: 2016,（1）
• 页码范围: 51-54,81
• 页数: 5页
• 分类号: TP301.6
• 字数: 3374字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-4550.2016.01.016

摘要

Hanoi 塔问题的经典递归算法虽然代码量小，但时间复杂度却是指数级的，而且难以理解。该文基于 Hanoi 塔问题的递归思想，构造出 Hanoi 塔的树模型，仔细分析递归函数的调用参数和语句执行时盘子移动的顺序，巧妙地找到两者之间的对应关系，从而提出一种新的自底向上非递归算法。该算法逐一地记录下 n 从1开始时盘子从源柱到目标柱时经历过的移动轨迹，进而直接应用到 n ＋1个盘子的移动问题。实验结果表明，该算法对应的代码易读且高效，时间复杂度降为O（n），是对 Hanoi 塔问题的非递归算法研究的进一步实践与探讨。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	戴莉萍	江西师范大学软件学院	12	27	2.0	4.0
2	黄龙军	江西师范大学软件学院	18	60	4.0	7.0
3	刘清华	江西师范大学软件学院	14	25	4.0	4.0