1 / 6
文档名称:

上机二 汉诺塔.doc

格式:doc   大小:44KB   页数:6页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

上机二 汉诺塔.doc

上传人:mh900965 2018/3/17 文件大小:44 KB

下载得到文件列表

上机二 汉诺塔.doc

文档介绍

文档介绍:上机二汉诺塔问题的实现及其优化
问题描述:
假设有三个分别命名为A、B、C的塔座,在塔座B上有n个直径大小各不相同、从小到大编号为1、2…,n的圆盘。现要求将塔座B上的n个圆盘移至塔座A上并按同样顺序叠放,当移动圆盘时应遵循下面规则:
每次只能移动一个圆盘;
圆盘可以放在A、B和C中的任一个上面;
任何时刻都不能将一个较大的圆盘压在较小的圆盘上。
算法思路:
为便于理解,先分析将B座上的三个盘子移动到A座上的过程如下:
B→A B→C A→C (B上的两个盘子移动到C上)
B→A (B上的一个盘子移动到A上)
C→B C→A B→A (C上的两个盘子移动到A上)
工经历7步。由此可推出:移动n个盘子要经历2^n-1步。如移动4个盘子要经历15步。
由上面分析可知:将n个盘子从B座移动到A座可以分解为以下3个步骤:
将B上n-1个盘借助A座先移到C座上
将B座上剩下的一个盘移动到A座上
将n-1个盘从C座借助于B座移动到A坐上
上边第一步和第三步都是吧n-1个盘从一个座移动到另一个座上,采取的办法是一样的,只是座的名字不同,为使之一般化,可以表示为:
将“one”座上n-1个盘移到:“two”座,对应关系是第一步one对B,two对C,three对A。第三步one对C,two对A,three对B。
因此,可以把上边3个步骤分成两类操作:
将n-1个盘从一个座移到另一个座上
将1个盘子从一个座上移到另一个座上
编写程序:
分别用两个函数实现以上的两类操作,用hanoi函数实现上面第1类操作,用move函数实现上面第2类操作,函数调用hanoi(你,one,two,three)表示将n个盘子从“one”座移到“three”座的过程。函数调用move(x,y)表示将1个盘子从x座移到y座的过程。x,y是代表A,B,C座之一,根据每次不同情况分别取A,B,C代入
#include<>
#include<>
#include<>

void do_something()
{
for(int i=0;i<100000;i++)
for(int j=0;j<10000;j++) ;
void hanoi(int n,char one,char two, char three);/*对hanoi函数的声明*/
int m;
int c;
printf("input the number of diskes");
scanf("%d",&m);
printf("The step to moveing %d diskes:\n\n",m);
hanoi(m,'B','C','A');
c= pow(2,m) -1; /*输出移动总次数*/
printf("\n移动的总次数为: %d \n",c);
}
void hanoi(int n, char one,char two,char three) /*定义hanoi函数*/
/*将n个盘从one座借助two座,移到three座*/
{