汉诺塔问题非递归算法详解

MakeByMr.Cai思路介绍：

首先，可证明，当盘子的个数为n时，移动的次数应等于2^n-1。

然后，把三根桩子按一定顺序排成品字型（如：），再把所有的圆盘按至上而下是从小到大的顺序放在桩子A上。

接着，根据圆盘的数量确定桩子的排放顺序：若n为偶数，按顺时针方向依次摆放；若n为奇数，按顺时针方向依次摆放。最后，进行以下步骤即可：（1）首先，按顺时针方向把圆盘1从现在的桩子移动到下一根桩子，即当n为偶数时，若圆盘1在桩子A，则把它移动到B；若圆盘1在桩子B，则把它移动到C；若圆盘1在桩子C，则把它移动到A。

（2）接着，把另外两根桩子上可以移动的圆盘移动到新的桩子上。

即把非空桩子上的圆盘移动到空桩子上，当两根桩子都非空时，移动较小的圆盘。（3）重复（1）、（2）操作直至移动次数为2^n-1。#include<iostream>#include<cmath>usingnamespacestd;#defineCap64classStake//表示每桩子上的情况{public: Stake(intname,intn) { this->name=name; top=0; s[top]=n+1;/*假设桩子最底部有第n+1个盘子，即s[0]=n+1，这样方便下面进行操作*/ } intTop()//获取栈顶元素 { returns[top];//栈顶 } intPop()//出栈 { returns[top--]; } voidPush(inttop)//进栈 { s[++this->top]=top; } voidsetNext(Stake*p) { next=p; } Stake*getNext()//获取下一个对象的地址 { returnnext; } intgetName()//获取当前桩子的编号 { returnname; }private: ints[Cap+1];//表示每根桩子放盘子的最大容量 inttop,name; Stake*next;};voidmain(){ intn; voidhanoi(int,int,int,int); cout<<"请输入盘子的数量："; cin>>n; if(n<1) cout<<"输入的盘子数量错误!!!"<<endl; else { cout<<"移动"<<n<<"个盘子的步骤如下："<<endl; if(n%2) hanoi(n,1,3,2); else hanoi(n,1,2,3); }}voidhanoi(constintn,intA,intB,intC){ Stakea(A,n),b(B,n),c(C,n); Stake*p,*ptr1,*ptr2,*pt; inti,temp,max=pow(2,n)-1; for(i=0;i<n;i++)//把n个盘子按顺序放在A桩子上 a.Push(n-i); a.setNext(&b); b.setNext(&c);//将3个桩子连在一起，就如同链表 c.setNext(&a); for(i=0,p=&a;i<max;i++)//此处打印盘子的移动步骤 { if(i%2) { ptr1=p->getNext(); ptr2=ptr1->getNext(); if(ptr1->Top()<ptr2->Top()) { pt=ptr1; ptr1=ptr2; ptr2=pt; } ptr1->Push(ptr2->Pop()); cout<<ptr2->getName()<<"-->" <<ptr1->getName()<<endl; } else { temp=p->Pop(); cout<<p->g