计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (35): 73-75.DOI: 10.3778/j.issn.1002-8331.2008.35.022

• 研发、设计、测试 • 上一篇    下一篇

汉诺塔问题的层次迭代算法

李玉华,崔凤云,刘晓庆   

  1. 西南交通大学 信息科学与技术学院,成都 610031
  • 收稿日期:2007-12-18 修回日期:2008-03-24 出版日期:2008-12-11 发布日期:2008-12-11
  • 通讯作者: 李玉华

Level iterative algorithm for towers of Hanoi puzzle

LI Yu-hua,CUI Feng-yun,LIU Xiao-qing   

  1. School of Information Science & Technology,Southwest Jiaotong University,Chengdu 610031,China
  • Received:2007-12-18 Revised:2008-03-24 Online:2008-12-11 Published:2008-12-11
  • Contact: LI Yu-hua

摘要: 汉诺(Hanoi)塔是程序算法设计的一个比较经典问题,目前已有大量的相关文献对其进行了研究。为进一步加快汉诺塔问题的求解速度,通过对汉诺塔问题抽象解树的分析,发现其可以划分为不同层次相同结构的子树,通过对子树层次化控制即可迭代出整个问题的解。基于此,提出了一种用已知子树分层次迭代汉诺塔问题的非递归算法。运行时间测试表明,该算法进一步提高了求解的速度。

关键词: 汉诺塔, 非递归算法, 抽象解树, 层次迭代

Abstract: The tower of Hanoi puzzle is a classic example about programming design and algorithm research.There have been a lot of researches on this algorithm.In order to speed up the tower of Hanoi problem solving this paper analyzes the abstract solving-tree of the tower of Hanoi problem and find it can be divided into different levels and the same structure,and then iterated the solution of the whole problem by controlling the levels of subtree.Based on this,a rapid non-recursive algorithm of the tower of Hanoi problem through different levels iteration of known subtree is proposed.The result of running time show that this algorithm speed up the velocity of the solving problem.

Key words: tower of Hanoi, non-recursive algorithm, abstract solution-tree, level iteration