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

戴莉萍，黄龙军，刘清华

(江西师范大学　软件学院，南昌　330022)



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

戴莉萍，黄龙军，刘清华

(江西师范大学软件学院，南昌330022)

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

Hanoi塔问题；自底向上记录式；非递归算法；目标柱

许多有趣的数学问题都是计算机算法所研究和解决的对象，如Fibonacci问题、水仙花问题、Hanoi塔(汉诺塔)问题等，其中Hanoi塔问题更为复杂和有趣。Hanoi塔问题本身是一个数学游戏，它由3根柱子和一堆可摆放在不同柱上的大小不一的盘子组成。最初所有盘子按照尺寸大小顺序地被放置在一根柱子上，最大的盘子在最下面，最小的盘子在最上面，从而形成一个圆锥形状。游戏的结果是将所有的盘子移动到另一根柱子上，移动过程中的规则是：1)每次只能移动一个盘子；2)每次将一根柱子上面的盘子移动到另一根柱子的上面，即只有某根柱子最上面的盘子才可以移动；3)大盘子不能放置在小盘子之上。3个盘子需要移动7次，n个盘子最少需要移动2n-1次[1]。

目前为止，已经有很多种算法来解决Hanoi问题[1-4]，最为经典的是递归算法，每种解决方法各有着重点。本文通过分析参数赋值顺序与盘子的移动顺序找出其中对应的规律，提出一种自底向上记录式的Hanoi塔非递归算法，使复杂的Hanoi塔问题在解决过程中变得更加简单直接。最终实现的代码短而精，易于理解，极大提高了执行速度。

1　Hanoi塔递归算法中的移动规律

解决Hanoi塔问题著名而经典的算法就是递归算法。设有A，B，C共3根柱子，开始时在A柱上叠有n个盘子，盘子从小到大编号为1，2，…，n，现在要求将A柱上的所有盘子移到C柱上。其基本思想是：1个盘子的Hanoi塔问题可直接移动；n个盘子的Hanoi塔问题可递归表示为首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。由此可见，n个盘子的移动问题可以分为两次n-1个盘子的移动问题，这又可以递归地用上述方法来做，因此可以设计出Hanoi塔问题的递归算法[5]。

下面的函数Hanoi(int n，charA，charC，charB)表示需要将n个盘子从柱子A移动到柱子C，期间可借助柱子B。图1是Hanoi塔问题示意图。

图1　Hanoi塔模型

Hnaoi塔递归算法表示如下:

voidHanoi(inti，charA，charC，charB)

{

if (i==1)move(A，i，C)-递归调用的出口

else

{

--两次递归调用自身函数

Hanoi(i-1，A，B，C);

Move(A，i，C);

Hanoi(i-1，B，C，A);

}

}

从代码组成以及递归调用的过程可以看出盘子移动步骤可以表示为一棵二叉树结构，而且移动过程正好是二叉树的中序遍历，2个盘子和3个盘子的执行顺序，如图2和图3所示。

图2　(n=2)时盘子移动过程

图3　(n=3)时盘子移动过程

现在来分析一下移动n个盘子所需要的移动次数f(n)：根据Hanoi塔递归算法中的步骤，可以发现f(n)=2f(n-1)+1，解此递归关系可以得出f(n)=2n-1。

根据二叉树的性质可以发现结果刚好等于深度为n的满二叉树所具有的结点数。这样的时间复杂度是非常大的。

现在来分析一下在递归调用和盘子移动之间是否存在一定的规律性。在图2中，n=2时Hanoi(2，A，C，B)盘子的移动顺序可以表示为1AB2AC1BC，其中1AB表示编号为1的盘子从A柱移动到B柱。在图3中，树左边n=2时Hanoi(2，A，B，C)盘子的移动顺序为1AC2AB1CB，树右边n=2时Hanoi(2，B，C，A)盘子的移动顺序为1BA2BC1AC。这两个图中n=2时的参数位置和移动位置的相对关系，如图4所示。

图4　n=2时，函数参数位置与移动位置

从图4可以看出函数传递参数的位置和移动位置存在一定的规律性，即函数中同一位置上的传递参数无论是什么，该参数在移动过程中出现的位置总是固定的，这里忽略盘子的编号数。例如Hanoi函数中传递的第1个参数arg1始终出现移动过程中的第1和第3位置；参数2即arg2出现在移动过程中的第4和第6的位置，参数3即arg3出现在移动过程中的第2和第5的位置。这样，只要知道n-1个盘子的移动过程，则在求n个盘子移动过程时，就可直接利用n-1个盘子的移动规律，通过相应的参数替换功能即可得到答案。下面举例说明。

已知n=2时从源柱A到目标柱子C的移动过程:

Hanoi(2，A，C，B)=Hanoi(2，arg1，arg2，arg3)

=’1AB2AC1BC’

=’1 arg1 arg3 2 arg1 arg2 1 arg3 arg2’

求n=3时前2个盘子的先后移动过程:

Hanoi(2，A，B，C)=Hanoi(2，arg1，arg2，arg3)

=’1 arg1 arg3 2 arg1 arg2 1 arg3 arg2’

=’1AC2AB1CB’

Hanoi (2，B，C，A)=Hanoi(2，arg1，arg2，arg3)

=’1 arg1 arg3 2 arg1 arg2 1 arg3 arg2’

=’1BA2BC1AC’

在求取Hanoi(2，A，B，C)或Hanoi(2，B，C，A)时，可以不需要再进行递归调用，而是直接利用’1AB2AC1BC’的结果，将对应的移动轨迹转换成对应的函数传递参数即可。

2　记录式Hanoi塔非递归算法描述

尽管Hanoi塔的递归技术能利用系统内部功能自动实现调用过程中信息的保存与恢复，省略了程序设计中的许多细节操作，简化了程序设计过程，但仍然存在一些问题，如运行效率较低，递归内部的实现原理比较难理解，程序阅读较为困难，因此，为消除算法的递归调用，大大节省运行时间，增强程序的可读性，提出了记录式Hanoi塔的非递归算法。

利用函数的参数位置和移动位置的对应关系，可以自底向上逐步求取并记录下当盘子数i=1，2，…，n时从源柱A到目标柱C期间所有各个盘子移动的顺序和位置，从而将递归算法自顶向下产生的各个子问题求解过程直接转换为循环非递归求解过程，算法复杂性大大降低了，时间复杂度得到了很好的改善。当n=3时自底向上记录式非递归算法过程如图5所示。

图5　n=3时，记录式算法的计算过程

从图5可以看出，要求取3个盘子从A到C的移动过程：首先得到1个盘子从A到C的移动过程；再求得2个盘子从A到C的移动过程，期间利用1个盘子的移动轨迹，根据参数位置改变移动轨迹的相应值；最后利用2个盘子的移动轨迹和传递参数替换得到3个盘子的最终移动结果。

下面是自底向上记录式的Hanoi塔非递归算法伪码表示。其中字符串变量result保存的就是前n-1个盘子从A柱到C柱所经历的盘子移动次序。HanoiRecord函数的主体部分仍与递归算法过程类似，只不过不要递归调用，而是采用循环，并直接通过HanoiReplace函数获取移动值。HanoiReplace函数中第1个参数表示当前盘子的个数，第2个参数表示当前所在柱，第3个参数表示当前目的柱，第4个参数表示当前辅助柱，第5个参数表示当前盘子数从A到C的已知移动轨迹。HanoiReplace函数主要的功能就是将result改成符合当前移动要求的顺序，简单来说就是替换。

输入:盘子个数n，起始柱A，目的柱C，辅助柱B

输出:结果字符串result

过程:

HanoiRecord(intn，charA，charC，charB)

{

if (n==1) result=’1AC’;

else

for (i=2;i<=n;i++)

{

firststep=HanoiReplace(i-1，A，B，C，result);

secondstep=str(i)+”AC’;//i变为字符型

laststep=HanoiReplace(i-1，B，C，A，result);

result=firststep+secondstep+laststep;

}

}

当n=1时，result变量直接赋值，这也是result的初始值，在计算n=2时盘子的移动过程会使用到它。firsttep是字符串变量，保存着前i-1个盘子从源柱A移动到辅助柱B经历的移动顺序，在这里辅助柱B相当于就是当前的目标柱了，求取过程中需要利用已知的前i-1个盘子从源柱A到目标柱C时移动轨迹的字符串result，然后加以参数替换。secondstep也是字符串变量，直接保存的就是编号为n的盘子从A柱到C柱的过程，str(i)是类型转换，将整数型转换为字符串型。字符串变量laststep求取的是将放置在B柱的前i-1个盘子移动到C柱，利用的仍然是已知的前i-1个盘子从A柱到C柱的移动字符串result。最后将这三步得到的字符串进行连接，保存在result变量中，即已知i个盘子从源柱A到目标柱C的所有路径，从而在下一个循环中加以利用。表1列出了部分执行过程中对应的变量值。

表1　Hanoitest表部分对应值

3　算法的代码实现

本文中采用Visual Basic来实现所提出的算法，由于这里主要体现算法思想，因此并不对执行过程做可视化处理；绘制的界面比较简单，如图6所示。界面使用了1个textbox用于输入盘子个数n值，另1个textbox用于显示各个盘子的移动过程，即结果。算法实现放置在按钮Hanoi的单击事件当中，采用循环替代了递归过程。除此之外，定义了一个函数Hanoireplace来进行字符替换，主要使用VB中的字符串函数replace来完成[6-7]。

图5　设计界面效果图

在Hanoireplace函数实现过程中，输入参数中result表示i-1个盘子从A到C的移动轨迹结果，source表示当前i-1个盘子所在位置，dest表示当前i-1个盘子将要被放置到的目标位置，auxi表示当前需要使用到的辅助位置。Hanoireplace主要使用了replace这个字符串函数，先将原有移动轨迹中的A、B、C替换成X、Y、Z，再将X、Y、Z替换成当前的源柱、辅助柱和目标柱表示。这样就体现了参数位置和移动顺序之间的对应关系，使得问题的解决更加简单明了。具体代码如下。

Public Function Hanoireplace(result As String，source As String，dest As String，auxi As String) As String

Dim varstep As String

varstep = result

varstep = Replace(varstep，"A"，"X")

varstep = Replace(varstep，"C"，"Z")

varstep = Replace(varstep，"B"，"Y")

varstep = Replace(varstep，"X"，source)

varstep = Replace(varstep，"Z"，dest)

varstep = Replace(varstep，"Y"，auxi)

Hanoireplace = varstep

End Function

按钮点击事件代码中则会调用上面定义好的Hanoireplace函数，最终求得n个盘子从A到C的移动轨迹结果。具体代码如下:

Dimi，nAs Integer

Dim firststep，secondstep，laststep，result As String

n= tx_n.Text

result = "1AC"

If (n= 1) Then

result = "1AC"

Else

Fori= 2 Ton

firststep = Hanoireplace(result，"A"，"B"，"C")

secondstep = CStr(i) + "AC"

laststep = Hanoireplace(result，"B"，"C"，"A")

result = firststep + secondstep + laststep

Nexti

End If

tx_result.Text = result

代码中n表示盘子个数，变量i是循环变量，在循环体内也表示当前盘子的个数。firststep表示i-1个盘子暂时从A柱移动到辅助柱B的移动结果，secondstep表示编号i的盘子直接A柱到C柱的结果，laststep表示i-1个盘子从辅助柱B到C柱的结果，result则是前面3个步骤的结果串联，初始值为1个盘子直接从A移动到C。

例如观察n=2时的记录，n为2表示当前盘子个数为2，firststep保存前n-1即1个盘子从源A柱到辅助B柱的移动轨迹:“1AB”，secondstep保存着第n个盘子即2号盘从源A柱直接移动到目标C柱的轨迹:“2AC”；laststep保存着前n-1即1个盘子从辅助B柱到目标C柱的移动轨迹:“1BC”；result则保存着全部路径，即前面三个字符串的合集:“1AB2AC1BC”。即先生成二叉树左子树，而后生成二叉树的中间节点，最后生成二叉树的右子树，符合递归过程的执行思路。

从算法分析和代码实现可以很容易地看出程序的主体就是一个循环体，分别获取了n=1，2，3……n个盘子的移动过程，时间复杂度为O(n)，将递归过程很巧妙地转换成为非递归调用。

4　结束语

自底向上记录式Hanoi塔非递归方法虽然变量result会随着n的增大而占用更大的空间，但时间复杂度为O(n)，执行效率仍有了非常大的提高。而且该算法的主体部分仍借鉴了Hanoi塔递归算法的基本思想，并在此基础上进行灵活的改进，从而使得代码简短、易于理解，极大地降低了程序的复杂性。本算法从另一个角度揭示了Hanoi塔问题中的其中一个特点，对于Hanoi塔问题的进一步研究提供了一定的参考思路和方法。

[1]王晓东.算法设计与分析[M].2版.北京：清华大学出版社，2010.

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

[3]陈业红，张洁，陈琦.基于动态规划技术的汉诺塔趣味递推实现[J].山东轻工业学院学报，2011，25(4):47-49 .

[4]魏斌，马继辉，牛虎.基于递归算法的树型结构图的设计与实现[J].计算机应用与软件，2011，28(1):96-98.

[5]周斌.“Problem of Towers of Hanoi”仿真软件的设计[J].实验室研究与探索，2011，30(7):61-63，71.

[6]陈瑞环，杨庆红，姚兴.使用递推解决递归问题的研究与应用[J].计算机应用与软件，2011，28(3):186-188.

[7]胡英.Visual Basic程序设计[M].北京：清华大学出版社.2014.

Non-Recursive Algorithm Based on Down-Up Record Method for Hanoi Tower

DAI Liping，HUANG Longjun，LIU Qinghua

(Software School，Jiangxi Normal University，Nanchang 330022，China)

The code of classical recursion algorithm for Hanoi tower problem is simple，but the time complexity isO(2n) and the code is difficult to understand.Understanding recursive idea of Hanoi tower problem and constructing a tree model based on the function，two objectives of the function’s parameters and the execution result are analyzed carefully.Then the relationship between them is obtained and used to design a new down-up non-recursive algorithm.This algorithm here records the moving paths ofnplates (n=1，2，…)，which could be applied to get the moving result ofn+1 plates directly.The experimental results show that the corresponding code is very easy to read，and its time complexity is onlyO(n)，which is further practice and study for the non-recursive research of Hanoi tower problem.

Hanoi tower problem; down-up record; non-recursive algorithm; Visual Basic

2014-12-30

江西省自然科学基金项目(20132BAB201031)。

戴莉萍(1979-)，女，硕士，讲师，主要从事软件工程、数据库技术方面的研究。

TP301.6

A

10.3969/j.issn.1672-4550.2016.01.016