漢諾塔程序設(shè)計報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)學(xué)院 ： 信息學(xué)院 班級： 計科高職13-2 姓名： 曲承玉 學(xué)號： 4 漢諾塔程序設(shè)計報告一、題目漢諾塔（Towers of Hanoi）問題二、設(shè)計要求1、在窗口中畫出初始時塔和碟子的狀態(tài)。2、可以以自動或手動兩種方式搬移碟子。3、自動搬移可以通過定時器或多線程的方法，每一次移動的時間間隔可以自定，以人眼觀察比較舒服為宜，每一次的移動過程如能實現(xiàn)動畫最好。4、定義塔的描述類和碟子的描述類。5、在程序中，碟子的數(shù)目及每次移動的時間間隔可以通過對話框設(shè)置（也應(yīng)該有默認(rèn)值）。6、支持暫停功和繼續(xù)的功能（在自動搬移過程中可以暫停，并繼續(xù)）。7、暫停后，可以將當(dāng)前的

2、狀態(tài)保存（碟子和塔的組合關(guān)系）。8、可以從7中保存的文件中讀出某個狀態(tài)，并繼續(xù)移動。三、問題分析1、已知有三個塔（1、2、3）和n個從大到小的金碟子，初始狀態(tài)時n個碟子按從大到小的次序從塔1的底部堆放至頂部。2、要求把碟子都移動到塔2（按從大到小的次序從塔2的底部堆放至頂部）。3、每次移動一個碟子。4、任何時候、任何一個塔上都不能把大碟子放到小碟子的上面。5、可以借助塔3。（圖1-1）圖1-1首先考慮a桿下面的盤子而非桿上最上面的盤子，于是任務(wù)變成了： 1、將上面的63個盤子移到b桿上；2、將a桿上剩下的盤子移到c桿上；3、將b桿上的全部盤子移到c桿上。將這個過程繼續(xù)下去，就是要先完成移動63

3、個盤子、62個盤子、61個盤子.1個盤的工作。四、算法選擇漢諾塔程序設(shè)計算法的實質(zhì)就是遞歸遞歸思想的運用。現(xiàn)將其算法簡述如下：為了更清楚地描述算法，可以定義一個函數(shù)hanoi(n,a,b,c)。該函數(shù)的功能是：將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重復(fù)以上過程，直到將全部的盤子移動到塔c上時為止。采用遞歸算法，移動N個盤子所需步驟數(shù)為次，64個盤的移動次數(shù)是：18，44

4、6，744，073，709，551，615。這是一個天文數(shù)字，若每一微秒可能計算(并不輸出)一次移動，那么也需要幾乎一百萬年，盤數(shù)為10時所需步驟為1023次,可借助計算機解決。本程序用于找出問題的解決方法并解決較小N值（N10）時的漢諾塔問題。五、方案設(shè)計1、為了方便按鈕等控件的創(chuàng)建，本程序采用Form框架。2、定義了塔類CTower和盤類CPlate，分別用于處理塔和盤的操作。CTower類主要定義塔的坐標(biāo)、塔上盤的總數(shù)、塔上每個盤的編號和位置。CPlate類定義了金盤的坐標(biāo)、大小、編號、顏色。3、為了支持保存功能，將塔和盤在移動過程中的狀態(tài)信息參數(shù)定義在文檔類CHanNuoTaDoc中。

5、在視圖類中通過文檔指針引用這些參數(shù)。4、在視圖類CHanNuoTaView中處理塔的移動操作。支持手動和自動兩種操作模式。在自動模式中支持暫停和繼續(xù)功能。兩種模式下均可以實現(xiàn)復(fù)位操作。5、設(shè)計了游戲設(shè)置對話框，用于實現(xiàn)對金盤數(shù)目和金盤移動速度的設(shè)定。設(shè)定后金盤處于初始狀態(tài)。其對應(yīng)的類是CGameSet。六、編程實現(xiàn)1、CTower類1）數(shù)據(jù)成員：protected:friend class CHanNuoTaView;friend class CHanNuoTaDoc;int status; /塔上盤的數(shù)量intx; /塔的坐標(biāo)inty;intz10; /塔上每個盤的序號將CHanNuoTaV

6、iew類和CHanNuoTaDoc類聲明為友元類，便于在這兩個類中直接對CTower類數(shù)據(jù)成員進行操作。2）成元函數(shù)public :CTower(); /構(gòu)造函數(shù)CTower(); /析構(gòu)函數(shù)voidsetzb(int a,int b); /設(shè)置坐標(biāo)intgethzb(); /獲得橫坐標(biāo)intgetczb(); /獲得縱坐標(biāo)void setstatus(); /設(shè)置狀態(tài)int getstatus(); /獲得狀態(tài)void gbstatus(); /改變狀態(tài)void setpansz(int x); /設(shè)置盤子intgetpansz(); /獲得盤子本程序中在其友元類中直接操作數(shù)據(jù)，故上述成員函

7、數(shù)大多未使用。2、CPlate類1）數(shù)據(jù)成元protected:friend class CHanNuoTaView;friend class CHanNuoTaDoc;int x,y; /盤的坐標(biāo)int number; /盤的編號int size; /盤的大小COLORREF color; /盤的顏色2）成元函數(shù)protedted:CPlate(); /構(gòu)造函數(shù)CPlate(); /析構(gòu)函數(shù)public:void setpsz(int x); /設(shè)置盤子的大小int getpsz(); /獲得盤子的大小由于本程序較小，采用友元類方式直接操作該類數(shù)據(jù)，故有些成元函數(shù)沒有定義。3、CHanNuo

8、TaDoc類1）數(shù)據(jù)成員protected:friend class CHanNuoTaView; /將CHanNuoTaView類聲明/為友元類，便于在CHanNuoTaView類中直接對CHanNuoTaDoc中的數(shù)據(jù)進行操作int platenumber; /盤的數(shù)目CTower tower3; /定義塔, CPlate plate10; /最多10個盤子int flag; /是否是第一次移動盤子CRect rect3;/定義三個塔上方的區(qū)域，手工搬移時用int x_from,y_from,x_to,y_to;/動畫移動起止坐標(biāo)int plateNo; /盤子編號struct moves

9、truct /步驟結(jié)構(gòu)int from;int to;movestruct mov1024; /用于存儲每一步驟int step; /步驟序號，計算總步驟數(shù)int step2; /步驟序號：取出數(shù)組中的每一步int pause; /bool是否暫停int interval; /兩次移動之間的時間間隔int steplength;/每次移動的步長int auto_run; /是否自動執(zhí)行int moving; /bool是否正在移動int tower_from,tower_to;/起始塔和目標(biāo)塔int auto_state;/“自動”按鈕狀態(tài)int manual_state; /“手動”按鈕狀態(tài)

10、int pause_state; /“暫?！卑粹o狀態(tài)int reset_state;/“復(fù)位”按鈕狀態(tài)CString pause_text;/暫停按鈕上的文字其中movestruct結(jié)構(gòu)用于將hanoi函數(shù)計算出來的移動步驟存檔，包括起始塔和目標(biāo)塔兩個參數(shù)。2）成元函數(shù)protected: CHanNuoTaDoc();DECLARE_DYNCREATE(CHanNuoTaDoc)public: virtual BOOL OnNewDocument(); /初始化數(shù)據(jù) virtual void Serialize(CArchive& ar); /執(zhí)行存儲與打開 virtual CHan

11、NuoTaDoc();4、CHanNuoTaView類1）數(shù)據(jù)成員public:/AFX_DATA(CHanNuoTaView)enum IDD = IDD_HANNUOTA_FORM ;CButtonm_reset;/復(fù)位按鈕CButtonm_pause;/暫停按鈕CButtonm_manual;/手動按鈕CButtonm_auto;/自動按鈕/AFX_DATA這四個變量用于控制四個按鈕的狀態(tài)。2）成元函數(shù)視圖類的成元函數(shù)很多，現(xiàn)只列出較為重要的。protected:virtual void OnDraw(CDC* pDC);/完成圖形界面的繪制public:void InitData();

12、 /數(shù)據(jù)初始化void DrawBackground(CDC* pDC);/繪制背景void nextstep(); /執(zhí)行下一步操作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

13、); /移動盤子，序號void hanoi(int n,int one,int two,int three);/漢諾塔程序protected:afx_msg void OnAuto(); /自動按鈕消息處理函數(shù)afx_msg void OnTimer(UINT nIDEvent); /定時器消息處理函數(shù)afx_msg void OnPause(); /暫停按鈕消息處理函數(shù)afx_msg void OnLButtonDown(UINT nFlags, CPoint point);/左鍵點擊消息處理函數(shù)afx_msg void OnReset(); /復(fù)位按鈕消息處理函數(shù)afx_msg void

14、OnGameSet(); /設(shè)置按鈕消息處理函數(shù)afx_msg void OnManual(); /手動按鈕消息處理函數(shù)afx_msg void OnUpdateFileOpen(CCmdUI* pCmdUI);/打開文件更新消息處理函數(shù)afx_msg void OnNextStep();/執(zhí)行下一步操作消息處理函數(shù)自動搬移流程：點擊“自動”按鈕，其消息處理函數(shù)OnAuto調(diào)用hanoi遞歸函數(shù)計算所需步驟，并將步驟存入CHanNuoTaDoc類的mov數(shù)組中。讀出mov數(shù)組中的第0個元素（即第一次搬移的起止塔號），作為參數(shù)調(diào)用MovePlate函數(shù)。MovePlate根據(jù)所傳參數(shù)獲得起始塔和

15、目標(biāo)塔上的金盤的信息，主要是金盤的編號和在起始塔與目標(biāo)塔上的坐標(biāo)。啟動定時器。完成其他參數(shù)修改。定時器消息處理函數(shù)OnTimer將MovePlate函數(shù)中算得的數(shù)字作為參數(shù)調(diào)用Move函數(shù)。Move函數(shù)判斷金盤是否已經(jīng)移到目標(biāo)塔上，若不是則將金盤再移動一步；若已經(jīng)移到目標(biāo)塔上，說明此次搬移已經(jīng)結(jié)束，關(guān)閉定時器。判斷是否所有的盤子都已經(jīng)移到目標(biāo)塔上，若是提示搬移結(jié)束，否則調(diào)用PostMessage函數(shù)發(fā)送NEXT_STEP消息以執(zhí)行下一步。NEXT_STEP消息的處理函數(shù)OnNextStep調(diào)用nextstep函數(shù)。nextstep函數(shù)修改參數(shù)，從mov數(shù)組中取出下一步驟，再調(diào)用MovePlate函數(shù)。OnPause函數(shù)的暫停/繼續(xù)功能是通過關(guān)閉和打開定時器來實現(xiàn)的。手動搬移功能主要在左鍵按下消息處理函數(shù)OnLButtonDown中實現(xiàn)。具體流程見圖1-2流程圖。七、運行總結(jié)經(jīng)調(diào)試運行，該程序基本滿足設(shè)計要求，但仍存在一些問題：1.若將速度調(diào)的很慢,當(dāng)自動運行時,鼠標(biāo)的一些快速移動也會使畫面的演示出問題。2.自動搬移時若暫停后再保