汉诺塔游戏设计过程.doc

2 - 1 - 兰州交通大学 数理与软件工程学院 课程设计报告 2011 ～2012学年第 二 学期 课程名称 数据结构 设计题目 汉诺塔游戏程序 班级 信计1001班 小组成员 张章、王欣、李贵生 报告者 李贵生 201005235 指导老师 金静 2012年6月 一、实验目的： 通过此次C++实训，一方面加深了对C++语言的了解，而不只是单单的在课本中学到的那些理论。通过学生动手亲自编写，平时乏味的课程，变的生动有趣。平时在课堂上学到的东西可以自己动手编写，将其转化成一些实用的技能。另一方面，通过学生小组完成任务，提高团队意识，增加凝聚力，让同学们意识到团结就是力量，每个人都是重要的一份子。 二、题目：汉诺塔游戏程序 1 问题描述：在平面上有三个位置A、B、C，在A位置上有n个大小不等的圆盘、小盘压在大盘上形成圆盘堆。要求将A位置的N个圆盘通过B位置移动到C位置上，并按同样的顺序叠放。移动圆盘时必须遵循以下规则： 每一次只能移动一个圆盘 圆盘可以放在A、B、C任何一个塔座上 任何时刻都不能将大圆盘压在小圆盘上 2 基本要求： 圆盘的个数从键盘输入（如3-64等）；用动画的形式在屏幕上显示盘的移动。 三、问题分析和任务定义 1、已知有三个塔（1、2、3）和n个从大到小的金碟子，初始状态时n个碟子按从大到小的次序从塔1的底部堆放至顶部。 2、要求把碟子都移动到塔2（按从大到小的次序从塔2的底部堆放至顶部）。 3、每次移动一个碟子。 4、任何时候、任何一个塔上都不能把大碟子放到小碟子的上面。 5、可以借助塔3。 先考虑a杆下面的盘子而非杆上最上面的盘子，于是任务变成了： 1、将上面的N个盘子移到b杆上； 2、将a杆上剩下的盘子移到c杆上； 3、将b杆上的全部盘子移到c杆上。 将这个过程继续下去，就是要先完成移动n个盘子、n-1个盘子、n-2个盘子1个盘的工作。 四、课题介绍： 4.1 汉诺塔问题初始模型： 4.2 实现步骤： 为满足题目中盘子的移动问题，必须遵循的条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面。 设要解决的汉诺塔共有N个圆盘，对A杆上的全部N个圆盘从小到大顺序编号，最小的圆盘为1号，次之为2号，依次类推，则最下面的圆盘的编号为N。 第一步：先将问题简化。假设A杆上只有一个圆盘，即汉诺塔只有一层N，则只要将1号盘从A杆上移到B杆上即可。 第二步：对于一个有N（N1）个圆盘的汉诺塔，将N个圆盘分成两部分：“上面的N-1个圆盘”看成一个整体，为了解决N个圆盘的汉诺塔，可以按下面图示的方式进行操作： （1）将A杆上面的N-1个盘子，借助B杆，移到C杆上； 图 4—1 （2）将A杆上剩余的N号盘子移到B杆上； 图 4—2 （3）将C杆上的N-1个盘子，借助A杆，移到B杆上。 图 4—3 五、流程图 游戏选择界面初始化界面、视窗开始 游戏选择界面 初始化界面、视窗 开始 结束Esc键退出游戏N退出界面、按任意键退出盘子数加1Y继续判断游戏结果开始游戏选择盘子数目（2—10）按键判断 结束 Esc键退出游戏 N 退出 界面、按任意键退出 盘子数加1 Y 继续 判断游戏结果 开始游戏 选择盘子数目（2—10） 按键判断 Enter键进入游戏 Enter键进入游戏 六、源程序代码 #includestdio.h #includestdlib.h #includeconio.h #includestring.h #includemath.h struct T { int h; //塔的高度 int x; //塔的第一个盘的x坐标,y坐标等于(7+n-塔的高度h) int l; //塔的第一个盘的长度 }ta[3]={{10,15,2},{0,0,0},{0,0,0}}; char hnt[18][79]={ { }, { 汉诺塔动画演示 }