数据结构课程设计报告 汉诺塔(081204112 黄露)
- 格式:doc
- 大小:732.50 KB
- 文档页数:14
数据结构
课程设计材料
学生姓名:黄露学号: 081204112 系 (院):信息工程学院
专业:信息管理与信息系统
设计(论文)题目: 汉诺塔的演示
完成日期: 2010年3月
指导教师: 朱俊武
2010年3月
目录
1.设计目的 (2)
2.设计要求 (2)
3.需求分析 (2)
4.概要设计 (4)
5.详细设计 (4)
6.调试分析 (4)
7.用户手册 (8)
8.测试结果 (10)
9.附录 (11)
10.参考文献 (12)
一、设计目的
课程设计是《数据结构》课程教学必不可缺的一个重要环节,它可加深学生对该课程所学内容的进一步的理解与巩固,是将计算机课程与实际问题相联接的关键步骤。通过课程设计,能够提高学生分析问题、解决问题,从而运用所学知识解决实际问题的能力,因而必须给予足够的重视。
二、设计要求
1.明确课设任务,复习与查阅有关资料。
2.按要求完成课设内容,课设报告要求文字和图工整、思路清楚、正确。
3.一至四名同学分为一组,完成一个应用问题的程序的编写工作。
4.应用程序应具有一定的可用性:
(1)凡等候用户输入时,给出足够的提示信息,如“Please Select(1—3):”提示用户选择。(2)格式明显易懂,配上适当的颜色、声音等辅助效果,能方便地改正输入时的错误,使用户感到方便、好用。
(3)有联机求助功能。用户能直接从系统得到必要的提示,不查手册也能解决一些疑难。5.程序具有一定的健壮性,不会因为用户的输入错误引起程序运行错误而中断执行:(1)对输入值的类型、大小范围、字符串的长度等,进行正确性检查,对不合法的输入值给出出错信息,指出错误类型,等待重新输入。
(2)当可能的回答有多种时,应允许输入任何一种回答。
(3)对删除数据应给出警告。
三、需求分析
汉诺塔的由来:
汉诺塔是源自印度神话里的玩具。
上帝创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着6 4片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。
汉诺塔与宇宙寿命:
如果移动一个圆盘需要1秒钟的话,等到64个圆盘全部重新落在一起,宇宙被毁灭是什么时候呢?
让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次,2个的时候是3次,3个的时候就用了7次......这实在是太累了
因此让我们逻辑性的思考一下吧。
4个的时候能够移动最大的4盘时如图所示。
到此为止用了7次。
接下来如下图时用1次,在上面再放上3个圆盘时还要用7次(把3个圆盘重新放在一起需要的次数)。
因此,4个的时候是
“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”
=2x“3个圆盘重新摞在一起的次数”+1次
=15次。
那么,n个的时候是
2x“(n-1)个圆盘重新摞在一起的次数”+1次。
由于1 个的时候是1次,结果n个的时候为(2的n次方减1)次。
1个圆盘的时候2的1次方减1
2个圆盘的时候2的2次方减1
3个圆盘的时候2的3次方减1
4个圆盘的时候2的4次方减1
5个圆盘的时候2的5次方减1
........
n个圆盘的时候2的n次方减1
也就是说,n=64的时候是(2的64次方减1)次。因此,如果移动一个圆盘需要1秒的话,宇宙的寿命=2的64次方减1(秒)用一年=60秒x60分x24小时x36 5天来算的话,大约有5800亿年吧。据说,现在的宇宙年龄大约是150亿年,还差得远呢。
言而总之,汉诺塔问题在数学界有很高的研究价值,而且至今还在被一些数学家们所研究也是我们所喜欢玩的一种益智游戏,它可以帮助开发智力,激发我们的思维。对汉诺塔还可以有进一步的研究。
四、概要设计
1、设计思想
如果盘子为1,则将这个盘子从塔座A移动到塔座C;
如果不为1,则采用递归思想。
将塔座A的前n-1个盘子借助C盘(即目的盘)移到塔座B,移后,此时C为空座,那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C,从而完成盘子的移动。
2、实现方法
通过函数的递归调用来实现。
3、主要模块
Main函数实现函数的调用,move函数实现输出,hanoi函数调用move函数实现移动和最终输出。
4、模块关系
程序从Main函数开始,到main函数结束。Main函数通过调用hanoi函数来实现盘子的移动,然后由move函数输出在屏幕上。
五、详细设计
1、功能设计
本程序的功能是建立一个汉诺塔模型,简化用户使用过程,便于用户直接查看一定的汉诺塔数据对应的移动步骤。
2、算法分析
本程序的主要算法是利用函数的递归调用算法。首先,想办法将A座上的前n-1个盘借助C 座移动到B座上,然后将A组上的第n个盘移动到C座上。然后再将B座上的n-1个盘借助A座移动到C座上,此次移动也和第一次移动一样,重复递归,直到最后一个盘为止。
六、调试分析
代码敲完后,先进行调试分析,找出程序中是否有错。
结果显示当前程序出错,需要返回检查。认真分析,可以看到,main函数在调用hanoi函数之前没有对hanoi函数进行声明,所以编译显示出错。
接下来就是修改,对hanoi函数先进行声明: