汉诺塔实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
实 验 报 告
课程名称 数据结构 实验名称 汉诺塔 实验类型 验证性实验 实验地点 计304机房 实验日期 指导教师 魏海平
专业 计算机科学与技术
班级 计算机1002
学号 20
姓名 张森
辽宁石油化工大学计算机与通信工程学院
数据结构实验报告评分表
项目 要求 分数 有无项目(?) 得分
实验目的明确 5
实验内容理解透彻 5 预习报告
实验
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
程序总体框架设计完整 10 (30分)
设计完整完成相关辅助代码 5
合理 测试方案合理 5
发现问题 5 实验过程
问题的分析 15 (30分)
问题的解决方法 10
内容翔实无缺漏 5 实验报告
如实
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
实验过程 10 (20分)
撰写规整 5
实验结果的分析 5 实验总结
(10分) 按照结果对原实验方案的改进意见 5
实验的收获 5 实验体会
(10分) 实验内容的发散考虑 5 总分
1.实验目的:
通过本实验,掌握复杂性问题的分析方法,了解汉诺塔游戏的时间复杂性和空间复杂性。 2.问题描述:
汉诺塔问题来自一个古老的传说:在世界刚被创建的时候有一座钻石宝塔(塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔(塔B和塔C)。从世界创始之日起,婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去,其间借助于塔B的帮助。每次只能移动一个碟子,任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时,世界末日也就到了。
3.算法设计思想:
对于汉诺塔问题的求解,可以通过以下三个步骤实现:
(1)将塔A上的n-1个碟子借助塔C先移到塔B上。
(2)把塔A上剩下的一个碟子移到塔C上。
(3)将n-1个碟子从塔B借助于塔A移到塔C上。
4.实验步骤:
1. 用c++ 或c语言设计实现汉诺塔游戏;
2. 让盘子数从2 开始到7进行实验,记录程序运行时间和递归调用次数;
3. 画出盘子数n和运行时间t 、递归调用次数m的关系图,并进行分析。
实验内容及实验结果
请写出具体的实验步骤,并给出相应的实验结果,附上编写的程序及其运行结果截图!!
#include
void hanio(int n,char A,char B,char C)
{
if (n==1) printf("Move disk from %c to %c\n",A,B);
else{
hanio(n-1,A,C,B);
printf("Move disk from %c to %c\n",A,B);
hanio(n-1,C,B,A);}
}
void main()
{
int n;
printf("input the number of disk:");
scanf("%d",&n);
printf("the steps for %d disk are:\n",n);
hanio(n,'A','B','C');
}
运行结果:
7、结论
通过对上述递归在Hanoi塔问题上的应用分析,我们可以得出如下结论:
1、递归调用过程中,在程序执行之前无法知道控制这种调用栈的规模,因为这一规模取决于递归调用的次序。在这种情况下,程序的地址空间可能动态变化;
2、递归应用于程序设计时,结构清晰、程序易读,编制和调试程序很方便,不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源(包括堆栈、软中断和存贮空间等),并消耗大量处理时间。因此,可以考虑采用并行计算进行处理,但
3、递归是串行的,其第n步运算依赖于第n-1步运算,所以在计算机软件理论上不存在递归问题并行计缓存大小 算的可能性。实际上是否存在并行递归计算有待进一步探讨。
8、总结
通过对汉诺塔算法的分析让我更清楚的认识到了不同的算法对程序性能的影响,也让我明白掌握了算法将会有助于提高软件的开发。