发布时间 : 星期日 文章数据结构课程设计报告 汉诺塔(081204112 黄露)更新完毕开始阅读
数据结构 课程设计材料
学生姓名： 黄露 学 号： 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 -
数据结构课程设计——汉诺塔的演示
一、设计目的
课程设计是《数据结构》课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。
二、设计要求
1．明确课设任务，复习与查阅有关资料。
2．按要求完成课设内容，课设报告要求文字和图工整、思路清楚、正确。 3．一至四名同学分为一组，完成一个应用问题的程序的编写工作。 4．应用程序应具有一定的可用性：
（1）凡等候用户输入时，给出足够的提示信息，如“Please Select（1—3）：”提示用户选择。 （2）格式明显易懂，配上适当的颜色、声音等辅助效果，能方便地改正输入时的错误，使用户感到方便、好用。
（3）有联机求助功能。用户能直接从系统得到必要的提示，不查手册也能解决一些疑难。 5．程序具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行： （1）对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。
（2）当可能的回答有多种时，应允许输入任何一种回答。 （3）对删除数据应给出警告。
三、需求分析
汉诺塔的由来：
汉诺塔是源自印度神话里的玩具。
- 2 -
数据结构课程设计——汉诺塔的演示
上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。 汉诺塔与宇宙寿命：
如果移动一个圆盘需要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小时x365天来算的话，大约有5800亿年吧。据说，现在的宇宙年龄大约是150亿年，还差得远呢。
言而总之，汉诺塔问题在数学界有很高的研究价值，而且至今还在被一些数学家们所研究也是我们所喜欢玩的一种益智游戏，它可以帮助开发智力，激发我们的思维。对汉诺塔还可以有进一步的研究。
- 3 -