1、 汉诺塔问题的非递归算法计算机科学与技术学院计 11-1 班张春颖（组长） 37 号刘 丹（组员） 22 号汉诺塔问题的非递归新解法计 11-1 张春颖 37 号刘 丹 22 号摘要：汉诺塔问题是计算机算法设计中经常被大家引用来说明递归算法的一个经典问题，长期以来，很多人一直认为这个问题只能用递归方法求解，从讨论汉诺塔问题的几个基本特性入手，通过分析和归纳总结，提出了一种全新的解决汉诺塔问题的简洁而又高效的非递归解法，并用具体的实例对其进行了验证。关键词：汉诺塔；非递归；对称性；形式不变性1汉诺塔问题及其特性汉诺塔问题可以一般地表述为：有 3 根针 A,B,C,在 A 针上有 n 个大小互不相
2、同的盘子，大盘在下，小盘在上，现在要将这 n 个盘子全部移到 C 针上，规则是：每次只能移一个盘子，任何时候在每根针上都要保持大盘在下面小盘在上;移动过程可以利用针 B.请问该怎么移？汉诺塔问题是一个古典的数学问题，一般的参考文献中都认为汉诺塔问题是一个只能用递归方法解决的问题。汉诺塔问题具有递归性，但并不是说它就只能用递归方法来解决，为了寻求其非递归新解法，下面先来讨论一下汉诺塔问题的几个基本特性。1.汉诺塔问题的递归性将这 n 个盘子由小到大依次编号为：1,2,3,.N.为了将这 n 个盘子按照规则从针A 移动到针 C.可以分 3 步走：第 1 步：将前 n-1 个盘子按照规则从针 A 移
3、动到针 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 个盘子的汉诺塔问题正好处于那两个
4、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 个盘子按照给定的规则从针
5、 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
6、(x,n,z)可定义为（c 是初值为 0的/全局变量，对搬动计数） ；12 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x,n,z);7 hanoi(n-1,y,x,z);8 9 但是递归看似简洁，但是递归算法解题的运行，效率较低，在递归调用的过程中系统为每层的返回点、局部量等开辟了栈来存储递归次数过多容易造成栈溢出，汉诺塔问题会多次用到递归，所以会发生栈溢出2非递归解法的几个基本问题根据递归性，我们很容易写出汉诺塔问题的递归解，关于这一点，很多高级语言的教科书都有涉及，下面我们专门来讨论其非递归解问题。为了找到其非递归解，我们需要
7、而且只需要解决下列 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*2n-1(n=1) 即：An=2n-1(n=1)所以，解决 n 个盘子的汉诺塔问题至少需要 2n-1 步操作。2.
8、每步的操作对象问题根据汉诺塔问题的对称性和递归性，在 n 个盘子的汉诺塔问题所需要的 2n-1 步操作中，处于中心位置的那一步的操作对象是 N 号盘，前一半操作和后一半操作的操作对象关于中心位置对称，因此只要确定出前一半操作的操作对象，那么后一半操作的操作对象也就随之确定了，而前一半操作又是解决前 n-1 个盘子的汉诺塔问题的，因此处于这一半的中心位置的那一步的操作对象就应该是 N-1 号盘，如此继续下去，每一步的操作对象都可以确定下来，下面给出 n=1,2,3,4,5 时，每一步的操作对象：1 个盘：12 个盘：1 2 1 3 个盘：1 2 1 3 1 2 14 个盘：1 2 1 3 1 2
9、 1 4 1 2 1 3 1 2 15 个盘：1 2 1 3 1 2 1 4 1 2 1 3 1 2 15 1 2 1 3 1 2 1 4 1 2 1 3 1 2 13.每步的起点和终点问题根据汉诺塔问题的对称性和递归性，在 n 个盘子的汉诺塔问题所需要的 2n-1 步操作中，处于中心位置的那一步的操作对象 N 号盘，起点是针 A，终点是针 C;前一半操作是将前 n-1 个盘子从针 A 移到针 B 的。因此，处于这一半的中心位置的那一步的操作对象是 N-1 号盘，起点是针 A,终点是针 B；后一半操作是将前 n-1 个盘子从针 B 移到针 C 的。因此，处于这一半的中心位置的那一步的操作对象是
10、 N-1 号盘，起点是针 B，终点是针 C，按照这种方式，从中心位置开始，逐渐向两端扩展，最终能够确定所有操作步的起点和终点。至此，前面提出的 3 个问题都得到了解决，可直接按照上述思想来设计汉诺塔问题的非递归算法却不是一件很容易的事情，且算法的效率也不太理想。3汉诺塔问题的几个基本理论任何递归问题都可以很容易地通过函数的递归调用来求解，但其效率却比较底下，比较而言，递归问题的的、非递归解法实现起来要困难一些，但其执行效率却比较高。那么，有没有既容易实现而且效率又较高的非递归解法呢？答案是肯定的，那就是递推！事实上，根据前面所述的分析，我们可以得到以下几个结论：（1）解决 n 个盘子的汉诺塔问
11、题所需要的最少操作步数为 2n-1；（2）在解决 n 个盘子的汉诺塔问题所需要的 2n-1 步操作中，处于中心位置的第2n-1 步的操作对象是 N 号盘，且操作的起点是针 A，终点是针 C；（3）在解决 n 个盘子的汉诺塔问题所需要的 2n-1 步操作中，除了中心点之外的前一半操作可以由解决 n-1 个盘子的汉诺塔问题所需要的 2n-1-1 步操作得到：将解决 n-1 个盘子的汉诺塔问题所需要的 2n-1-1 步操作中的 B 换成 C，C 换成 B,而 A 保持不变。（4）在解决 n 个盘子的汉诺塔问题所需要的 2n-1 步操作中，除了中心点之外的后一半操作可以由前一半操作得到，将前一半操作中
12、的 A 换成 B,B 换成 C,C 换成 A.至此，汉诺塔问题的递归算法就产生了，其实，递归递推只是同一类问题的两种不同求解策略而已。因此，任何递归问题都可以采用递推方法求解，只不过难易程度有别而已。四递推算法下面用 C 语言给出利用上述 4 点结论的非递归解法的计算机算法递推算法。重要数据结构：S2n 行 3 列的二维数组，存放所有的操作步。其中，第 i 行（i=1,2,3,.）表示第 i 步，而且 Si1表示操作的起点，Si2表示操作的终点，算法如下：for(K=1;K=N;K+)for(X=1,M=1,M=K-1,M+)X=X*2;SX0=K;SX1=A;SX2=C;for(L=1;L=
13、X-1;L+)if (SL1=B)SL1=C;else if (SL1=C)SL1=Bif(SL2=B)SL2=C;else if(SL2=C)SL2=B;for(L=X+1;L=2*X-1;L+) SL0=SL-X0;if(SL-X1=A) (SL-X1=B);else if(SL-X1=B) (SL1=C);else SL1=A;if(SL-X2=A) SL2=B;else if(SL-X2=B) SL2=C;else SL2=A;实际上，为解决 n 个盘子的汉诺塔问题，数组 S 只需要2n-1行即可；先求出 n-1个盘子的汉诺塔问题的解，然后根据 S 的内容输出 n 个盘子的汉诺塔问题的
14、解，这样，空间开销句降低了一半，时间开销也有所改善。5结语目前，已经见诸文章的解决汉诺塔问题的非递归算法为数不多而且多数都是利用二叉树甚至是三叉树做为逻辑数据结构并通过树的构造和遍历来实现的.这类算法虽然思想基础较简单，但空间开销和时间开销都比较大，另有一些算法虽然空间和时间开销大有改善，但其导出过程比较复杂，一般人难以领悟。比较而言，本文介绍的递推算法不仅简单易行，而且其思想基础人人都能把握。参考文献：1李永新，汉诺塔问题的非递归算法实现J.荆州师范学院学报（自然科学版） ，2000,22（6）：4347.2王 颖，王正洲，汉诺塔问题迭代算法实现和分析J.合肥联合大学学报。1999,9（3）：8487.
