上机二 汉诺塔.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代入 #includestdio.h #includemath.h #includetime.h void do_something() { for(int i=0;i100000;i++) for(int j=0;j10000;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座*/ { void move(char x,char y); /*对move函数的声明*/ if(n==1) move(one,three); else { hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } void move(char x,char y) /*定义move函数*/ { printf(%c--%c\n,x,y);; } int main(int arg,char ** argv) /*计算程序运行时间*/ { clock_t start=clock(); do_something(); clock_t end=clock(); float time=(float)(end-start)/CLOCKS_PER_SEC; printf(程序运行总时间 : %f\n,time); return 0; } 测试数据： 结论分析 在本程序中move函数并未真正移动盘子，而只是输出移动的方案（从哪一个座移动到哪一个座）。 计算本程序的运行时间是指从打开该