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

汉诺塔问题的非递归算法

计算机科学与技术学院

计11-1班

张春颖（组长）37号

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

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

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

汉诺塔问题及其特性
汉诺塔问题可以一般地表述为：有3根针A,B,C,在A针上有n个大小互不相同的盘子，大盘在下，小盘在上，现在要将这n个盘子全部移到C针上，规则是：每次只能移一个盘子，任何时候在每根针上都要保持大盘在下面小盘在上;移动过程可以利用针B.请问该怎么移？
汉诺塔问题是一个古典的数学问题，一般的参考文献中都认为汉诺塔问题是一个只能用递归方法解决的问题。
汉诺塔问题具有递归性，但并不是说它就只能用递归方法来解决，为了寻求其非递归新解法，下面先来讨论一下汉诺塔问题的几个基本特性。
汉诺塔问题的递归性
将这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所需的所有操作步集合。
汉诺塔问题的轮换性
设S为将n个盘子按照给定的规则从针A移到针B所需的所有操作步的集合，按照形式不变性，如果将S中的A全部换成B,B全部换成C，C全部换成A,则得到的是将N个盘子按照同样的规则从针B移到针C所需的所有操作步的集合。同样，如果将S中的A全部换成C，C全部换成A，B保持不变，则得到的是将n个盘子按照同样的规则从针C移到针B所需的所有操作步的集合。
递归算法如下
Voidhanoi(intn,charx,chary,charz)上按
//将塔座x上按直径由小到大且自上而下编号为1至nde个圆盘按规则搬到塔
//座z上，y可用作辅助塔座。搬动操作move(x,n,z)可定义为（c是初值为0的
//全局变量，对搬动计数）；
1{
2if(n==1)
3move(x,1,z);
4else
5hanoi(n-1,x,z,y);
6move(x,n,z);
7hanoi(n-1,y,x,z);
8}
9}

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

非递归解法的几个基本问题
根据递归性，我们很容易写出汉诺塔问题的递归解，关于这一点，很多高级语言的教科书都有涉及，下面我们专门来讨论其非递归解问题。
为了找到其非递归解，我们需要而且只需要解决下列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.每步的操作对象问题
根据汉诺塔问题的对称性和递归性，