汉诺塔实验报告.doc

课课 程程 设设 计计 2012 年12 月21日 目录目录 1 概述 概述 4 2 2 实验目的 实验目的 4 3 3 问题分析 问题分析 5 4 4 实验步骤 实验步骤 5 5 5 流程图 流程图 6 6 6 程序代码 程序代码 7 7 7 程序调试与测试 程序调试与测试 10 8 8 结论 结论 12 9 9 总结 总结 15 一 概述一 概述 数据结构是计算机学科非常重要的一门专业基础理论课程 要想编写针对非数值计算问 题的高质量程序 就必须要熟练的掌握这门课程设计的知识 另外 他与计算机其他课程 都有密切联系 具有独特的承上启下的重要位置 拥有 数据结构 这门课程的知识准备 对于学习计算机专业的其他课程 如操作系统 数据库管理系统 软件工程的都是有益的 二 实验目的二 实验目的 通过本实验 掌握复杂性问题的分析方法 了解汉诺塔游戏的时间复杂性和空 间复杂性 三 问题分析三 问题分析 任务 有三个柱子 A B C A 柱子上叠放有 n 个盘子 每个盘子都比它下面的盘子要 小一点 可以从上到下用 1 2 n 编号 要求借助柱子 B 把柱子 A 上的所有的盘子移动到柱子 C 上 移动条件为 1 一次只能移一个盘子 2 移动过程中大盘子不能放在小盘子上 只能小盘子放在大盘子上 分析 首先容易证明 当盘子的个数为 n 时 移动的次数应等于 2 n 1 首先把三根柱子按顺序排成品字型 把所有的圆盘按从大到小的顺序放在柱子 A 上 根据圆盘的数量确定柱子的排放顺序 若 n 为偶数 按顺时针方向依次摆放 A B C 若 n 为奇数 按顺时针方向依次摆放 A C B 1 按顺时针方向把圆盘 1 从现在的柱子移动到下一根柱子 即当 n 为偶数时 若圆盘 1 在柱子 A 则把它移动到 B 若圆盘 1 在柱子 B 则把它移动到 C 若圆盘 1 在柱子 C 则把它移动到 A 2 接着 把另外两根柱子上可以移动的圆盘移动到新的柱子上 即把非空柱子上的圆盘移动到空柱子上 当两根柱子都非空时 移动较小的圆盘 这一步没有明确规定移动哪个圆盘 你可能以为会有多种可能性 其实不然 可实施的行 动是唯一的 反复进行 1 2 操作 最后就能按规定完成汉诺塔的移动 四 实验步骤四 实验步骤 1 用 c 或 c 语言设计实现汉诺塔游戏 2 让盘子数从 2 开始到 7 进行实验 记录程序运行时间和递归调用次数 3 画出盘子数 n 和运行时间 t 递归调用次数 m 的关系图 并进行分析 五 流程图五 流程图 开始 输入 m m 20 是否继续 结束 输出结果 2 否 1 是 六 程序代码 六 程序代码 include include Hanoi 塔 class Hanoi public Hanoi cout floor if floor 20 cout 层数错误重新输入 goto input cout endl arrayA new char floor arrayB new char floor arrayC new char floor for int h 0 h floor h arrayA h new char floor 1 arrayB h new char floor 1 arrayC h new char floor 1 for int i 0 i floor i for int j 0 j floor 1 j arrayA i j 0 arrayB i j 0 arrayC i j 0 for int n 0 n floor n for int m 0 m n m arrayA n m stepcount 0 void HanoiShow hanoiShow floor arrayA arrayB arrayC void Display system cls cout 第 stepcount 步 endl int i int j for i 0 i floor 1 i if i 0 cout A else cout cout for i 0 i floor 1 i if i 0 cout B else cout cout for i 0 i floor 1 i if i 0 cout C else cout cout endl for i 0 i floor i for j 0 j floor 1 j cout arrayA i j cout for j 0 j floor 1 j cout arrayB i j cout for j 0 j floor 1 j cout arrayC i j cout endl system pause Hanoi for int i 0 i 0 hanoiShow n 1 A C B move n A B hanoiShow n 1 C B A else return void move int n char D char S int dc 1 int sc 1 int i int j for i 0 i floor i if D i 0 dc i break for j 0 j floor j if S j 0 sc j 1 break if sc 1 sc floor 1 for int k 0 k floor 1 k S sc k D dc k D dc k 0 stepcount Display int stepcount int floor char arrayA char arrayB char arrayC endif 自定义头文件 include stdafx h include Hanoi h 七 程序调试与测试七 程序调试与测试 在编译过程中发现错误 经查找之后发现没有对主函数 main 说明 经改正后 运行结果运行结果 第一步第一步 先输入要玩的层数 第二步第二步 手动运行手动运行 八 结论八 结论 通过对上述递归在 Hanoi 塔问题上的应用分析 我们可以得出如下结论 1 递归调用过程中 在程序执行之前无法知道控制这种调用栈的规模 因为这 一规模取决于递归调用的次序 在这种情况下 程序的地址空间可能动态变化 2 递归应用于程序设计时 结构清晰 程序易读 编制和调试程序很方便 不 需要用户自行管理递归工作栈 但递归应用于计算机时需要占用大量系统资源 包括堆栈 软中断和存贮空间等 并消耗大量处理时间 因此 可以考虑 采用并行计算进行处理 但 3 递归是