文档介绍：Make By
思路介绍:
首先,可证明,当盘子的个数为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>
using namespace std;
#define Cap 64
class Stake //表示每桩子上的情况
{
public:
Stake(int name,int n)
{
this->name=name;
top=0;
s[top]=n+1;/*假设桩子最底部有第n+1个盘子,即s[0]=n+1,这样方便下面进行操作*/
}
int Top()//获取栈顶元素
{
return s[top];//栈顶
}
int Pop()//出栈
{
return s[top--];
}
void Push(int top)//进栈
{
s[++this->top]=top;
}
void setNext(Stake *p)
{
next=p;
}
Stake *getNext()//获取下一个对象的地址
{
return next;
}
int getName()//获取当前桩子的编号
{
return name;
}
private:
int s[Cap+1];//表示每根桩子放盘子的最大容量
int top,name;
Stake *next;
};
void main()
{
int n;
void hanoi(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);
}
}
void hanoi(const int n,int A,int B,int C)
{
Stake a(A,n),b(B,n),c(C,n);
Stake *p,