汉诺塔程序设计报告

VC++作业电信学院电子0801班张海滨20809050汉诺塔程序设计报告一、 题目汉诺塔（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)-I I 图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个盘子的工作就可以按照以下过程进行：hanoi(n-1,a,c,b);//将n-1个金盘由a借助c移到b将最下面的金盘从a移动到c上;3） hanoi（n-1,b,a,c）；//将b上的n-1个盘借助a移到c重复以上过程，直到将全部的盘子移动到塔c上时为止。采用递归算法，移动N个盘子所需步骤数为2n1次，64个盘的移动次数是：18，446，744，073，709，551，615。这是一个天文数字，若每一微秒可能计算（并不输出）一次移动，那么也需要几乎一百万年，盘数为10时所需步骤为1023次，可借助计算机解决。本程序用于找出问题的解决方法并解决较小N值（NW10）时的汉诺塔问题。五、方案设计1、 为了方便按钮等控件的创建，本程序采用Form框架。2、 定义了塔类CTower和盘类CPlate，分别用于处理塔和盘的操作。CTower类主要定义塔的坐标、塔上盘的总数、塔上每个盘的编号和位置。CPlate类定义了金盘的坐标、大小、编号、颜色。3、 为了支持保存功能，将塔和盘在移动过程中的状态信息参数定义在文档类CHanNuoTaDoc中。在视图类中通过文档指针引用这些参数。4、 在视图类CHanNuoTaView中处理塔的移动操作。支持手动和自动两种操作模式。在自动模式中支持暂停和继续功能。两种模式下均可以实现复位操作。5、 设计了游戏设置对话框，用于实现对金盘数日和金盘移动速度的设定。设定后金盘处于初始状态。其对应的类是CGameSet。六、编程实现1、CTower类

1)数据成员：protected:friendclassCHanNuoTaView;friendclassCHanNuoTaDoc;intstatus;//塔上盘的数量intx;〃塔的坐标inty;intz[10];〃塔上每个盘的序号将CHanNuoTaView类和CHanNuoTaDoc类声明为友元类，便于在这两个类中直接对CTower类数据成员进行操作。2）成元函数public:CTower();〃构造函数~CTower();//析构函数voidsetzb(inta,intb);//设置坐标int gethzb();〃获得横坐标int getczb();〃获得纵坐标voidsetstatus();〃设置状态intgetstatus();//获得状态voidgbstatus();//改变状态voidsetpansz(intx);//设置盘子intgetpansz();〃获得盘子

本程序中在其友元类中直接操作数据，故上述成员函数大多未使用。2、CPlate类1）数据成元protected:friendclassCHanNuoTaView;friendclassCHanNuoTaDoc;intx,y;//本程序中在其友元类中直接操作数据，故上述成员函数大多未使用。2、CPlate类1）数据成元protected:friendclassCHanNuoTaView;friendclassCHanNuoTaDoc;intx,y;//盘的坐标intnumber;//盘的编号intsize;//盘的大小COLORREFcolor;//盘的颜色2）成元函数CPlate();protedted:CPlate();〃构造函数//析构函数~CPlate();//析构函数public:voidsetpsz(intx);〃设置盘子的大小intgetpsz();//获得盘子的大小voidsetpsz(intx);〃设置盘子的大小intgetpsz();//获得盘子的大小由于本程序较小，采用友元类方式直接操作该类数据，故有些成元函数没有定义。3、CHanNuoTaDoc类1）数据成员protected:

friendclassCHanNuoTaView; //将CHanNuoTaView类声明//为友元类，便于在CHanNuoTaView类中直接对CHanNuoTaDoc中的数据进行操作intplatenumber;〃盘的数日CTowertower[3];〃定义塔，CPlateplate[10];//最多10个盘子intflag;〃是否是第一次移动盘子CRectrect[3];〃定义三个塔上方的区域，手工搬移时用intx_from,y_from,x_to,y_to; //动画移动起止坐标intplateNo;〃盘子编号structmovestruct//步骤结构{intfrom;intto;};movestructmov[1024]; //用于存储每步骤intstep;〃步骤序号，计算总步骤数intstep2;//步骤序号:取出数组中的每步intpause;//bool是否暂停intinterval;〃两次移动之间的时间间隔intsteplength;//每次移动的步长intauto_run;//是否自动执彳丁intmoving;//bool是否正在移动inttower_from,tower_to;〃起始塔和日标塔intauto_state;//“自动”按钮状态intmanual_state;//“手动”按钮状态intpause_state;//“暂停”按钮状态intreset_state;//“复位”按钮状态CStringpause_text;〃暂停按钮上的文字其中movestruct结构用于将hanoi函数计算出来的移动步骤存档，包括起始塔和日标塔两个参数。2)成元函数protected:CHanNuoTaDoc();DECLARE_DYNCREATE(CHanNuoTaDoc)public:virtualBOOLOnNewDocument(); //初始化数据virtualvoidSerialize(CArchive&ar);//执行存储与打开virtual~CHanNuoTaDoc();4、CHanNuoTaView类1)数据成员public://{{AFX_DATA(CHanNuoTaView)enum{IDD=IDD_HANNUOTA_FORM};CButton m_reset; //复位按钮CButton m_pause; //暂停按钮CButton m_manual; //手动按钮CButton m_auto; //自动按钮//}}AFX_DATA这四个变量用于控制四个按钮的状态。2)成元函数视图类的成元函数很多，现只列出较为重要的。protected:virtualvoidOnDraw(CDC*pDC); //完成图形界面的绘制public:voidInitData(); //数据初始化voidDrawBackground(CDC*pDC);//绘制背景voidnextstep(); //执行下一步操作voidMove(intplateNo,intx1,inty1,intx2,inty2);〃移动盘子，动画voidMovePlate(CTower*tower_from,CTower*tower_to);〃移动盘子，无动画voidDrawPlate(CDC*pDC,CPlateplate); //绘制盘子voidBuildTower(CDC*pDC,CTowertower);//绘制塔voidmove(intget,intput); //移动盘子，序号voidhanoi(intn,intone,inttwo,intthree);//汉诺塔程序

protected:afx_msgvoidOnAuto(); //自动按钮消息处理函数afx_msgvoidOnTimer(UINTnIDEvent);//定时器消息处理函数afx_msgvoidOnPause(); //暂停按钮消息处理函数afx_msgvoidOnLButtonDown(UINTnFlags,CPointpoint);//左键点击消息处理函数afx_msgvoidOnReset(); //复位按钮消息处理函数afx_msgvoidOnGameSet();//设置按钮消息处理函数afx_msgvoidOnManual();//手动按钮消息处理函数afx_msgvoidOnUpdateFileOpen(CCmdUI*pCmdUI);//打开文件更新消息处理函数afx_msgvoidOnNextStep();//执行下一步操作消息处理函数自动;移流程:自动;移流程:点击“自动”按钮，其消息处理函数OnAuto调用hanoi递归函数计算所需步骤，并将步骤存入CHanNuoTaDoc类的mov数组中。读出mov数组中的第0个元素(即第一次搬移的起止塔号)，作为参数调用MovePlate函数。MovePlate根据所传参数获得起始塔和日标塔上的金盘的信息，主要是金盘的编号和在起始塔与日标塔上的坐标。启动定时器。完成其他参数修改。定时器消息处理函数OnTimer将MovePlate函数中算得的数字作为参数调用Move函数。Move函数判断金盘是否已经移到目标塔上，若不是则将金盘再移动步；若已经移到目标塔上，说明此次搬移已经结束，关闭定时器。判断是否所有的盘子都已经移到目标塔上，若是提示搬移结束，否则调用PostMessage函数发送NEXT_STEP消息以执行下一步。NEXT_STEP消息的处理函数OnNextStep调用nextstep函数。nextstep函数修改参数，从mov数组中取出下一步骤，再调用MovePlate函数。OnPaus