文档介绍：汉诺塔问题非递归算法详解汇总
汉诺塔问题非递归算法详解汇总
1 / 2
汉诺塔问题非递归算法详解汇总
Make By
思路介绍：
首先，可证明，当盘子的个数为 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>
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)// 进栈 { } { next=p; } Stake *getNext()// 获取下一个对象的地址
{ return next; s[++this->top]=top; void setNext(Stake *p) } int getName()// 获取当前桩子的编号 { return name;
}
private:
int s[Cap+1];//表示每根桩子放盘子的最大容量
int top,name; Stake *next;
};
void main()
{
}
void hanoi(const int n,int A,int B,int C)
{
Stake a(A,n),b(B,n),c(C,n); 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);