文档介绍：实验题目:Hanoi塔问题一、问题描述:假设有三个分别命名为A,B和C的塔座,在塔座B上插有n个直径大小各不相同、从小到大编号为1,2,…,n的圆盘。现要求将塔座B上的n个圆盘移至塔座A上并仍按同样顺序叠排,圆盘移动时必须遵守以下规则:每次只能移动一个圆盘;圆盘可以插在A,B和C中任一塔上;任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。要求:用程序模拟上述问题解决办法,并输出移动的总次数,圆盘的个数从键盘输入;并想办法计算出程序运行的时间。二、算法思路:1、建立数学模型:这个问题可用递归法解决,并用数学归纳法又个别得出普遍解法:假设塔座B上有3个圆盘移动到塔座A±:〃将塔座B上2个圆盘借助塔座A移动到塔座C上;〃将塔座B上1个圆盘移动到塔座A上;〃将塔座C上2个圆盘借助塔座B移动到塔座A上。其屮笫2步可以直接实现。笫1步又可用递归方法分解为:〃将塔座B上1个圆盘从塔座X移动到塔座A;〃将塔座B上1个圆盘从塔座X移动到塔座C;3〃将塔座A上1个圆盘从塔座Z移动到塔座Co第3步可以分解为:;;:可得到移动3个圆盘的步骤为B->A,B->C,A->C,B->A,C->B,C->A,B->A,2、算法设计:将n个圆盘rflB依次移到A,C作为辅助塔座。当n二1时,可以直接完成。否则,将塔座B顶上的n-1个圆盘借助塔座A移动到塔座C上;然后将圆盘B上第n个圆盘移到塔座A上;最后将塔座C上的n-l个圆盘移到塔座A上,并用塔座B作为辅助塔座。三、原程序#include<>#include<>#include<>inttimes=0;voidmove(chara,charb){printf("%c---->%c\n",a,b);}voidhno(intn,chara,charb,charc)if(n==l)move(a,c);times++;}else{hno(n-l,a,c,b);move(a,c);times++;hno(n-l’bac);}}voidmain(){unsignedstart,finish;intN;printf("请输入汉诺塔的层数:");scanf(H%d",&N);start=GetTickCount();//hnoJN/BVC'/A*);finish=GetTickCount();floattime=(finish-start)/;printf("共移动了%d次!\n",times);coutvv”总共需要时间为:"«time«endl;}四:Ac若又-冃吉->->事鹫舉腐霜务0-016^ressitnykeytocont;,可以得出如下结论:递归应用中的Hanoi塔问题分析递归应用中的1、Hanoi塔问题中函数调用时系统所做工作一个函数在运行期调用