实验题目：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步又可用递归方法分解为：1.1"将塔座B上1个圆盘从塔座X移动到塔座A；1.2"将塔座B上1个圆盘从塔座X移动到塔座C；1.3"将塔座A上1个圆盘从塔座Z移动到塔座C。第3步可以分解为：3.1将塔座C上1个圆盘从塔座Y移动到塔座B；3.2将塔座C上1个圆盘从塔座Y移动到塔座A；3.3将塔座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#includeinttimes=0;voidmove(chara,charb){printf("%c---->%c\n",a,b);}voidhno(intn,chara,charb,charc){if(n==1){move(a,c);times++;}else{hno(n-1,a,c,b);move(a,c);times++;hno(n-1,b,a,c);}}voidmain(){unsignedstart,finish;intN;printf("请输入汉诺塔的层数：");scanf("%d",&N);start=GetTickCount();//hno(N,'B','C','A');finish=GetTickCount();floattime=(finish-start)/1000.0;printf("共移动了%d次!\n",times);cout<<"总共需要时间为："<
