汉诺塔》课程设计.doc

届课程设计汉诺塔课程设计说明书学生姓名 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 指导教师 教师职称 讲师 塔里木大学教务处制目录前言11. 数据结构简介12. 应用技术领域及范围13.设计的原理、方法和主要内容1正文21. 设计目的22. 设计要求23.需求分析23.1 汉诺塔的由来：23.2汉诺塔与宇宙寿命：34. 问题分析：45. 概要设计55.1设计思想55.2 实现方法55.3 主要模块55.4 模块关系56. 详细设计56.1 功能设计56.2 算法分析66.3 编写程序如下：66.4 程序执行过程分析：77. 调试分析：78.小结10致谢11参考文献11前言1. 数据结构简介数据结构是计算机程序设计的重要理论设计基础，它不仅是计算机学科的核心课程，而且成为其他理工专业的热门选修课。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。2. 应用技术领域及范围汉诺塔的应用技术是来自于我们所学的数据知识和数学方面的学科，其中用到了数学递归，函数和数据的函数以及C语言等方面的知识。汉诺塔的领域是在我的日常生活中的每一个细节中，反复的运用是我的数学知识在生活的体现，如做归一问题，循环问题，倒排问题，逻辑思维的相关问题等都要运用到我闷得汉诺塔原理。汉诺塔的范围来自每一个知识的指导，和生活中的运用。在我们的世界不是一成不变的，而是时时刻刻都在发生着变化，但一切的变化都没有脱离我们这个世界的规则。3.设计的原理、方法和主要内容 汉诺塔的设计原理是我们所学的数据结构与递归原理的应用，并且是在数据老师的指导下编写的源程序。得到了自己所设计的结果。汉诺塔的方法是把n个盘子从柱子1移到柱子3（利用柱子2），第一步，把n-1个盘子从柱子1移到柱子2（利用柱子3），第二步，把柱子1剩下的最大的盘子移到柱子3，第三步，把n-1个盘子从柱子2移到柱子3（利用柱子1）。每一个的移动都是所有的东西动，一个动就会把所有的逻辑打乱并且得不到所要测得结果。偏离我这此所设计的初终。汉诺塔的主要内容是经过不断地移动来挪去所有的盘子到指定的位置，递归原理的应用来解释了我所用的数据的知识。一个一个的去组织去协调，所有的设计不断地在循环到达一定的次数的到我这次所设计结果。正文1. 设计目的课程设计是数据结构课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。2. 设计要求1明确课设任务，复习与查阅有关资料。2按要求完成课设内容，课设报告要求文字和图工整、思路清楚、正确。3一至四名同学分为一组，完成一个应用问题的程序的编写工作。4应用程序应具有一定的可用性：（1）凡等候用户输入时，给出足够的提示信息，如“Please Select（13）：”提示用户选择。（2）格式明显易懂，配上适当的颜色、声音等辅助效果，能方便地改正输入时的错误，使用户感到方便、好用。（3）有联机求助功能。用户能直接从系统得到必要的提示，不查手册也能解决一些疑难。5程序具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行：（1）对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。（2）当可能的回答有多种时，应允许输入任何一种回答。（3）对删除数据应给出警告。3.需求分析3.1 汉诺塔的由来：汉诺塔是源自印度神话里的玩具。如下图：在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。 3.2汉诺塔与宇宙寿命：如果移动一个圆盘需要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次方减12个圆盘的时候 2的2次方减1 3个圆盘的时候 2的3次方减14个圆盘的时候 2的4次方减1 5个圆盘的时候 2的5次方减1 .n个圆盘的时候 2的n次方减1假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 264-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下， 18446744073709551615/31556952=584554049253.855年，这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。也就是说，n=64的时候是（2的64次方减1）次。因此，如果移动一个圆盘需要1秒的话，宇宙的寿命=2的64次方减1（秒）用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。据说，现在的宇宙年龄大约是150亿年，还差得远呢。言而总之，汉诺塔问题在数学界有很高的研究价值，而且至今还在被一些数学家们所研究也是我们所喜欢玩的一种益智游戏，它可以帮助开发智力，激发我们的思维。对汉诺塔还可以有进一步的研究。4. 问题分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但我们可以利用下面的方法来解决：设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：（1）以C盘为中介，从A杆将1至n-1号盘移至B杆；（2）将A杆中剩下的第n号盘移至C杆；（3）以A杆为中介，从B杆将1至n-1号盘移至C杆；这样，问题解决了，但实际操作中，只有第二步可直接完成，而第一、三步又成为移动的新问题。以上操作的实质是把移动n个盘子的问题转化为移动n-1个盘。那一、三步如何解决？事实上，上述方法：设盘子数为n，n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n-1个盘子从A杆移到B杆（第一步）或从B杆移到C杆（第三步）问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。依据该原理，层层递推，即可将原问题转化为解决移动n-2、n-33、2直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。至此，我们的任务算作是真正完成了。而这种由繁化简，用简单的问题和已知的操作运算来解决复杂问题的方法，就是递归法。在计算机设计语言中，用递归法编写的程序就是递归程序。5. 概要设计5.1设计思想如果盘子为1，则将这个盘子从塔座A移动到塔座C；如果不为1，则采用递归思想。将塔座A的前n-1个盘子借助C盘（即目的盘）移到塔座B，移后，此时C为空座，那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C，从而完成盘子的移动。5.2 实现方法通过数学函数的递归方法调用来实现。5.3 主要模块Main函数实现函数的调用，move函数实现输出，hanoi函数调用move函数实现移动和最终输出。5.4 模块关系程序从Main函数开始，到main函数结束。Main函数通过调用hanoi函数来实现盘子的移动，然后由move函数输出在屏幕上。6. 详细设计6.1 功能设计如果n=1，则将圆盘从A直接移动到C。如果n=2，则：(1)将A上的n-1（等于1）个圆盘移到B上；(2)再将A上的一个圆盘移到C上；(3)最后将B上的n-1（等于1）个圆盘移到C上。 如果n=3，则：A)将A上的n-1（等于2，令其为n）个圆盘移到B（借助于C），步骤如下：(1)将A上的n-1（等于1）个圆盘移到C上。(2)将A上的一个圆盘移到B。(3)将C上的n-1（等于1）个圆盘移到B。B)将A上的一个圆盘移到C。C)将B上的n-1（等于2，令其为n）个圆盘移到C（借助A），步骤如下：(1)将B上的n-1（等于1）个圆盘移到A。(2)将B上的一个盘子移到C。(3)将A上的n-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。 从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n-1个圆盘从一个针移到另一个针上，这里的n=n-1。6.2 算法分析本程序的主要算法是利用函数的递归调用算法。首先，想办法将A座上的前n-1个盘借助C座移动到B座上，然后将A组上的第n个盘移动到C座上。然后再将B座上的n-1个盘借助A座移动到C座上，此次移动也和第一次移动一样，重复递归，直到最后一个盘为止。 6.3 编写程序如下：#include void main()void hanoi(int n,char one,char two,char three );/*对hanoi函数进行生声明*/int m;printf(Please input the number of diskes:n);scanf(%d,&m);printf(The step to moving %d diskes :n,m);hanoi(m,A,B,C);getch();void hanoi(int n,char one,char two,char three) /*定义hanoi函数*/ /*将n个盘从one座借助two座移到three座*/void move(char x,char y); /*对move函数的声明*/if(n=1) move(one ,three); else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x,char y) /*定义move函数*/ printf(%c-%cn,x,y); getch(); return 0; 6.4 程序执行过程分析：如图分析7. 调试分析：代码敲完后，先进行调试分析，找出程序中是否有错。结果显示当前程序出错，需要返回检查。认真分析，可以看到，main函数在调用hanoi函数之前没有对hanoi函数进行声明，所以编译显示出错。接下来就是修改，对hanoi函数先进行声明：加上这行声明后再进行调试程序敲完了，发现运行后速度很快，还没看清结果就结束了。因此，要在main函数最后加一个getch（）函数，此函数的功能是停留运行时间，按任意键继续，使用户能够看到运行结果。因为CPU的运算速度太快了，如果没有这个函数，则会在运行的时候还没能看到结果就退出程序了。加上getch函数之后，好了，编译成功了，现在就可以测试一下结果是否满足要求了。可以看到，结果显示在屏幕上是正确的，设计完成。8.小结通过这次课程设计，增加了我学习软件技术的兴趣，虽然还不明确软件技术包含的具体内容，但从C语言这门课程开始，到数据结构，研究算法的特性，已发现程序设计的乐趣，在学习数据结构的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个大体的了解。 这次课程设计是通过我们一个小组的努力所实现的要求。在实际操作过程中犯的一些错误还会有意外的收获，感觉很有意思。在具体操作中对这学期所学的数据结构的理论知识得到巩固，达到设计的基本目的，也发现自己的不足之处，在以后的上机中应更加注意，同时体会到算法应具有的语句简洁，简单易懂，可读性高，使用灵活，执行效率高等特点。发现上机实训的重要作用，特别是对函数的递归调用有了深刻的理解。 通过实际操作，学会分析问题，解决