汉诺塔实验报告.doc

《汉诺塔实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计2012年12月21日目录1、概述42、实验目的43、问题分析54、实验步骤55、流程图66、程序代码：77、程序调试与测试108、结论129、总结15一、概述数据结构是计算机学科非常重要的一门专业基础理论课程，要想编写针对非数值计算问题的高质量程序，就必须要熟练的掌握这门课程设计的知识。另外，他与计算机其他课程都有密切联系，具有独特的承上启下的重要位置。拥有《数据结构》这门课程的知识准备，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程的都是有益的。二、实验目的通过本实验，掌

2、握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。三、问题分析任务：有三个柱子A,B,C.A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1,2,...,n编号。要求借助柱子B，把柱子A上的所有的盘子移动到柱子C上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。分析：首先容易证明，当盘子的个数为n时，移动的次数应等于2^n-1。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量

3、确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放ABC；若n为奇数，按顺时针方向依次摆放ACB。（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。反复进行（1）

4、（2）操作，最后就能按规定完成汉诺塔的移动。四、实验步骤1、用c++或c语言设计实现汉诺塔游戏；,2、让盘子数从2开始到7进行实验，记录程序运行时间和递归调用次数；3、画出盘子数n和运行时间t、递归调用次数m的关系图，并进行分析。五、流程图开始输入m（m<=20）是否继续结束输出结果2、否1、是六、程序代码：#include#include//Hanoi塔classHanoi{public:Hanoi(){cout<<"请输入你想玩的层数(1-20)：";in

5、put:cin>>floor;if(floor<1

6、

7、floor>20){cout<<"层数错误重新输入：";gotoinput;}cout<

8、r(inti=0;i

9、("cls");cout<<"第"<

10、=0;i