递归方法就是通常的方法。
非递归方法是：
循环移动最小的盘子，然后再移动不包括最小盘子的两根杆上的盘子（比较大小），直到结束。根据移动盘子个数是奇数或偶数确定先移动到那个杆上，是123循环，还是321循环，详情见程序。
// Hanoi.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream.h>
#include <stack>
#include <map>
using namespace std;
void Move(int nFrom,int nTo);
void Hanoi1(int nNums,int nFrom,int nThrough,int nTo);
void Hanoi2(int nNums,int nFrom,int nThrough,int nTo);
int main(int argc, char* argv[])
{
cout<<"begining...."<<endl;
Hanoi1(4,1,2,3);
cout<<"begining2...."<<endl;
Hanoi2(4,1,2,3);
return 0;
}
void Move(int nFrom,int nTo)
{
cout<< "move from peg "<<nFrom << " to peg " << nTo << endl;
}
void Hanoi1(int nNums,int nFrom,int nThrough,int nTo)
{
if(1==nNums) {
Move(nFrom,nTo);
}
else {
Hanoi1(nNums-1,nFrom,nTo,nThrough);
Move(nFrom,nTo);
Hanoi1(nNums-1,nThrough,nFrom,nTo);
}
}
void Hanoi2(int nNums,int nFrom,int nThrough,int nTo)
{
stack<int> peg[3];
map<int,int> amap;
amap.insert(map<int,int>::value_type(0,nFrom));
amap.insert(map<int,int>::value_type(1,nThrough));
amap.insert(map<int,int>::value_type(2,nTo));
int i;
for(i=nNums;i>=1;i--) peg[0].push(i);
int nDirection=(nNums % 2)?-1:1;
bool bSmallMove=true;
int nSmallest=0;
int nSmallestNext;
while (peg[2].size()!=nNums)
{
if (bSmallMove)
{
nSmallestNext=(nSmallest+nDirection+3) % 3;
peg[nSmallest].pop();
peg[nSmallestNext].push(1);
Move(amap[nSmallest],amap[nSmallestNext]);
nSmallest=nSmallestNext;
}
else
{
int k,indice[2],count;
count=0;
for(k=0;k<3;k++)
{
if (peg[k].empty()) {
indice[count]=k;
count++;
continue;
}
if (peg[k].top()==1) continue;
indice[count]=k;
count++;
}
if( !( peg[indice[0]].empty() || peg[indice[1]].empty() ) )
{
if (peg[indice[0]].top()>peg[indice[1]].top())
{
k=indice[0];
indice[0]=indice[1];
indice[1]=k;
}
}
else if (peg[indice[0]].empty())
{
k=indice[0];
indice[0]=indice[1];
indice[1]=k;
}
k=peg[indice[0]].top();
peg[indice[0]].pop();
peg[indice[1]].push(k);
Move(amap[indice[0]],amap[indice[1]]);
}
bSmallMove=!bSmallMove;
} //while
}