汉诺塔程序设计报告

数据结构

学院 ： 信息学院

班级： 计科高职13-2

姓名： *** 学号： ************

汉诺塔程序设计报告

一、题目

汉诺塔（Towers of Hanoi）问题 二、设计要求

1、在窗口中画出初始时塔和碟子的状态。 2、可以以自动或手动两种方式搬移碟子。

3、自动搬移可以通过定时器或多线程的方法，每一次移动的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的移动过程如能实现动画最好。

4、定义塔的描述类和碟子的描述类。

5、在程序中，碟子的数目及每次移动的时间间隔可以通过对话框设置（也应该有默认值）。

6、支持暂停功和继续的功能（在自动搬移过程中可以暂停，并继续）。 7、暂停后，可以将当前的状态保存（碟子和塔的组合关系）。 8、可以从7中保存的文件中读出某个状态，并继续移动。 三、问题分析

1、已知有三个塔（1、2、3）和n个从大到小的金碟子，初始状态时n个碟子按从大到小的次序从塔1的底部堆放至顶部。

2、要求把碟子都移动到塔2（按从大到小的次序从塔2的底部堆放至顶部）。

3、每次移动一个碟子。

—1—

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移到b 2) 将最下面的金盘从a移动到c上；

—2—

3) hanoi(n-1,b,a,c)；//将b上的n-1个盘借助a移到c 重复以上过程，直到将全部的盘子移动到塔c上时为止。 采用递归算法，移动N个盘子所需步骤数为2n1次，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类

—3—

1）数据成员： protected:

friend class CHanNuoTaView; friend class CHanNuoTaDoc;

int status; //塔上盘的数量 int x; //塔的坐标 int y;

int z[10]; //塔上每个盘的序号

将CHanNuoTaView类和CHanNuoTaDoc类声明为友元类，便于在这两个类中直接对CTower类数据成员进行操作。

2）成元函数 public :

CTower(); //构造函数 ~CTower(); //析构函数 void setzb(int a,int b); //设置坐标 int gethzb(); //获得横坐标 int getczb(); //获得纵坐标 void setstatus(); //设置状态 int getstatus(); //获得状态 void gbstatus(); //改变状态 void setpansz(int x); //设置盘子 int getpansz(); //获得盘子

—4—

本程序中在其友元类中直接操作数据，故上述成员函数大多未使用。 2、CPlate类 1）数据成元 protected:

friend class CHanNuoTaView; friend class CHanNuoTaDoc;

int x,y; //盘的坐标 int number; //盘的编号 int size; //盘的大小 COLORREF color; //盘的颜色 2）成元函数 protedted:

CPlate(); //构造函数 ~CPlate(); //析构函数 public:

void setpsz(int x); //设置盘子的大小 int getpsz(); //获得盘子的大小

由于本程序较小，采用友元类方式直接操作该类数据，故有些成元函数没有定义。

3、CHanNuoTaDoc类 1）数据成员 protected:

—5—

friend class CHanNuoTaView; //将CHanNuoTaView类声明//为友元类，便于在CHanNuoTaView类中直接对CHanNuoTaDoc中的数据进行操作

int platenumber; //盘的数目 CTower tower[3]; //定义塔, CPlate plate[10]; //最多10个盘子 int flag; //是否是第一次移动盘子 CRect rect[3]; //定义三个塔上方的区域，手工搬移时用 int x_from,y_from,x_to,y_to; //动画移动起止坐标 int plateNo; //盘子编号 struct movestruct //步骤结构 {

int from; int to; };

movestruct mov[1024]; //用于存储每一步骤 int step; //步骤序号，计算总步骤数 int step2; //步骤序号：取出数组中的每一步 int pause; //bool是否暂停

int interval; //两次移动之间的时间间隔 int steplength; //每次移动的步长 int auto_run; //是否自动执行

—6—

int moving; //bool是否正在移动 int tower_from,tower_to; //起始塔和目标塔 int auto_state; //“自动”按钮状态 int manual_state; //“手动”按钮状态 int pause_state; //“暂停”按钮状态 int reset_state; //“复位”按钮状态 CString pause_text; //暂停按钮上的文字

其中movestruct结构用于将hanoi函数计算出来的移动步骤存档，包括起始塔和目标塔两个参数。

2）成元函数 protected: CHanNuoTaDoc();

DECLARE_DYNCREATE(CHanNuoTaDoc) public:

virtual BOOL OnNewDocument(); //初始化数据 virtual void Serialize(CArchive& ar); //执行存储与打开 virtual ~CHanNuoTaDoc(); 4、CHanNuoTaView类 1）数据成员 public:

//{{AFX_DATA(CHanNuoTaView) enum { IDD = IDD_HANNUOTA_FORM };

—7—

CButton m_reset; //复位按钮 CButton m_pause; //暂停按钮 CButton m_manual; //手动按钮 CButton m_auto; //自动按钮 //}}AFX_DATA

这四个变量用于控制四个按钮的状态。 2）成元函数

视图类的成元函数很多，现只列出较为重要的。 protected:

virtual void OnDraw(CDC* pDC); //完成图形界面的绘制 public:

void InitData(); //数据初始化 void DrawBackground(CDC* pDC); //绘制背景 void nextstep(); //执行下一步操作 void Move(int plateNo,int x1,int y1,int x2,int y2); //移动盘子，动画

void MovePlate(CTower* tower_from,CTower* tower_to);

//移动盘子，无动画

void DrawPlate(CDC* pDC,CPlate plate); //绘制盘子 void BuildTower(CDC* pDC,CTower tower); //绘制塔 void move(int get,int put); //移动盘子，序号 void hanoi(int n,int one,int two,int three); //汉诺塔程序

—8—

protected:

afx_msg void OnAuto(); //自动按钮消息处理函数 afx_msg void OnTimer(UINT nIDEvent); //定时器消息处理函数 afx_msg void OnPause(); //暂停按钮消息处理函数 afx_msg void OnLButtonDown(UINT nFlags, CPoint point);

//左键点击消息处理函数

afx_msg void OnReset(); //复位按钮消息处理函数 afx_msg void OnGameSet(); //设置按钮消息处理函数 afx_msg void OnManual(); //手动按钮消息处理函数 afx_msg void OnUpdateFileOpen(CCmdUI* pCmdUI);

//打开文件更新消息处理函数

afx_msg void OnNextStep(); //执行下一步操作消息处理函数 自动搬移流程：

点击“自动”按钮，其消息处理函数OnAuto调用hanoi递归函数计算所需步骤，并将步骤存入CHanNuoTaDoc类的mov数组中。读出mov数组中的第0个元素（即第一次搬移的起止塔号），作为参数调用MovePlate函数。

MovePlate根据所传参数获得起始塔和目标塔上的金盘的信息，主要是金盘的编号和在起始塔与目标塔上的坐标。启动定时器。完成其他参数修改。

定时器消息处理函数OnTimer将MovePlate函数中算得的数字作为参数调用Move函数。

—9—

Move函数判断金盘是否已经移到目标塔上，若不是则将金盘再移动一步；若已经移到目标塔上，说明此次搬移已经结束，关闭定时器。判断是否所有的盘子都已经移到目标塔上，若是提示搬移结束，否则调用PostMessage函数发送NEXT_STEP消息以执行下一步。

NEXT_STEP消息的处理函数OnNextStep调用nextstep函数。nextstep函数修改参数，从mov数组中取出下一步骤，再调用MovePlate函数。

OnPause函数的暂停/继续功能是通过关闭和打开定时器来实现的。 手动搬移功能主要在左键按下消息处理函数OnLButtonDown中实现。具体流程见图1-2流程图。

七、运行总结

经调试运行，该程序基本满足设计要求，但仍存在一些问题： 1.若将速度调的很慢,当自动运行时,鼠标的一些快速移动也会使画面的演示出问题。

2.自动搬移时若暂停后再保存退出则重新打开后可继续运行；但是在没有暂停的情况下保存退出，在打开后就不正常。

3.在没有暂停的情况下进行设置也会导致程序不正常。

—10—

开始 是否自动搬移 否 是 是 退出 是否正在移动 否 是否点中某个塔 是 否 退出 退出 是 否 是否已定义起始塔 否 塔上是否有盘 是 是否起始塔 否 是 该塔顶盘是否比欲移动盘大 是 消息框报错 定义当前塔为起始塔，并将塔顶盘设为蓝色 取消起始塔定义，并将塔顶盘设为黄色 退出 退出 否 消息框报错 定义为目标塔，调MovePlate函数，将起始塔顶的金盘移动到目标塔顶。 退出 退出 退出

图1-2 流程图

—11—