汉诺塔问题非递归算法详解汇总.doc

汉诺塔问题非递归算法详解汇总
汉诺塔问题非递归算法详解汇总
1/2
汉诺塔问题非递归算法详解汇总

思路介绍：
第一，可证明，当盘子的个数为 n时，搬动的次数应等于 2^n-1汉诺塔问题非递归算法详解汇总
汉诺塔问题非递归算法详解汇总
1/2
汉诺塔问题非递归算法详解汇总

思路介绍：
第一，可证明，当盘子的个数为 n时，搬动的次数应等于 2^n-1。
尔后，把三根桩子按必然序次排成品字型（如：），再把全部的圆盘按至上而下是..C
从小到大的序次放在桩子 A上。
接着，依据圆盘的数目确立桩子的排放序次：
若n为偶数，；..C若n为奇数，。..B
最后，进行以下步骤即可：
（1）第一，按顺时针方向把圆盘1从现在的桩子搬动到下一根桩子，即当n为偶数时，若圆盘1在桩子A，则把它搬动到B；若圆盘1在桩子B，则把它搬动到C；若圆盘1在桩子C，则把它搬动到A。
（2）接着，把别的两根桩子上可以搬动的圆盘搬动到新的桩子上。
即把非空桩子上的圆盘搬动到空桩子上，当两根桩子都非空时，搬动较小的圆盘。
（3）重复（1）、（2）操作直至搬动次数为 2^n-1。
#include<iostream>
#include<cmath>
usingnamespacestd;
#defineCap64
classStake//表示每桩子上的状况
{
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)//进栈{}{next=p;}Stake*getNext( )//获得下一个对象的地址
{returnnext;s[++this->top]=top;voidsetNext(Stake*p)}intgetName( )//获得当前桩子的编号{returnname;
}
private:
ints[Cap+1];//表示每根桩子放盘子的最大容量
inttop,name;Stake*next;
};
voidmain( )
{
}
voidhanoi(constintn,intA,intB,intC)
{
Stakea(A,n),b(B,n),c(C,n);intn;voidhanoi(int,int,int,int);cout<<"请输入盘子的数目：";cin>>n;if(n<1)cout<<"输入的盘子数目错误!!!"<<endl;else{}cout<<"搬动"<<n<<"个盘子的步骤以下："<<endl;if(