文档介绍：一、实验目的
用回非递归方法解决汉诺塔问题。
二、算法原理
汉诺塔游戏,其规则如下:
,B,C。A杆上有若干碟子
,小的只能叠在大的上面
可以看出,当n=1时,直接将源柱上的盘子移到目标柱即可。当n大于等于2时,移动的过程可分解为三个步骤:
第一步  把A上的n-1个圆盘移到中间柱上;
第二步  把A上的一个圆盘移到目标柱上;
第三步  把B上的n-1个圆盘移到目标柱上。
最终以最大的盘子落到最初的目标柱上为目的,不断改变中间柱和目标柱,达到移动目的。此问题本身具有地归性,然而用非递归方法也是可以解决的。
三、算法描述(解决问题的步骤、流程图)
可以看出,当对于规模为n的hanoi,
1.  奇数编号盘子总是移动移动到它后的第2个柱子上
2.  偶数编号的盘子总是移动移动到它的后第1个柱子上
∴流程图如下:
Start
给每个盘子编号
End
Input n
初始化柱子和盘子状态
盘子号和 n同奇或同偶?
向右移动一位
移动
向右移动两位
源柱上当前盘子变为下一个
是否移动完?
是否无空柱?
找到柱顶盘子最小的柱子
找到该柱右边的柱子
四、实验环境
软件平台:windows XP SP3下,Visual C++
硬件平台:Inter® Core™ 2 Duo CPU
E4500 @ ,
五、实验过程及结果
六、结论(总结及下一步优化改进)
这个程序主要是根据这样的规律:如果把三个柱子围成一个环,盘子总数为N,其移动的规律是:如果N为偶数:奇数号盘每次2步;偶数号盘每次1步;如果N为奇数:奇数号盘每次1步;偶数号盘每次2步;当三个柱子都不为空则优先移动最小的盘子。
而这个规律,可以通过如下表格得出:
步
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1,2
1,2
1,2
1,2
1,2
1,2
1,2
1,2
1
2,1
2,1
2,1
2,1
2
1,2
1,2
3
2,1
七、附源代码
#include<>
#include<>
#define N 7
#define X dish[i].dnum
#define Y dish[i].lnum
#define SP dish[i].peg
int mov1(int,int);//向右走一步
int mov2(int,int);//向右走两步
struct dish
{
int dnum; //自身编号
int lnum; //下面的盘子
int peg; //所在的柱子
}dish[N];
int s[3]={N};//初始化每个柱的状态为空
void main()
{
int n;
int i,change=1,j;
for(i=0;i<N;i++)
{
dish[i].dnum=i; //作为盘子的唯一标识,顶层为0,最高级的最大盘子为N-1
dish[i].lnum=i+1; //底层