漢諾塔問題非遞歸算法詳解

MakeByMr.Cai思路介紹：

首先，可證明，當(dāng)盤子的個數(shù)為n時，移動的次數(shù)應(yīng)等于2^n-1。

然后，把三根樁子按一定順序排成品字型（如：），再把所有的圓盤按至上而下是從小到大的順序放在樁子A上。

接著，根據(jù)圓盤的數(shù)量確定樁子的排放順序：若n為偶數(shù)，按順時針方向依次擺放；若n為奇數(shù)，按順時針方向依次擺放。最后，進行以下步驟即可：（1）首先，按順時針方向把圓盤1從現(xiàn)在的樁子移動到下一根樁子，即當(dāng)n為偶數(shù)時，若圓盤1在樁子A，則把它移動到B；若圓盤1在樁子B，則把它移動到C；若圓盤1在樁子C，則把它移動到A。

（2）接著，把另外兩根樁子上可以移動的圓盤移動到新的樁子上。

即把非空樁子上的圓盤移動到空樁子上，當(dāng)兩根樁子都非空時，移動較小的圓盤。（3）重復(fù)（1）、（2）操作直至移動次數(shù)為2^n-1。#include<iostream>#include<cmath>usingnamespacestd;#defineCap64classStake//表示每樁子上的情況{public: Stake(intname,intn) { this->name=name; top=0; s[top]=n+1;/*假設(shè)樁子最底部有第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()//獲取當(dāng)前樁子的編號 { returnname; }private: ints[Cap+1];//表示每根樁子放盤子的最大容量 inttop,name; Stake*next;};voidmain(){ intn; voidhanoi(int,int,int,int); cout<<"請輸入盤子的數(shù)量："; cin>>n; if(n<1) cout<<"輸入的盤子數(shù)量錯誤!!!"<<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