汉诺塔论文

摘要：长期以来，人们只熟悉汉诺塔问题的递归算法。这里我们采用非递归算法解决这个问题，没用到栈和二叉树。关键字：改变表现，递推关系，时间（空间）复杂度汉诺塔问题：有大小不同的n个盘子和三个柱子。一开始的时候，所有的盘子都按照大小顺序套在第一根柱子上，最大的盘子在底部，最小的盘子在顶部。目的是把所有的盘子都移动到第三根柱子上去，在必要的时候可以借助第二根柱子。我们每次只能移动一个盘子，但不能把较大的盘子放在较小的盘子上面。我们都知道这个问题的递归算法。由递归算法我们可以得到递推关系：M(n)=2M(n-1)+1当n1时M(n)=1当n=1时这里的M(n)代表n个盘子所需移动的次数。我们用反向替换法可以得到：M(n)=2M(n-1)+1=2[2M(n-2)+1]+1=22M(n-2)+2+1=22[M(n-3)+1]+2+1=22M(n-3)+22+2+1经过i次替换后：M(n)=2iM(n-i)+2i-1+2i-2+……+2+1=2iM(n-i)+2i-1因为初始条件是在n=1时确立的，所以令i=n-1,则M(n)=2n-1M(n-(n-1))+2n-1-1=2n-1M(1)+2n-1-1=2n-1因此我们知道对于问题规模为n的问题，时间效率最好为Θ(2n)，即我们所得的算法最好也是指数级的。若用递归会更低效，但我们必须承认递归简洁，易懂。我们现在手工模拟一下当n=5时的情况。设源柱子为A，辅助柱子为B，目标柱子为C，用A→B，表示从A柱子移动到B柱子。1:A→C2:A→B3:C→B4:A→C13:A→C14:A→B15:C→B16:A→C25:A→C26:A→B27:C→B28:A→C5:B→A6:B→C7:A→C8:A→B17:B→A18:B→C19:A→C20:B→A29:B→A30:B→C31:A→C9:C→B10:C→A11:B→A12:C→B21:C→B22:C→A23:B→A24:B→C我们分析这个表，找到其规律就可以解决汉诺塔问题。我们称这种方法为“改变表现”。所谓“改变表现”是指一个问题实例的表现改变为同样实例的另一种表现，它是变治思想的一种类型。从上面的移动过程中就很容易发现其规律。我们将上述过程四个分为一组，每一组的前三步移动循环出现且固定不变，而只有每一组中第四步移动改变。（这个规律只适用于当n为奇数的时候）。分析：我们用count表示移动的次数，初值为1；当n=1时，A→C。当n1时（n为奇数）a:count%12=1时，连续的三次移动一定为A→C，A→B，C→B，未知步。b:count%12=5时，连续的三次移动一定为B→A，B→C，A→C，未知步。c:count%12=9时，连续的三次移动一定为C→B，C→A，B→A，未知步。这样每次情况的前三步移动确定了，那么只要解决第四步怎样移动，问题就解决了。不管怎么样，移动的情况只有6种：①A→C②A→B③B→A④B→C⑤C→A⑥C→B在a情况时：我们可以排除的移动为⑥C→B，④B→C，③B→A，②A→B。（排除时考虑前三步移动后柱子上大小盘子就能判断出了）；所以第四步移动只能为①A→C或⑤C→A。同样我们可以判断出：在b情况时：第四步移动只能为②A→B或③B→A。在c情况时：第四步移动只能为⑥C→B或④B→C。我们还可以发现每次结束时，都是在b情况下的前三步走完的情况下。n=3时，最后三步B→A，B→C，A→C。n=5时，最后三步B→A，B→C，A→C。用数学归纳法证明：当n=2k+1(k=1,2,…..)时，(2n-1)%12=7成立。当k=1,2时，(2n-1)%12=7成立。假设当k=m时，(2n-1)%12=7也成立。那么：(22(m+1)+1-1)%12=(4×22m+1%12-1)%12=7所以，移动结束时肯定在b情况后。那么当n为偶数时，怎么办呢？同样n为偶数时，也存在相应规律，但不相同。为了简便，我们只需将C看成辅助柱子，B看成目标柱子，当Hanio(&A,&C,&B,n)调用完后，我们的目的也就实现了。注意n必须大于2，因为我们每一组都是四步，而n=2时只有3步。我编写的Hanio()对n=2时没做处理，我们将在主程序中完成。我们最后只要输出A和C柱子上的数，可是否逆序输出就可以了。（结果是正确的）总结：这种方法是最好的，要比用二叉树的方法节省大量的空间，比递归节省时间。所以这个算法无论从空间还是时间效率上，都是比较好的，只不过其规律难以发现。源程序：#includestdio.h#defineN20typedefstructcolumn{intplate[N];/*存放盘子号，从1开始*/inttop;/*指向最小的盘子*/}COLUMN;/*无条件移动，用于每一组的前三步*/voidMove_three(COLUMN*p,COLUMN*q){q-plate[++q-top]=p-plate[p-top--];/*p→q*/}/*用于第四步移动，只有两种可能，并且是互逆的*/voidMove_four(COLUMN*p,COLUMN*q){if(p-plate[p-top]q-plate[q-top])/*p→q*/q-plate[++q-top]=p-plate[p-top--];elseif(p-plate[p-top]q-plate[q-top])/*q→p***/p-plate[++p-top]=q-plate[q-top--];}/*仅当pa指向源柱子，pc指向目标柱子，且n为奇数*/voidHanio(COLUMN*pa,COLUMN*pb,COLUMN*pc,intn){intcount=1;intsum=1;for(count=1;count=n;count++)sum=sum*2;count=1;if(n==1)Move_three(pa,pc);elsewhile(countsum){if(count%12==1){Move_three(pa,pc);Move_three(pa,pb);Move_three(pc,pb);Move_four(pa,pc);}elseif(count%12==5){Move_three(pb,pa);Move_three(pb,pc);Move_three(pa,pc);/*判断是否还存在第四步*/if(count+3=sum-1)break;Move_four(pa,pb);}elseif(count%12==9){Move_three(pc,pb);Move_three(pc,pa);Move_three(pb,pa);Move_four(pb,pc);}count+=4;}}voidmain(){COLUMNA,B,C;inti,n,k;printf(请输入盘子数:);scanf(%d,&n);getchar();k=n;for(i=1;i=n;i++){A.plate[i]=k--;}A.top=n;B.top=C.top=0;A.plate[0]=B.plate[0]=C.plate[0]=100;/*赋于一个较大的数，主要方便Move_four().想一想为什么不能去掉**处的if条件*/for(i=0;i=n;i++)printf(%4d,A.plate[i]);if(n==2){Move_three(&A,&B);Move_three(&A,&C);Move_three(&B,&C);}elseif(n%2==1)Hanio(&A,&B,&C,n);elseHanio(&A,&C,&B,n);}参考文献：1：谭浩强，C语言程序设计（第二版），清华大学出版社2：（美）AnanyLevtin（著），潘彦译，算法设计与分析基础，清华大学出版社