1、 0 数据结构实验课程设计报告数据结构实验课程设计报告 题 目： 汉诺威塔 学生姓名： 学 号： 专业班级： 同组姓名： 指导教师： 设计时间： 大二上学期十七周 指导老师意见: 评定成绩: 签名: 日期: 1 目录目录 一一. . 设计目的与要求设计目的与要求 0202 1.11.1 设计目的设计目的 0202 1.21.2 设计要求设计要求 0202 二二. . 设计分析设计分析 0202 2.12.1 汉诺威塔问题汉诺威塔问题 0202 2.22.2 算法分析算法分析 0303 2.32.3 流程图流程图 0606 2.42.4 模块及其功能介绍模块及其功能介绍 0707 三三. . 设
2、计实现设计实现 0808 四四. . 心得体会心得体会 0909 五五. . 参考文献参考文献 1010 2 1.1.设计目的与要求设计目的与要求 1.11.1 设计目的设计目的 随着计算机技术以及外围设备的发展，计算机在辅助设计制造，计算机教育，计算机信 息化应用中，图形的作用和魅力愈加显现。 如何运用计算机技术、 运用算法编程来优化解决低阶汉诺威塔问题对我们学生来说具有 可实现和可操作性。 本次课程设计的目的就是利用所学习到得算法知识和编程语言知识来解 决、实现低阶汉诺威塔问题。 1.21.2 设计要求设计要求 功能：编程序显示 n（n=2 时，移动的过程可分解为三个步骤： 1) 把 A
3、上的 n-1 个圆盘移到 B 上； 2) 把 A 上的一个圆盘移到 C 上； 3) 把 B 上的 n-1 个圆盘移到 C 上；其中第一步和第三步是相同的。 为了更清楚地描述算法，用图示法描述如下： 要将 N 个盘子从 A 杆上借助 C 杆移动到 B 杆上。 这样移动 N 个盘子的工作就可以按照以 下过程进行： 第一次调用递归 将一个盘子从 A 移动到 B 上； 第二次调用递归 重复以上过程，直到将全部的盘子移动到位时为止。 由递归算法我们可以得到递推关系： 移动 n 个圆盘需要1 2 n 步，如：移动 4 个圆盘需要 15 步，移动 64 个圆盘需要 2 64-1 示意图示意图: 4 递归运行
4、的层次 递归工作栈状态 （n 值，x值，y 值，z 值） 塔与圆盘的状态 分析说明 1 3，a，b，c a b c 有主函数进入第一层递归后， 运行至 语句（行）5，因递归调用而进入下一 层 由第一层的语句行 5 进入第二层递归， 执行至行 5 。 2 2，a，c，b 3，a，b，c 3 1，a，b，c 2，a，c，b 3，a，b，c a b c 由第二层行 5 进入第三层递归， 执行行 3，将 1 号盘由 a 移至 c 后从行 9 退出 第三层递归，返回二层行 6 。 2 2，a，c，b 3，a，b，c a b c 将 2 号盘由 a 移至 b 后， 从行 7 进入下 一层递归。 3 1，c，a，b 2，a，c，b 3，a，b，c a b c 将 1 号盘由 c 移至 b 后， 从行 9 退出第 三层。返回到第二层的行 8。 2 2，a，c，b 3，a，b，c 从行 9 退出第二层。返回第一层行 6 。 1 3，a，b，c a b c 将 3 号盘由 a 移至 c 后， 从行 7 进入下 一层递归。 2 2，b，a，c 3，a，b，c 从第二层行 5 进入第三层递归。 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1
