C语言课程设计（论文）汉诺塔演示程序设计

《C语言课程设计（论文）汉诺塔演示程序设计》由会员分享，可在线阅读，更多相关《C语言课程设计（论文）汉诺塔演示程序设计（20页珍藏版）》请在装配图网上搜索。

1、本科计算机图形学课程设计 玻璃切割优化方案算法设计攀枝花学院学生课程设计（论文）题 目： 汉诺塔演示程序设计 学生姓名： 学 号: 所在院（系）： 计算机学院 专 业： 计算机科学与技术 班 级： 04计本3班 指 导 教 师： 职称： 硕士 2007年7月12日攀枝花学院教务处制1攀枝花学院本科学生课程设计任务书题目汉诺塔演示程序设计1、课程设计的目的1、通过课程设计，加深对图形学算法设计思想的理解，并掌握用C语言及Tc2.0进行简单的开发和设计.2、通过算法的设计，学会从具体问题抽象出数学模型，并能够用程序设计语言描述出来，用计算方法来求解3、学习一些基本的数据结构及算法思想，比如排序以及

2、链表的基本操作在C环境中的实现。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）1、能够对经典问题汉诺塔进行进求解，给出解决方案，要求正确，并按比例画出图形。2、对用户输入的盘子个数（不少于5个）进行相应的求解，获得移动盘子的方案，并用图形动画演示。3、演示过程中允许用户在任意时刻中断演示。以避免上时间的无意义等待。3、主要参考文献1 潘云鹤，董金祥等计算机图形学原理、方法及应用M高等教育出版社，20032 孙家广等，计算机图形学（第三版）M.清华大学出版社,20043 陈元琰编著计算机图形学实用技术M北京：科学出版社，20004 和青芳著计算机图形学原理及算法教程M北京：清华大

3、学出版社5 陆润民.C语言绘图教程.北京：清华大学出版社M.19964、课程设计工作进度计划1)19周星期一，选课题2)19周星期二15周星期三，查找参考书3)19周星期四16周星期二，代码编写4)20周星期三16周星期四，写论文5) 20周星期五检查材料和程序结果指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）： 接受任务时间： 2007年 7月2日 课程设计（论文）指导教师成绩评定表题目名称评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关

4、的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能力水平35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。06设计（实验）能力，方案的设计能力5能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析能力

5、（综合分析能力、技术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成果质量45%09插图（或图纸）质量、篇幅、设计（论文）规范化程度5符合本专业相关规范或规定要求；规范化符合本文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名： 年月日II攀枝花学院本科课程设计（论文） 摘 要 摘 要汉诺塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个圆的金

6、片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。传说固然只是传说，这个古老的故事到今天又引申出一连串的包括统筹、管理等等数学问题。在现实生活中，任何一个人都不可能直接写出移动盘子的每一个具体步骤。比较经典的使用递归算法也是在这方面做了大量研究得出的一种相对优化的算法方案。本文主要从图形学的角度对这个问题作了一些简单的探讨。整个程序采用了自顶向下，逐步细化的设计方法。主要分为三个模块：图形环境初始

7、化、问题求解、以及过程动画演示。程序能够处理用户输入的不同初始值使需要搬动的盘子数初始化。初始化图形采用点阵方式直接写屏。关键词 汉诺塔，图形，点阵，直接写屏，动画，演示4攀枝花学院本科课程设计（论文） 目 录 目 录摘 要11设计目的和要求31.1设计目的31.2设计要求32 系统设计52.1设计思路52.2功能模块图62.3主程序流程图62.4汉诺塔求解流程图73 模块详细说明83.1背景初始化83.1.1开启DOS图形模式83.1.2字幕显示模块93.2问题求解模块103.2.1汉诺塔问题描述103.2.2移动方案以103.2.3演示动画103.2.4屏幕暂停函数123.2.5路径清理模

8、块124 用户运行界面图示144.1 用户界面图示144.2 图形演示界面145 心 得 体 会16参 考 文 献17攀枝花学院本科课程设计（论文） 设计目的和要求 1 设计目的和要求1.1设计目的随着计算机技术以及外围设备的发展，在高交互性需求的前提下，计算机图形技术在越来越多的应用中得到应用。早期的计算机与用户之间的交互仅仅是在文本对话方式。而今天，计算机图形学在计算机辅助设计制造，计算机教育，计算机信息化应用中，图形的作用和魅力愈加显现。本课程设计是在我们学完计算机图形学课程之后，对知识掌握程度及实践动手能力的一个综合检验。通过本课程设计，使我们加深对面图形化设计思想的理解.通过对图形方

9、面程序的编写,使我们增强对图形化开发的认识以及兴趣，为以后编程和学习打下良好基础,同时也能够很好地锻炼学生编程的能力。现在的图形化开发工具可以说是百家争鸣。由于我们的课程设计目的是为了了解一些基本图形生成算法的实现，所以我们选择了C语言以及Tc集成开发环境，作为我们的开发工具。一方面，因为Dos下直接写屏方式易于算法实现，另一方面，低级化的开发工具也有利于我们对实现方法的理解。1.2设计要求1.2.1功能要求 能够实现按用户需要对输入的不同盘子数量进行处理。 能够实现根据输入条件，给出完整的解决方案。 能够显示出每次搬运后的结果。 能够实现每一个搬运步骤的动画演示。 演示过程中允许用户在任意时

10、刻中断演示。以避免无意义等待。1.2.2环境要求 能够在windows操作系统下正常运行。 具有一定的错误屏蔽功能。 有友好的界面。 是用户能接受的简单的操作。1.2.3课程设计设备满足下列系统要求，安装Visual Studio C+ 6.0版本的计算机：处理器：配有Pentium III级处理器 (600 MHz)的PC，建议：1 GHz；RAM：192 MB，建议：256MB4可用硬盘空间：必需：基本容量：系统驱动器上需要 75 MB 的可用空间；安装驱动器上需要 330 MB 的可用空间；可选：含 MSDN 速成版：系统驱动器上需要 166 MB 的额外可用空间；安装驱动器上需要 60

11、0 MB 的额外可用空间；操作系统：Windows 2000、Windows XP 或 Windows Server 2003；CD-ROM 或 DVD-ROM 驱动器：没有要求；视频：800 x 600，256 色；建议：1024 x 768，增强色 16 位；鼠标：Microsoft 鼠标或兼容的指针设备。攀枝花学院本科课程设计（论文） 系统设计 2 系统设计2.1设计思路ABC图2.1 汉诺塔对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另

12、外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1. 命令僧人63将63个盘子从A座移到C座2. 自己将最底下的最大的一个盘子从A座移到C座3. 再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：1. 命令僧人62将62个盘子从A移动到C2. 自己将一个盘子从A座移动到B座3. 再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个

13、座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，都是可以执行的。按照如此的思路设计递归算法，很容易得出盘子的移动方案。另外是图形演示盘子的移动过程。为了能够更加形象的表示盘子的移动过程。在设计图形演示的时候，我们采用了图形动态演示。首先我们将字幕、柱子、以及提示信息等等屏幕内容设置成固定不变，我们这里称之为舞台。我们将盘子看作对象，一个盘子一个对象。在设计演示过程的时候，只需要将盘子对象放置于二维界面中的不同信置，通过刷新屏幕，实现动画显示。 2.2功能模块图汉诺塔图形演示程序背景初始化问题求解图形动画演示柱子舞台图形点阵字模字

14、幕Hanio方案移动传值调用路径动作演示屏幕暂停路径清理模块图2.2 功能模块示意图如下图2.2功能模块示意图：初始化过程绘制初始图形汉诺塔求解开始输入盘子数结束图2.3 主程序流程图2.3主程序流程图2.4汉诺塔求解流程图开始将盘子从A座移到C座n为1？是否递归调用，初始n=n-1盘子数为n结束图2.4 Hanoi递归过程流程图退出一级调用n=n+117攀枝花学院本科课程设计（论文） 模块详细说明 3 模块详细说明3.1背景初始化3.1.1开启DOS图形模式Turbo C 提供了非常丰富的图形函数，所有图形函数的原型均在graphics. h 中，在该个初始化模块中主要完成图形模式的初始化、

15、独立图形程序的建立、基本图形功能、图形窗口以及图形模式下的文本输出等函数。另外，使用图形函数时要确保有显示器图形驱动程序*BGI，同时将集成开发环境options/Linker中的Graphics lib选为on，只有这样才能保证正确使用图形函数。不同的显示器适配器有不同的图形分辨率。即是同一显示器适配器，在不同模式下也有不同分辨率。因此，在屏幕作图之前，必须根据显示器适配器种类将显示器设置成为某种图形模式，在未设置图形模式之前，微机系统默认屏幕为文本模式(80列，25行字符模式)，此时所有图形函数均不能工作。设置屏幕为图形模式，可用下列图形初始化函数：void far initgraph(i

16、nt far *gdriver, int far *gmode,char *path);其中gdriver和gmode分别表示图形驱动器和模式，path是指图形驱动程序所在的目录路径。有关图形驱动器、图形模式的符号常数及对应的分辨率见下表。图形驱动程序由Turbo C出版商提供，文件扩展名为.BGI。 根据不同的图形适配器有不同的图形驱动程序。例如对于EGA、 VGA 图形适配器就调用驱动程序EGAVGA.BGI。void init() /* 初始化函数 */ int gd=DETECT,gm ; int i,n,color ; clrscr(); initgraph(&gd,&gm,c:tc

17、); cleardevice(); zimu(); /* 绘制字幕*/3.1.2字幕显示模块 对于使用少量的汉字图形程序，完全没有必要带巨大的汉字库来运行，只要内存允许，可以把汉字字模直接定义为数组的信息存储在EXE文件里。可以把单个字模信息直接取出来，然后在源代码中粘贴。设计时，选用了Win-Tc提供的字模工具。该工具的强大在于不仅可以生成1212、1616宋体这些存在于DOS字库的字模，而且可以生成1616楷体、黑体甚至自定义字体的字模，而且可以提供6种字模大小选择并即时预览效果！对使用少量汉字的图形编程能够提供极大方便。以下是其输出函数的代码：void drawmat(char *mat

18、,int matsize,int x,int y,int color)/*依次：字模指针、点阵大小、起始坐标(x,y)、颜色*/int i,j,k,n; n=(matsize-1)/8+1; for(j=0;jmatsize;j+) for(i=0;in;i+) for(k=0;kk) /*测试为1的位则显示*/ putpixel(x+i*8+k,y+j,color);ABC图2.1 汉诺塔3.2问题求解模块3.2.1汉诺塔问题描述可以看出，递归调用的结束条件是最后一个步骤只需要移动一个盘子。否则，递归过程还将继续进行下去。只有僧人1的任务完成后，僧人1的任务才能完成。若将问题简化，将两个盘子

19、移动的过程可以这样描述：1. 将盘子1 移动到B座2. 将盘子2移动到C座3. 将盘子1从B座移动到C座一共经历了3个步骤，我们可以很容易地推断出，移动N个盘子需要个步骤。编写程序时，用若干个程序实现这个操作，用hanoi函数实现编号较大的僧人需要完成的任务。用move()实现编号较小的僧人需要完成的任务。3.2.2移动方案以其中，move()函数实现的过程，是将主调用函数传来的参数为根据，将需要搬走的盘子对应的柱子出栈一个对象操作，然后将对应搬入的柱子入栈相应对象。该对象即为盘子对象，盘子对象由主调用函数带入。出栈与入栈操作是一次性完成，虽然是由不同的代码段完成，但设计逻辑上认为是一个操作。

20、在程序的流程中，我们还将移动盘子的动画部分在该过程中完成调用。3.2.3演示动画此块模块的设计是整个课程设计的重点，也是设计难点。此处的设计不仅仅是对已经有现成答案的问题从程序设计的角度去实现它，而是在设计的过程中提出了新的挑战。首先，为了实现比较好的视觉效果，设计中制作的动画和一般的不同，平常的动画设计它本身的对象移动路径是固定的，其路径函数可以很容易的表示出来。而我们的柱子栈高度是动态的，当它堆栈的盘子数目不同时，柱子的高度也不同。另外，每个盘子所移动的路线，幅度都是不一样的。这个问题怎么解决呢？我们设计一个动态的函数，假设其为一个抛物线。设抛物线函数为：(Y-b)=p(X-a)2.在一个

21、时间点内，每个柱子堆栈的高度是一定的，可以根据相应的盘子数目得出。柱子的水平位置在程序设计时也是固定的。将其量化为屏幕上的像素点。可以得出两个函数在屏幕上对应点。另外，我们可以设计抛物线最高点为固定值，设其值为H。这样，包含有三个参数的曲线函数就可以唯一确定。其推导过程如下：P(x1-a)2= y1-H P(x2-a)2= y2-H 由可以得到：P = (y2-H)/ (x2-a)2将其代入中可以得到：(y1-H)/( y2-H) = (x1-a)2/(x2-a)2设 q = (y1-H)/( y2-H)1/2此时 a=(x1-x2*q)/(1-q) P=( y2-H)/(x2-a)2 H为固

22、定值。此时，所有参数已经确定，整个方程都可以列出来。每一次盘子移动的路径也可以唯一确定下来。当move 得到由主调用函数传递来的参数时，每一次被调用都需要重新计算函数参数值，以保证每个演示帧自然呈现。路径函数为 ：Y= P(x-a)2+b. 每刷新一个帧后，须根据x 自变量计算下一帧中盘子对象的Y坐标。代码实现如下：void move(char x,char y) void clearprocess(); /*申明函数*/ void action(); /*申明移动动画函数*/ int ifrom,ito; pans data; int mountf,mountt; char a1; char

23、 b1; a0=x;a1=0; b0=y;b1=0; ifrom = x-96; ito = y-96; mountf = pillarifrom.amount; /*数量*/ mountt = pillarito.amount; data = pillarifrom.panmountf; pillarifrom.amount-; /*出栈*/ sdelay(6); /*暂停屏幕*/ if(movecount=15) clearprocess();/*清除步骤提示*/ movecount = movecount%15+1; /*模20+1*/ setcolor(RED); /*输出移动过程*/

24、 settextstyle(TRIPLEX_FONT, HORIZ_DIR, 1); outtextxy(560,30+movecount*10,a); outtextxy(580,30+movecount*10,-); outtextxy(620,30+movecount*10,b); setfillstyle(SOLID_FILL,BLACK);/*涂黑_重画*/ bar(3,pillar1.y-PANHOU*19-20,584,412); drawpps(); /*重画*/ action(data,pillarifrom,pillarito);/*此处添加动画函数*/ pillarito

25、.amount+; /*入栈*/ mountt = pillarito.amount;/*刷新数量*/ pillarito.panmountt = data; drawpps(); /*重画*/3.2.4屏幕暂停函数屏幕暂停函数的设计是因为平常我们所使用的delay函数是根据cpu的时钟来确定延时的，当CPU的运行频率变化时，程序延时的精确性将出现较大的偏差，所以我自行设计了一个sdelay()函数。以保证系统的完美运行。以上是在我们自己所设计的模型条件下建立起来的。这些方面的优化工作相当繁杂，在设计的时候也花费了相当的时间和精力。既使是这样，经过不断的测试，我们的算法到目前为止还仍然不是最优

26、化的算法，不过，已经相当具体实际应用价值了。 对应实现代码如下：/* 自定义延时程序 函数作者:攀枝花学院 谢争东整数1代表(1/18.2)秒 */void sdelay(int delay_t) clock_t start_time ; start_time=clock(); while(clock()-start_time)delay_t) ; /*循环空语句*/3.2.5路径清理模块在实现了动画的移动过程后，路径中会留下长长的“尾巴”，这时候，需要设计一个功能模块来清理痕迹。这个过程相对简单。只需要对路径的前一帧使用与背景颜色相同的色块将其抹去即可。实现代码如下：void clearpr

27、ocess() int i; setfillstyle(SOLID_FILL,BLACK); for(i=0;i=16;i+) bar(545,30+i*10,638,40+i*10); sdelay(1); /*动画延迟n个(1/18.2)秒*/ 攀枝花学院本科课程设计（论文） 用户运行界面 4 用户运行界面图示4.1 用户界面图示图4.1 用户运行首界面此处需要用户输入盘子的总数目，当用户输入大于19的数字时，系统会默认将起修改为19.以防止溢出。4.2 图形演示界面图4.2 用户运行首界面在图形界面中，每一个盘子的移动过程都会以设计好的速度演示出来。其中，屏幕右边显示了没一步移动的过程，

28、当显示步骤大于等于20步时，系统会将右边屏幕刷新，重新输出相继的新的移动步骤。用户可以根据屏幕的提示，跟着演示动画实际操作。当用户需要中断演示动画时，只需要按键盘上任意键即可。至此，整个设计完全设计完成，达到设计要求。攀枝花学院本科课程设计（论文） 心得体会 5 心 得 体 会通过此次对TC的使用，对TC的功能和作用有了更多的理解。以前我总是以为TC是很简单的工具，只能在文本方式下运行，过往想当然的想法使我对软件开发工作没有全面而客观的认识。而现在通过这个课程设计题目，并而我选择了一个对我来讲相当富有挑战性的题目，这更使我认识到，仅仅是学会书面知识是不行的，一方面，对程序设计语言本身的理解不够

29、透彻，另一方面，由于对数据结构及常用算法的理解上的欠缺，再加上我自己在这方面的练习相当少，这些都不同程度地添加了我完成这个题目的困难度。要做算法的设计首先是对程序设计语言的相当的熟悉，而且能够实际熟练地运用，要能够把自己的想法，转换为由程序设计语言来表达。这就要求自己不仅仅要会解决实际问题，而且要有能够将实际问题抽象化，数学建模，以及能用计算机程序设计语言来表达实现。这对我们的程序设计水平和对程序语言代码的敏感度以及专业修养是一个很好的挑战。其次，算法设计的要求也不仅仅是程序设计语言，前面讲到了由实际具体问题抽象建模，由于计算机内部是由二进制来表示和存储数据，程序设计语言实现了计算机内部表示和

30、程序员和计算机交流的语言断层，而程序设计语言和自然语言之间又有一个断层，这个断层就需要靠程序员的集体或个人脑力劳动来弥补。软件总体质量的好坏除了对软件工程的设计者相关，程序设计者的水平至关重要。从自然语言到计算机能够读懂的程序设计语言，是对程序设计能力的考验。仅仅是对程序设计语言的熟悉理解和熟练操作运用是不行的。算法的设计是一个多方面的工作，一方面，我们需要对实际工作中所涉及到的可行性进行分析，另一方面，我们还需要完成对实际问题的研究性解决。有时候，一个问题的解并不是唯一的，而多解问题并不是每个解都是同质同性的，它们之间或多或少有这样那样量度甚至质的区别。比如在我们这个课题中，我们选择了汉诺塔

31、求解演示。通过计算机设计的算法，求解得到较优化的图形演示方案。我们所涉及的问题是怎样尽可能地使界面美观而又能直观、生动地达到演示效果，在这些方案中，不断地比较，进行优化选择。前面已经提到了，经过反复的测试比较，还能找出这个设计的很多不足甚至于错误，也就是说，我现在所做的设计并不是那么尽善尽美的。但它相比较其它同类型的演示程序，已经有了很大的进步。最后，感谢指导老师悉心指导，感谢同学们无私的帮助。参 考 文 献1 陆润民.C语言绘图教程.北京：清华大学出版社，19962 陈锦昌，赵明秀.C语言计算机绘图教程.广州：华南理工大学出版社，1998.93 杨昂岳.微机实用绘图方法与技巧.长沙：国防科技大学出版社，1995.124 刘路放.C语言的窗口式图形界面设计自带汉字环境的应用软件编程.西安交通大学出版社，19965 网冠科技.C语言时尚编程百例.北京：机械工业出版社，2004.16 潘云鹤，董金祥等著计算机图形学原理、方法及应用北京：高等教育出版社，2003.127 孙家广等，计算机图形学（第三版），清华大学出版社,20048 陈元琰编著计算机图形学实用技术北京：科学出版社，20009 和青芳著计算机图形学原理及算法教程北京：清华大学出版社