汉诺塔问题递归算法与非递归算法比较

肖红德

摘要：汉诺塔问题是一个古典数学问题，对于给定的盘子数量及每步移动盘子次序是确定的。因此，只要能够确定盘子移动的规则，就可以通过计算机程序加以实现。递归算法虽然代码简单，但对于初学者而言，理解其内涵存在困难，且算法执行效率不高。提出一种基于非递归思想的移动方向判断算法解决汉诺塔问题，通过与递归算法执行时间比较，提出的判断移动方向算法执行效率更高，且算法思想相对更简单、更容易理解。

关键词：汉诺塔问题；递归算法；非递归算法；移动规律；算法效率

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成立。

通过对汉诺塔问题算法过程特点的分析，提出一种操作更简单、效率更高的算法实现过程。

通过对移盘顺序在底座之间移动规律的分析得出：在一个底座得到一个最小盘子，之后一次移盘必定在其它两个底座之间进行。如果其它两个底座都没有盘子，则算法结束；如果其它两个底座上只有一个底座有盘子，则从有盘子的底座移向没有盘子的底座；如果其它两个底座都有盘子，则从底座顶端盘子小的一个底座移动到另一个底座，即在判断其它两个底座从一个底座移向另一个底座之前需要判断这两个底座上最顶端的盘子哪个小，移盘方向是从底座上最顶端盘子小的一个底座移向另一个底座。在实现过程中，把每个底座用一个数组表示，每次数组操作都在数组尾部进行，移出一个盘子表示数组减少一个元素，移入一个元素表示数组增加一个元素，类似于栈的出栈与入栈操作。按照该操作规律，提出判断移动方向算法。

判断移动方向算法是在排除上次移入最小盘子（编号为1的盘子）底座的基础上判断在剩余两个底座中，由哪个底座移入另一个底座的算法。判断准则为：哪个底座上最上面盘子小则哪个作为移出底座，另一个作为移入底座；如果其中一个底座上没有盘子，则将非空盘底座作为移出底座，另一个作为移入底座；如果两个底座都没有盘子，则移动盘子结束。

2.2 算法实现

在算法实现过程中，采取一些对比两种算法执行效率一致性的措施，具体如下：每个底座都使用一个对应的数组表示，为简化输出过程，程序中将移盘操作简化为对应底座移出与移入数据的操作，即简单的赋值操作。移动盘子采用对应数组元素赋值的方式表示，每个数组元素的下标采用指针变量的形式指向等。对于类似的操作，采用一致的处理办法表达，这样的处理结果才能体现出不同算法思想在执行效率上的差别。

2.3 运行时间测试

本文所写程序均运行于虚拟机VMware-workstation_full_12.1.1.6932下，主机处理器为：Intel（R） Core（TM） i7-4790 CPU @ 3.60GHz，虚拟机下使用的系统为windows XP，内存1G，处理器1个。由于每次运行程序需要的时间有差别，所得到的时间都是在运行3次后取平均值，通过与递归算法时间对比，得出对于汉诺塔问题，基于非递归思想的判断移动方向算法实现效率更高。

3 结语

从解决汉诺塔问题的移盘规律出发，通过分析发现移盘顺序特点，设计一种解决汉诺塔问题的基于非递规思想的移动方向判断算法实现过程。由于算法中利用了上次移动目标底座，在即将要移动的盘子中排除了上次的目标底座，因此在进行底座之间的移盘方向时只需判断其它两个底座，哪个是源底座哪个是目标底座即可，直到剩余这两个底座都为空时，则完成了目标求解。

参考文献：

[1] 谭浩强.C程序设计（第四版）[M].北京：清华大学出版社，2010.

[2] 吴晓晨.递归程序设计教学方法的研究[J].天津科技，2017，44（1）：69-73.

[3] 姚云霞.对汉诺塔（Hanoi）问题的算法探索与研究[J].物联网技术，2013（7）：48-49.

[4] 王明.梵塔问题的两个定理[J].应用数学，1999（2）：112-114.

[5] 严蔚敏，陈文博.数据结构及应用算法教程[M].北京：清华大学出版社，2011.

[6] 戴莉萍，黄龙军，刘清华.自底向上记录式Hanoi塔非递归算法[J].实验科学与技术，2016，14（1）：51-54.

[7] 张建波.一种将递归过程转换为非递归过程的方法研究[J].计算机教育，2017（8）：139-142.

[8] 李玉华，崔凤云，刘晓庆.汉诺塔问题的层次迭代算法[J].计算机工程与应用，2008，44（35）：73-75.

[9] 卢芳芳，孙燮华，仇苏恺，等.Hanoi塔问题非递归的新算法[J].计算机工程与应用，2006，42（17）：108-110.

[10] 赵东跃.汉诺塔非递归算法研究[J].计算机应用与软件，2008，25（5）：241-243.

[11] 戴莉萍，黄龙军，刘清华，等.记录式Hanoi塔非递归算法及快速仿真[J].电气电子教学学报，2015，37（6）：112-116.

[12] 李健.汉诺塔算法演示系统的设计与实现[J].现代计算机：专业版，2011（24）：76-80.

[13] 卫洪春.图形环境下的汉诺塔演示[J].电子设计工程，2014（15）：8-10.

[14] 李兆歆，张大坤.基于VSL语言的三维动态交互移动实现及其应用[J].计算机工程与设计，2010，31（2）：455-458.

[15] 曾夏玲.基于計算思维能力培养的“轻游戏”教学模式初探[J].职教论坛，2015（11）：79-82.

[16] 李清霞，孙欣.益智课堂，数学核心素养践行之地——以“汉诺塔”活动课为例[J].中国教师，2017（10）.

（责任编辑：刘亭亭）