汉诺塔问题递归算法与非递归算法比较
作者：肖红德
来源：《软件导刊》2018年第08期
        摘要：汉诺塔问题是一个古典数学问题，对于给定的盘子数量及每步移动盘子次序是确定的。因此，只要能够确定盘子移动的规则，就可以通过计算机程序加以实现。递归算法虽然代码简单，但对于初学者而言，理解其内涵存在困难，且算法执行效率不高。提出一种基于非递归思想的移动方向判断算法解决汉诺塔问题，通过与递归算法执行时间比较，提出的判断移动方向算法执行效率更高，且算法思想相对更简单、更容易理解。
        关键词：汉诺塔问题；递归算法；非递归算法；移动规律；算法效率
        DOIDOI：10.11907/rjdk.173151
        中图分类号：TP312
        文献标识码：A 文章编号：1672-7800（2018）008-0118-03
        英文摘要Abstract：The Hanoi tower problem is a classical mathematical problem.Since the order of moving plate at each step is fixed for a given number of plates，the rules for moving plate can be readily determined by computer program.Although the code of recursive algorithm is simple，but for beginners，its meaning is not easy to understand，and the efficiency of its execution is not high.In this paper，we propose algorithm which is based on the non-recursive thinking and used to jude moving directions
        to solve the problem of the Hanoi tower.By comparing with the execution time of the recursive algorithm，we can draw a conclusion that judge the algorithm proposed in this paper is more efficient，and its algorithmic thinking is relatively simple，easier to understand.
        英文关键词Key Words：the problem of hanoi tower；recursive algorithm； non-recursive algorithm； movement rule； algorithm efficiency
        0 引言
        汉诺塔问题是一个古典数学问题，也是计算机程序设计中用递归算法解题的经典例子。问题描述如下：有3个底座A、B、C可以用来存放盘子，有64个大小不等的盘子，初始时64个盘子都在A座上且大盘子在下、小盘子在上（编号由上到下依次为1～64），若让这64个盘子从A座移动到C座，在移动过程中需要满足以下条件：每次只能移动一个盘子；A、B、C 3个底座上的盘子都需要保持大盘子在下、小盘子在上。要求给出每次移动盘子的具体步骤。
        1 汉诺塔问题研究现状
        汉诺塔问题的研究已有大量成果。文献[1-3]通过递归算法加以实现；文献[4]给出关于移盘顺序与移盘规律的两个定理；文献[5]中涉及多处对递归算法转换为非递归算法的介绍，其中在介绍栈与二叉树相关内容时对递归与非递归结构之间转化以及在具体解决实际问题中有大量分析与具体实现过程；文献[6-7]研究了递归算法转换为非递归算法的过程；文献[8-10]通过非递归算法实现该问题的求解；文献[11-14]通过程序仿真演示移盘过程；文献[15-16]给出了汉诺塔问题在教育教学改革中的具体应用。
        对于该问题，在很多计算机程序设计的教材与参考书中都有涉及，但有部分算法实现需
要学习者有较为深厚的理论基础，不能通过简单的规则，使用比较基础的语言进行简明实现，致使不少初学者对该问题仍有困惑。
        2 汉诺塔问题算法实现
        2.1 算法准备
        对于汉诺塔问题，给定n个盘子，其具有以下事实：
        （1）对于n个圆盘，求解Hanoi问题，最少总移动次数是需要移动盘子次数的2n-1次，如文献[9]中的定理1。
        （2）对于任意给定的圆盘数量n与给定源底座与目标底座，移盘顺序与移盘过程（每一次的移动圆盘号、源底座、目标底座）是确定的，如文献[4]中的两个定理。
        （3）盘子在底座上的移动规律为：最小盘（第1号盘）移动与其它大盘（第2-n号盘）移动是交叉进行的，即移动一次最小盘，就要移动一次其它大盘。如果n为奇数，则最小盘子的移动规律是A→C→B→A…的循环移动，即先由底座A移动到底座C，再移动一次大盘子，
再将最小的盘子由底座C移动到底座B，再移动一次大盘子，再将最小盘子底座B移动到底座A，再移动一次大盘子…；如果n为偶数，则最小盘子的移动规律是A→B→C→A…的循环移动；大盘子移动的规律是在两次最小盘子移动之间进行的。
        （4）每个盘子需要移动的次数是确定的，每个盘子需要移动的次数为2n-i。
        对于事实（4）的证明：
        ①当n=1时，i=1，只需将一个盘子从底座A移动到底座C，结论成立。
        ②假设n=k（k≥1）时结论成立，即每个盘子需要移动的次数为2n-i。二叉树中序遍历非递归算法
        ③当n=k+1（k≥1）时，由汉诺特问题的递归调用算法可知，前k个盘子需要整体移动2次，即前k个盘子移动的次数是当n=k（k≥1）时的2倍，表示为2×2k-i=2（k+1）-i；第n=k+1（k≥1）个盘子只需移动一个盘子，表示为2n-（k+1），即当n=k+1（k≥1）时，每个盘子移动的次数2n-i成立。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。