文档介绍：数据结构学院:信息学院班级:计科高职13-2姓名:曲承玉学号:4汉诺塔程序设计报告一、题目汉诺塔(TowersofHanoi)问题二、设计要求1、在窗口中画出初始时塔和碟子的状态。2、可以以自动或手动两种方式搬移碟子。3、自动搬移可以通过定时器或多线程的方法,每一次移动的时间间隔可以自定,以人眼观察比较舒服为宜,每一次的移动过程如能实现动画最好。4、定义塔的描述类和碟子的描述类。5、在程序中,碟子的数目及每次移动的时间间隔可以通过对话框设置(也应该有默认值)。6、支持暂停功和继续的功能(在自动搬移过程中可以暂停,并继续)。7、暂停后,可以将当前的状态保存(碟子和塔的组合关系)。8、可以从7中保存的文件中读出某个状态,并继续移动。三、问题分析1、已知有三个塔(1、2、3)和n个从大到小的金碟子,初始状态时n个碟子按从大到小的次序从塔1的底部堆放至顶部。2、要求把碟子都移动到塔2(按从大到小的次序从塔2的底部堆放至顶部)。3、每次移动一个碟子。4、任何时候、任何一个塔上都不能把大碟子放到小碟子的上面。5、可以借助塔3。(图1-1)图1-1首先考虑a杆下面的盘子而非杆上最上面的盘子,于是任务变成了:1、将上面的63个盘子移到b杆上;2、将a杆上剩下的盘子移到c杆上;3、将b杆上的全部盘子移到c杆上。将这个过程继续下去,就是要先完成移动63个盘子、62个盘子、61个盘子....1个盘的工作。四、算法选择汉诺塔程序设计算法的实质就是递归递归思想的运用。现将其算法简述如下:为了更清楚地描述算法,可以定义一个函数hanoi(n,a,b,c)。该函数的功能是:将n个盘子从塔a上借助塔b移动到塔c上。这样移动n个盘子的工作就可以按照以下过程进行:1)hanoi(n-1,a,c,b);//将n-1个金盘由a借助c移到b2)将最下面的金盘从a移动到c上;3)hanoi(n-1,b,a,c);//将b上的n-1个盘借助a移到c重复以上过程,直到将全部的盘子移动到塔c上时为止。采用递归算法,移动N个盘子所需步骤数为次,64个盘的移动次数是:18,446,744,073,709,551,615。这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年,盘数为10时所需步骤为1023次,可借助计算机解决。本程序用于找出问题的解决方法并解决较小N值(N≤10)时的汉诺塔问题。五、方案设计1、为了方便按钮等控件的创建,本程序采用Form框架。2、定义了塔类CTower和盘类CPlate,分别用于处理塔和盘的操作。CTower类主要定义塔的坐标、塔上盘的总数、塔上每个盘的编号和位置。CPlate类定义了金盘的坐标、大小、编号、颜色。3、为了支持保存功能,将塔和盘在移动过程中的状态信息参数定义在文档类CHanNuoTaDoc中。在视图类中通过文档指针引用这些参数。4、在视图类CHanNuoTaView中处理塔的移动操作。支持手动和自动两种操作模式。在自动模式中支持暂停和继续功能。两种模式下均可以实现复位操作。5、设计了游戏设置对话框,用于实现对金盘数目和金盘移动速度的设定。设定后金盘处于初始状态。其对应的类是CGameSet。六、编程实现1、CTower类1)数据成员:protected: friendclassCHanNuoTaView; friendclassCHanNuoTaDoc; intstatus;//塔上盘的数量 int x;//塔的坐标 int y; int z[10]; //塔上每个盘的序号将CHanNuoTaView类和CHanNuoTaDoc类声明为友元类,便于在这两个类中直接对CTower类数据成员进行操作。2)成元函数public: CTower(); //构造函数 ~CTower(); //析构函数 void setzb(inta,intb);//设置坐标 int gethzb(); //获得横坐标 int getczb(); //获得纵坐标 void setstatus(); //设置状态 int getstatus(); //获得状态 void gbstatus(); //改变状态 void setpansz(intx);//设置盘子 int getpansz(); //获得盘子本程序中在其友元类中直接操作数据,故上述成员函数大多未使用。2、CPlate类1)数据成元protected: friendclassCHanNuoTaView; friendclassCHanNuoTaDoc; intx,y; //盘的坐标 intnumber;//盘的编号 intsize;//盘的大小 COLORREFcolor;//盘的颜色2)成元函数protedted:CPlate(); //构造函数 ~CPlate(); /