汉诺塔问题的非递归新解法.doc

汉诺塔问题的非递归算法

计算机科学与技术学院

计11-1 班

张春颖（组长） 37 号

刘 丹（组员） 22 号
汉诺塔问题的非递归新解法

计11-1 张春颖 37号
刘 丹 22号

摘要：汉诺塔问题是计算机算法设计中经常被大家引用来说明递归算法的一个经典问题，长期以来，很多人一直认为这个问题只能用递归方法求解，从讨论汉诺塔问题的几个基本特性入手，通过分析和归纳总结，提出了一种全新的解决汉诺塔问题的简洁而又高效的非递归解法，并用具体的实例对其进行了验证。
关键词：汉诺塔；非递归；对称性；形式不变性

一． 汉诺塔问题及其特性
汉诺塔问题可以一般地表述为：有3根针A,B,C,在A针上有n个大小互不相同的盘子，大盘在下，小盘在上，现在要将这n个盘子全部移到C针上，规则是：每次只能移一个盘子，任何时候在每根针上都要保持大盘在下面小盘在上;移动过程可以利用针B.请问该怎么移？
汉诺塔问题是一个古典的数学问题，一般的参考文献中都认为汉诺塔问题是一个只能用递归方法解决的问题。
汉诺塔问题具有递归性，但并不是说它就只能用递归方法来解决，为了寻求其非递归新解法，下面先来讨论一下汉诺塔问题的几个基本特性。
1. 汉诺塔问题的递归性
将这n个盘子由小到大依次编号为：1,2,3,......N.为了将这n个盘子按照规则从针A移动到针C.可以分3步走：
第1步：将前n-1个盘子按照规则从针A移动到针B;
第2步：将第n个盘子直接从针A移动到针C;
第3步：将前n-1个盘子按照规则从针B移动到针C;
这样一来，n个盘子的汉诺塔问题就转化成了n-1个盘子的汉诺塔问题，而它们之间只是盘子的数目以及起点和终点有别而已。而n-1个盘子的汉诺塔问题又可以进一步地转化成n-2个盘子的汉诺塔问题。如此转化下去，最终结果是：n个盘子的汉诺塔问题转化成了一序列1个盘子的汉诺塔问题。
2汉诺塔问题的对称性
由上述分析可见，n个盘子的汉诺塔问题可以转化为两个n-1个盘子的汉诺塔问题和一个1个盘子的汉诺塔问题，并且这1个盘子的汉诺塔问题正好处于那两个n-1个盘子的汉诺塔问题的中间，因此，解决n个盘子的汉诺塔问题所需要的最少操作步数应该是奇数，而且所有操作步的操作对象按照顺序应该是中心对称的，对称中心就是N号盘。
3.汉诺塔问题的形式不变性
一般地，设X,Y,Z为3根针，S为将n个盘子按照给定的规则从针X移到针Y所需的所有操作步的集合，如果用A,B,C的任意一个全排列K1，K2，K3去对应替换S中的X,Y,Z:K1替换X,K2替换Y,K3替换Z，则得到的是将n个盘子按照同样的规则从针K1移到K2所需的所有操作步集合。
4. 汉诺塔问题的轮换性
设S为将n个盘子按照给定的规则从针A移到针B所需的所有操作步的集合，按照形式不变性，如果将S中的A全部换成B,B全部换成C，C全部换成A,则得到的是将N个盘子按照同样的规则从针B移到针C所需的所有操作步的集合。同样，如果将S中的A全部换成C，C全部换成A，B保持不变，则得到的是将n个盘子按照同样的规则从针C移到针B所需的所有操作步的集合。
5. 递归算法如下
Void hanoi(int n,char x,char y,char z)上按
//将塔座x上按直径由小到大且自上而下编号为1至nde 个圆盘按规则搬到塔
//座z上，y可用作辅助塔座。搬动操作move(x,n,z)可定义为（c是初值为0的
//全局变量，对搬动计数）；
1{
2 if(n==1)
3 move(x,1,z);
4 else
5 hanoi(n-1,x,z,y);
6 move(x,n,z);
7 hanoi(n-1,y,x,z);
8 }
9 }

但是递归看似简洁，但是递归算法解题的运行，效率较低，在递归调用的过程中系统为每层的返回点、局部量等开辟了栈来存储递归次数过多容易造成栈溢出，汉诺塔问题会多次用到递归，所以会发生栈溢出

二． 非递归解法的几个基本问题
根据递归性，我们很容易写出汉诺塔问题的递归解，关于这一点，很多高级语言的教科书都有涉及，下面我们专门来讨论其非递归解问题。
为了找到其非递归解，我们需要而且只需要解决下列3个问题：
（1） 至少需要多少步操作？
（2） 每一步的操作对象是谁？
（3） 每一步操作的起点和终点又是谁?
1.操作步数问题
设将n个盘子按照规则从第1根针移动到第3根针所需要的最少操作步数为An,则根据汉诺塔问题的递归性和对称性，数列{An}满足：
A1=1，而当n>=2时有An=2An_1+1 由An=2An_1+1可得：An+1=2(An_1+1) 这说明数列（An+1）是以2为公比而以A1+1即2为首项的等比例数，所以：An+1=2*2^n-1(n>=1) 即：An=2^n-1(n>=1)
所以，解决n个盘子的汉诺塔问题至少需要2^n-1步操作。
2.每步的操作对象问题
根据汉诺塔问题的对称性和递归性，在n个盘子的汉诺塔问题所需要的2^n-1步操作中，处于中心位置的那一步的操作对象是N号盘，前一半操作和后一半操作的操作对象关于中心位置对称，因此只要确定出前一半操作的操作对象，那么后一半操作的操作对象也就随之确定了，而前一半操作又是解决前n-1个盘子的汉诺塔问题的，因此处于这一半的中心位置的那一步的操作对象就应该是N-1号盘，如此继续下去，每一步的操作对象都可以确定下来，下面给出n=1,2,3,4,5时，每一步的操作对象：
1个盘：1
2个盘：1 2 1
3个盘：1 2 1 3 1 2 1
4个盘：1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
5个盘：1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
5
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
……
3.每步的起点和终点问题
根据汉诺塔问题的对称性和递归性，在n个盘子的汉诺塔问题所需要的2^n-1步操作中，处于中心位置的那一步的操作对象N号盘，起点是针A，终点是针C;前一半操作是将前n-1个盘子从针A移到针B的。因此，处于这一半的中心位置的那一步的操作对象是N-1号盘，起点是针A,终点是针B；后一半操作是将前n-1个盘子从针B移到针C的。因此，处于这一半的中心位置的那一步的操作对象是N-1号盘，起点是针B，终点是针C，按照这种方式，从中心位置开始，逐渐向两端扩展，最终能够确定所有操作步的起点和终点
至此，前面提出的3个问题都得到了解决，可直接按照上述思想来设计汉诺塔问题的非递归算法却不是一件很容易的事情，且算法的效率也不太理想。
三． 汉诺塔问题的几个基本理论
任何递归问题都可以很容易地通过函数的递归调用来求解，但其效率却比较底下，比较而言，递归问题的的、非递归解法实现起来要困难一些，但其执行效率却比较高。那么，有没有既容易实现而且效率又较高的非递归解法呢？答案是肯定的，那就是递推！
事实上，根据前面所述的分析，我们可以得到以下几个结论：
（1） 解决n个盘子的汉诺塔问题所需要的最少操作步数为2^n-1；
（2） 在解决n个盘子的汉诺塔问题所需要的2^n-1步操作中，处于中心位置的第2^n-1步的操作对象是N号盘，且操作的起点是针A，终点是针C；
（3） 在解决n个盘子的汉诺塔问题所需要的2^n-1步操作中，除了中心点之外的前一半操作可以由解决n-1个盘子的汉诺塔问题所需要的2^n-1-1步操作得到：将解决n-1个盘子的汉诺塔问题所需要的2^n-1-1步操作中的B换成C，C换成B,而A保持不变。
（4） 在解决n个盘子的汉诺塔问题所需要的2^n-1步操作中，除了中心点之外的后一半操作可以由前一半操作得到，将前一半操作中的A换成B,B换成C,C换成A.
至此，汉诺塔问题的递归算法就产生了，其实，递归递推只是同一类问题的两种不同求解策略而已。因此，任何递归问题都可以采用递推方法求解，只不过难易程度有别而已。
四．递推算法
下面用C语言给出利用上述4点结论的非递归解法的计算机算法——递推算法。
重要数据结构：S——2n行3列的二维数组，存放所有的操作步。其中，第i行（i=1,2,3,...）表示第i步，而且S[i]{[1]表示操作的起点，S[i][2]表示操作的终点，算法如下：
for(K=1;K<=N;K++)
{
for(X=1,M=1,M<=K-1,M++)X=X*2;
S[X][0]=K;
S[X][1]=’A’;
S[X][2]=’C’;
for(L=1;L<=X-1;L++)
{
if (S[L][1]==’B’)S[L][1]=’C’;
else if (S[L][1]==’C’)S[L][1]=’B’
if(S[L][2]==’B’)S[L][2]=’C’;
else if(S[L][2]==’C’)S[L][2]=’B’;
}
for(LX+1;L<=2*X-1;L++)
{
S[L][0]=S[L-X][0];
if(S[L-X][1]==‘A’) (S[L-X][1]==‘B’);
else if(S[L-X][1]==‘B’) (S[L][1]==‘C’);
else S[L][1]=‘A’;
if(S[L-X][2]==‘A’) S[L][2]=‘B’;
else if(S[L-X][2]==‘B’) S[L][2]=‘C’;
else S[L][2]=‘A’;
}
}
实际上，为解决n个盘子的汉诺塔问题，数组S只需要2^n-1行即可；先求出n-1个盘子的汉诺塔问题的解，然后根据S的内容输出n个盘子的汉诺塔问题的解，这样，空间开销句降低了一半，时间开销也有所改善。
五． 结语
目前，已经见诸文章的解决汉诺塔问题的非递归算法为数不多而且多数都是利用二叉树甚至是三叉树做为逻辑数据结构并通过树的构造和遍历来实现的.这类算法虽然思想基础较简单，但空间开销和时间开销都比较大，另有一些算法虽然空间和时间开销大有改善，但其导出过程比较复杂，一般人难以领悟。
比较而言，本文介绍的递推算法不仅简单易行，而且其思想基础人人都能把握。

参考文献：
[1]李永新，汉诺塔问题的非递归算法实现[J].荆州师范学院学报（自然科学版），2000,22（6）：43~47.
[2]王 颖，王正洲，汉诺塔问题迭代算法实现和分析[J].合肥联合大学学报。1999,9（3）：84~87.