1.先給出遞歸的算法
void fnHanoi(int n, char a, char b, char c)
{
if(n==0) return;
fnHanoi(n-1,a,c,b);
std::cout<<"第"<<n<<"個(gè)盤(pán)子從"<<a<<" 移動(dòng) "<<c<<std::endl;
fnHanoi(n-1,b,a,c);
}
#include <iostream>
using namespace std;
void fnHanoi(int m,int n){
int c,t,y;
for(t=n,y=t&1,c=m;y-1;t=t>>1,y=t&1,--c);//c表示層號(hào)
switch((c&1)*3+(t>>1)%3)//c&1奇偶判斷,t>1為層中序號(hào)
{
case 0:cout<<n<<"*:A - B"<<endl;break;
case 1:cout<<n<<"*:B - C"<<endl;break;
case 2:cout<<n<<"*:C - A"<<endl;break;
case 3:cout<<n<<"*:A - C"<<endl;break;
case 4:cout<<n<<"*:C - B"<<endl;break;
case 5:cout<<n<<"*:B - A"<<endl;break;
}
}
int main(){
int nMax=1,nDish,nMove=1;
cin>>nDish;
for(nMax<<=nDish;nMove<nMax;++nMove)
fnHanoi(nDish,nMove);
return 0;
}另外給出另一種非遞歸算法
算法介紹：
首先容易證明，當(dāng)盤(pán)子的個(gè)數(shù)為n時(shí)，移動(dòng)的次數(shù)應(yīng)等于2^n - 1。
一位美國(guó)學(xué)者發(fā)現(xiàn)一種出人意料的方法，只要輪流進(jìn)行兩步操作就可以了。
首先把三根柱子按順序排成品字型，把所有的圓盤(pán)按從大到小的順序放在柱子A上。
根據(jù)圓盤(pán)的數(shù)量確定柱子的排放順序：若n為偶數(shù)，按順時(shí)針?lè)较蛞来螖[放 A B C；
若n為奇數(shù)，按順時(shí)針?lè)较蛞来螖[放 A C B。
（1）按順時(shí)針?lè)较虬褕A盤(pán)1從現(xiàn)在的柱子移動(dòng)到下一根柱子，即當(dāng)n為偶數(shù)時(shí)，若圓盤(pán)1在柱子A，則把它移動(dòng)到B；
若圓盤(pán)1在柱子B，則把它移動(dòng)到C；若圓盤(pán)1在柱子C，則把它移動(dòng)到A。
（2）接著，把另外兩根柱子上可以移動(dòng)的圓盤(pán)移動(dòng)到新的柱子上。
即把非空柱子上的圓盤(pán)移動(dòng)到空柱子上，當(dāng)兩根柱子都非空時(shí)，移動(dòng)較小的圓盤(pán)
這一步?jīng)]有明確規(guī)定移動(dòng)哪個(gè)圓盤(pán)，你可能以為會(huì)有多種可能性，其實(shí)不然，可實(shí)施的行動(dòng)是唯一的。
（3）反復(fù)進(jìn)行（1）（2）操作，最后就能按規(guī)定完成漢諾塔的移動(dòng)。
最后就是用棧模擬遞歸算法,然后也可以實(shí)現(xiàn)非遞歸算法....
[如有錯(cuò)誤,請(qǐng)指出]