数据结构课程设计报告-- 汉诺威塔

《数据结构课程设计报告-- 汉诺威塔》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验课程设计报告题目：汉诺威塔学生姓名：学号：专业班级：同组姓名：指导教师：设计时间：大二上学期十七周指导老师意见:评定成绩:签名:日期:10目录一.设计目的与要求…………………………………………………021.1设计目的………………………………………………021.2设计要求………………………………………………02二.设计分析…………………………………………………………022.1汉诺威塔问题…………………………………………022.2算法分析………………………………………………032.3流程图…………………………………………………062.4模块及其功能介绍……………………………………07三

2、.设计实现…………………………………………………………08四.心得体会…………………………………………………………09五.参考文献…………………………………………………………10101.设计目的与要求1.1设计目的随着计算机技术以及外围设备的发展，计算机在辅助设计制造，计算机教育，计算机信息化应用中，图形的作用和魅力愈加显现。如何运用计算机技术、运用算法编程来优化解决低阶汉诺威塔问题对我们学生来说具有可实现和可操作性。本次课程设计的目的就是利用所学习到得算法知识和编程语言知识来解决、实现低阶汉诺威塔问题。1.2设计要求功能：编程序显示n（n<=9）层汉诺威塔的调整过程。分步实施：1.初步完成总

3、体设计，搭好框架，确定人机对话的界面，确定函数个数；2.完成最低要求：实现5层汉诺威塔的调整过程；3.进一步要求：直至实现n＝9时的情况。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。2.设计分析2.1汉诺威塔问题n阶汉诺威塔问题：有三个柱子A,B,C。A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1,2,...,n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一

4、次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C2.2算法分析10为满足题目中盘子的移动问题，必须遵循的条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面。设A上有n个盘子。当n=1时，则将圆盘从A直接移动到C。当n>=2时，移动的过程可分解为三个步骤：1)把A上的n-1个圆盘移到B上；2)把A上的一个圆盘移到C上；3)把B上的n-1个圆盘移到C上；其中第一步和第三步是相同的。为了更清楚地描述算法，用图示法描述如下：要将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按

5、照以下过程进行：①第一次调用递归②将一个盘子从A移动到B上；③第二次调用递归重复以上过程，直到将全部的盘子移动到位时为止。由递归算法我们可以得到递推关系：移动n个圆盘需要步，如：移动4个圆盘需要15步，移动64个圆盘需要264-1示意图:10递归运行的层次递归工作栈状态（n值，x值，y值，z值）塔与圆盘的状态分析说明13，a，b，c321abc有主函数进入第一层递归后，运行至语句（行）5，因递归调用而进入下一层由第一层的语句行5进入第二层递归，执行至行5。22，a，c，b3，a，b，c31，a，b，c2，a，c，b3，a，b，c321abc由第二层行5进入第三层递归，执行行3，将1号盘由a移至

6、c后从行9退出第三层递归，返回二层行6。22，a，c，b3，a，b，c321abc将2号盘由a移至b后，从行7进入下一层递归。31，c，a，b2，a，c，b3，a，b，c321abc将1号盘由c移至b后，从行9退出第三层。返回到第二层的行8。22，a，c，b3，a，b，c从行9退出第二层。返回第一层行6。13，a，b，c321abc将3号盘由a移至c后，从行7进入下一层递归。22，b，a，c3，a，b，c从第二层行5进入第三层递归。1031，b，c，a2，b，a，c3，a，b，c123abc将1号盘由b移至a后，从行9退出第三层递归。返回至第二层行6。22，b，a，c3，a，b，c132abc

7、将2号盘由b移至c后，从行7进入下一层递归。31，a，b，c2，b，a，c3，a，b，cab321c将1号盘由a移至c后，从行9退出第三层。返回至第二层行8。22，b，a，c3，a，b，c从行9退出至第二层。返回至第一层行8。13，a，b，c从行9退出递归行数。返回至主函数。0栈空继续运行主程序当N=3时的递归调用树状图，可以使我们更清楚的了解递归的调用过程。10Hanoi(3,A,B,C)Han