文献类型：期刊文章

作　　者：赵东跃[1]

机构地区：[1]福州大学工程技术学院,福建福州350002

出　　处：《计算机应用与软件》

年　　份：2008

卷　　号：25

期　　号：5

起止页码：241-243

语　　种：中文

收录情况：BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD_E2011_2012、IC、ZGKJHX、核心刊

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

关 键 词：汉诺塔 递归算法 非递归算法

分 类 号：TP301.6] TP311.1[计算机类]