1 #include <iostream> 2 #include <stack> 3 #include <assert.h> 4 using namespace std; 5 6 class HANOI 7 { 8 private: 9 struct HanioData{ 10 int x;//所在盘子编号 11 int y;//移动后所在编号 12 int n;//盘子数 13 }; 14 HanioData hd; 15 static int c; 16 stack<HanioData> m_stack; 17 inline void move(int x,int z,int n)const 18 { 19 cout<<"第"<<c++<<"步: 将"<<n<<"号盘从"<<x<<"座移动到"<<z<<"座"<<endl; 20 } 21 public: 22 //递归实现 23 void hanoi(int n,int x,int y,int z)const 24 { 25 if(n==1) 26 move(x,z,1); 27 else 28 { 29 hanoi(n-1,x,z,y); 30 move(x,z,n); 31 hanoi(n-1,y,x,z); 32 } 33 } 34 //非递归实现 35 void hanoi(int n,int x,int y) 36 { 37 assert(n>0&&x>0&&y>0&&y<4&&x!=y); 38 hd.n=n; 39 hd.x=x; 40 hd.y=y; 41 c=0; 42 while (hd.n||!m_stack.empty()) 43 { 44 while(hd.n) 45 { 46 hd.n--; 47 m_stack.push(hd); 48 hd.y^=hd.x; 49 } 50 if(!m_stack.empty()) 51 { 52 hd=m_stack.top(); 53 m_stack.pop(); 54 move(hd.x,hd.y,hd.n+1); 55 hd.x^=hd.y; 56 } 57 } 58 59 } 60 }; 61 62 int HANOI::c = 0; 63 64 int main() 65 { 66 HANOI H; 67 int n; 68 int p[3] = {1,2,3}; 69 cout<<"3个塔座为"<<p[0]<<" "<<p[1]<<" "<<p[2]<<",目的:从"<<p[0]<<"座移动到"<<p[2]<<"座。请输入圆盘数:"; 70 cin>>n; 71 cout<<"递归求解:"<<endl; 72 H.hanoi(n,p[0],p[1],p[2]); 73 cout<<"非递归求解:"<<endl; 74 H.hanoi(n,p[0],p[2]); 75 76 return 0; 77 }