汉诺塔程序实验报告.doc

文档介绍：实验题目:
Hanoi塔问题
一、问题描述:
假设有三个分别命名为A,B和C的塔座,在塔座B上插有n个直径大小各不相同、从小到大编号为1,2,…,n的圆盘。现要求将塔座B上的n个圆盘移至塔座A上并仍按同样顺序叠排,圆盘移动时必须遵守以下规则:
(1)每次只能移动一个圆盘;
(2)圆盘可以插在A,B和C中任一塔上;
(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
要求:用程序模拟上述问题解决办法,并输出移动的总次数,圆盘的个数从键盘输入;并想办法计算出程序运行的时间。
算法思路:
1、建立数学模型:
这个问题可用递归法解决,并用数学归纳法又个别得出普遍解法:
假设塔座B上有3个圆盘移动到塔座A上:
(1)"将塔座B上2个圆盘借助塔座A移动到塔座C上;
(2)"将塔座B上1个圆盘移动到塔座A上;
(3)"将塔座C上2个圆盘借助塔座B移动到塔座A上。
其中第2步可以直接实现。第1步又可用递归方法分解为:
"将塔座B上1个圆盘从塔座X移动到塔座A;
"将塔座B上1个圆盘从塔座X移动到塔座C;
"将塔座A上1个圆盘从塔座Z移动到塔座C。
第3步可以分解为:
将塔座C上1个圆盘从塔座Y移动到塔座B;
将塔座C上1个圆盘从塔座Y移动到塔座A;
将塔座B上1个圆盘从塔座X移动到塔座A。
综上所述:可得到移动3个圆盘的步骤为
B->A,B->C, A->C, B->A, C->B, C->A, B->A,
2、算法设计:
将n个圆盘由B依次移到A,C作为辅助塔座。当n=1时,可以直接完成。否则,将塔座B顶上的n-1个圆盘借助塔座A移动到塔座C上;然后将圆盘B上第n个圆盘移到塔座A上;最后将塔座C上的n-1个圆盘移到塔座A上,并用塔座B作为辅助塔座。
三、原程序
#include<>
#include <>
#include <>
int times = 0;
void move(char a, char b)
{
printf("%c ----> %c \n", a,b);
}
void hno(int n,char a , char b, char c)
{
if (n==1)
{
move(a,c);
times ++;
}
else
{
hno(n-1,a,c,b);
move(a,c);
times ++;
hno(n-1,b,a,c);
}
}
void main()
{
unsigned start,finish;
int N;
printf("请输入汉诺塔的层数:");
scanf("%d",&N);
start=GetTickCount();//
hno(N,'B','C','A');
finish=GetTickCount();
float time=(finish-start)/;
printf("共移动了%d次! \n",times);
cout<<"总共需要时间为: "<<time<<endl;
}
四:

通过对上述递归在 Hanoi 塔问