作業(yè)題目2013.doc

作業(yè)題目請大家認真閱讀下面紅色字體部分！要求與說明：l 作業(yè)成績總分40分，起評分下列作業(yè)題目各自不同，見具體作業(yè)題目，自選作業(yè)需根據(jù)實際判定。l 鼓勵創(chuàng)新?？勺詳M（或結(jié)合實際項目情況）題目，有創(chuàng)新、有價值的題目起評分在35分以上。l 所有作業(yè)要求使用Visual studio（各個版本）編程工具實現(xiàn)。l 所有題目都要求具有完整的圖形用戶界面、輸入/出接口，功能要完備。l 題目涉及的算法實現(xiàn)方法不限（同一個問題可以使用不同的算法實現(xiàn)）。l 要求撰寫設(shè)計報告（內(nèi)容包括：問題分析、算法選擇、方案設(shè)計、編程實現(xiàn)），設(shè)計報告以Word文檔形式與作業(yè)程序源代碼壓縮到一起提交。l 任何上交的作業(yè)（包括：設(shè)計報告、程序源代碼）僅作為作業(yè)看待，不承擔(dān)任何版權(quán)問題，而且必須是獨立完成。l 提交作業(yè)時，請將程序目錄下的debug和release目錄及其下所有內(nèi)容刪除，并統(tǒng)一用WinRAR壓縮，壓縮文件名的命名格式：學(xué)號西文字符，半角，短橫線姓名-西文字符，半角，短橫線所在院系名稱例如：2013090143-姓名-學(xué)院命名不規(guī)范將在起評分基礎(chǔ)上扣2分！l 作業(yè)的提交時間：2013年11月25日12月23日。l 作業(yè)的提交方式：統(tǒng)一提交到為提交作業(yè)的獨立性（避免作業(yè)提交后被別人下載或被別人看到），從2013年12月1日起，郵箱將不再向大家開放，郵箱中的實例、文檔請大家在此之前下載。作業(yè)提交日期不得晚于2013年12月23日！l 作業(yè)只允許提交1次。l 作業(yè)提交名單（最終）將在考試日公布。l 請大家根據(jù)自己的情況，在作業(yè)完成后及時提交，以免集中提交造成郵箱阻塞而影響提交。l 被判定為抄襲者，其成績按如下計算：非抄襲所得成績/抄襲次數(shù)，抄襲人次3次以上，所有抄襲、被抄襲者成績?yōu)?；一、 作業(yè)題目1：（起評分30分）1、 編制一個圖形化的列表程序，具體要求如下：a) 以雙向鏈表為數(shù)據(jù)模型，分別將鏈表的結(jié)點和鏈表本身定義為兩個C+類，類名分別為CNode、CList。b) 一般結(jié)點的圖形顯示結(jié)果如下：c) 頭結(jié)點顯示如下：d) 尾結(jié)點顯示如下：e) 當(dāng)前結(jié)點顯示如下：f) 整個鏈表顯示結(jié)構(gòu)如下：g) 鏈表應(yīng)完成下列操作：i. 插入、追加、刪除結(jié)點ii. 選中某結(jié)點成為當(dāng)前結(jié)點iii. 結(jié)點可以拖拽iv. 鏈表雙向遍歷v. 通過對話框修改某結(jié)點的數(shù)據(jù)域h) 程序結(jié)果要求：i. 采用MDI方式ii. 對鏈表的操作通過菜單完成iii. 結(jié)點和鏈表的串行化處理iv. 多視圖更新二、 漢諾塔（Towers of Hanoi）問題（起評分28分）漢諾塔（Towers of Hanoi）問題來自一個古老的傳說：在世界剛被創(chuàng)建的時候有一座鉆石寶塔，其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔1上的碟子移動到塔2上去，其間借助于塔3的幫助。由于碟子非常重，因此，每次只能移動一個碟子。另外，任何時候都不能把一個碟子放在比它小的碟子上面。按照這個傳說，當(dāng)牧師們完成他們的任務(wù)之后，世界末日也就到了。圖1-1問題：1、已知有三個塔（1、2、3）和n個從大到小的金碟子，初始狀態(tài)時n個碟子按從大到小的次序從塔1的底部堆放至頂部。2、要求把碟子都移動到塔2（按從大到小的次序從塔2的底部堆放至頂部）。3、每次移動一個碟子。4、任何時候、任何一個塔上都不能把大碟子放到小碟子的上面。5、可以借助塔3。作業(yè)要求：1、在窗口中畫出初始時塔和碟子的狀態(tài)。2、可以以自動或手動兩種方式搬移碟子。3、自動搬移可以通過定時器或多線程的方法，每一次移動的時間間隔可以自定，以人眼觀察比較舒服為宜，每一次的移動過程如能實現(xiàn)動畫最好。4、定義塔的描述類和碟子的描述類。5、在程序中，碟子的數(shù)目及每次移動的時間間隔可以通過對話框設(shè)置（也應(yīng)該有默認值）。6、支持暫停功和繼續(xù)的功能（在自動搬移過程中可以暫停，并繼續(xù)）。7、暫停后，可以將當(dāng)前的狀態(tài)保存（碟子和塔的組合關(guān)系）。8、可以從7中保存的文件中讀出某個狀態(tài)，并繼續(xù)移動。三、 聊天系統(tǒng)（起評分30分）創(chuàng)建一個聊天系統(tǒng)，該系統(tǒng)由服務(wù)器程序和客戶端程序兩部分構(gòu)成。其簡單的工作原理如下圖所示。當(dāng)服務(wù)器程序運行時，首先啟動一個監(jiān)聽器，負責(zé)監(jiān)聽服務(wù)器的某個端口，當(dāng)客戶端要進行聊天時，首先要對服務(wù)器的特定端口進行連接請求，即客戶端試圖連接服務(wù)器被監(jiān)聽的端口時，服務(wù)器的監(jiān)聽器可以選擇接受或拒絕連接請求。如果接受客戶端的連接請求，則由監(jiān)聽器為客戶端分配一個對應(yīng)的“套接字”對象，這樣在服務(wù)器和某個客戶端之間就建立了一條數(shù)據(jù)管道，可以聊天了。本聊天室主要采用Socket（套接字）編寫，套接字可以支持TCP和UDP協(xié)議。圖1 聊天室工作原理圖圖2 聊天室服務(wù)器啟動界面圖3 聊天室服務(wù)器主界面聊天客戶端狀態(tài)信息待發(fā)送信息區(qū)聊天信息圖4 聊天室客戶端主界面圖5 客戶端連接服務(wù)器主界面除實現(xiàn)上述基本聊天功能外，還要求：（1） 在服務(wù)器端可以將客戶登陸、退出及在線時間等情況記錄并保存。（2） 服務(wù)器和客戶端都可以將聊天記錄保存。附加功能：可以在客戶端和服務(wù)器端傳送文件，支持視頻功能。四、 開關(guān)盒布線問題（起評分32分）給定一個矩形布線區(qū)域，其外圍有若干針腳。兩個針腳之間通過布設(shè)一條金屬線路而實現(xiàn)互連。這條線路被稱為電線，被限制在矩形區(qū)域內(nèi)。如果兩條電線發(fā)生交叉，則會發(fā)生電流短路。所以，不允許電線間的交叉。每對互連的針腳被稱為網(wǎng)組。我們的目標(biāo)是要確定對于給定的網(wǎng)組，能否合理地布設(shè)電線以使其不發(fā)生交叉。圖11a給出了一個布線的例子，其中有八個針腳和四個網(wǎng)組。四個網(wǎng)組分別是(1,4)，(2,3)，(5,6)和(7,8)。圖11b給出的布線方案有交叉現(xiàn)象發(fā)生（(1,4)和(2,3)之間），而圖11c則沒有交叉現(xiàn)象發(fā)生。由于四個網(wǎng)組可以通過合理安排而不發(fā)生交叉，因此可稱其為可布線開關(guān)盒（routable switch box）。（在具體實現(xiàn)時，還需要在兩個相鄰的電線間留出一定的間隔。我們要解決的問題是，給定一個開關(guān)盒布線實例，確定它是不是一個可布線的。圖11 開關(guān)盒布線原理圖作業(yè)要求：1、畫出給定矩形布線區(qū)域（包括需要連同的線網(wǎng)組），針腳和線網(wǎng)組在數(shù)據(jù)庫中存放，通過數(shù)據(jù)庫接口讀出。2、在自動布線的每一步，用圖形標(biāo)示其狀態(tài)。3、自動布線的過程可以通過定時器或多線程的方法，每一次布線的時間間隔可以自定，以人眼觀察比較舒服為宜，每一次的布線過程如能實現(xiàn)動畫最好。4、如需要，請定義相關(guān)的描述類。5、在程序中，請使用對話框設(shè)定需要的各種參數(shù)。6、布線完成后，請將結(jié)果存入數(shù)據(jù)庫中。7、統(tǒng)計算法耗時。五、迷宮問題（起評分26分）迷宮（maze）是一個矩形區(qū)域，它有一個入口和一個出口。在迷宮的內(nèi)部包含不能穿越的墻或障礙。在圖2-1所示的迷宮中，障礙物沿著行和列放置，它們與迷宮的矩形邊界平行。迷宮的入口在左上角，出口在右下角。假定用nm的矩陣來描述迷宮，位置(1,1)表示入口，(n,m)表示出口，n和m分別代表迷宮的行數(shù)和列數(shù)。迷宮中的每個位置都可用其行號和列號來指定。在矩陣中，當(dāng)且僅當(dāng)在位置(i,j)處有一個障礙時其值為1，否則其值為0。圖2-2給出了圖2-1中迷宮對應(yīng)的矩陣描述。迷宮老鼠（ratinamaze）問題要求尋找一條從入口到出口的路徑。路徑是由一組位置構(gòu)成的，每個位置上都沒有障礙，且每個位置（第一個除外）都是前一個位置的東、南、西或北的鄰居（如圖2-3所示）。圖2-1 圖2-2 圖2-3作業(yè)要求：1、在窗口中畫出初始時迷宮的狀態(tài)，迷宮隨機生成，并驗證其合法性(可以通行的迷宮)。2、在自動尋找迷宮路徑的每一步，用圖形標(biāo)示其狀態(tài)。3、自動尋找迷宮路徑可以通過定時器或多線程的方法，每一步的時間間隔可以自定，以人眼觀察比較舒服為宜，每一步的過程如能實現(xiàn)動畫最好。4、定義迷宮的描述類。5、在程序中，迷宮的大小及每步移動的時間間隔可以通過對話框設(shè)置（也應(yīng)該有默認值）。6、支持暫停功和繼續(xù)的功能（在自動尋徑過程中可以暫停，并繼續(xù)）。7、暫停后，可以將當(dāng)前的狀態(tài)保存。8、可以從7中保存的文件中讀出某個狀態(tài)，并繼續(xù)。六、殘缺棋盤問題（起評分30分）殘缺棋盤（defective chessboard）是一個有2k2k個方格的棋盤，其中恰有一個方格殘缺。圖4-1給出k2時各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。注意當(dāng)k=0時，僅存在一種可能的殘缺棋盤（如圖4-1a所示）。事實上，對于任意k，恰好存在22k種不同的殘缺棋盤。殘缺棋盤的問題是：要求用三格板（triominoes）覆蓋殘缺棋盤（如圖4-2所示）。在此覆蓋中，兩個三格板不能重疊，三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格。在這種限制條件下，所需要的三格板總數(shù)為(22k-1)/3?？梢则炞C(22k-1)/3是一個整數(shù)。k為0的殘缺棋盤很容易被覆蓋，因為它沒有非殘缺的方格，用于覆蓋的三格板的數(shù)目為0。當(dāng)k=1時，正好存在3個非殘缺的方格，并且這三個方格可用圖4-2中的某一方向的三格板來覆蓋。解決的思想：用分而治之方法可以很好地解決殘缺棋盤問題。這一方法可將覆蓋2k2k殘缺棋盤的問題轉(zhuǎn)化為覆蓋較小殘缺棋盤的問題。2k2k棋盤一個很自然的劃分方法就是將它劃分為如圖4-3a所示的4個2k-12k-1棋盤。注意到當(dāng)完成這種劃分后，4個小棋盤中僅僅有一個棋盤存在殘缺方格（因為原來的2k2k棋盤僅僅有一個殘缺方格）。首先覆蓋其中包含殘缺方格的2k-12k-1殘缺棋盤，然后把剩下的3個小棋盤轉(zhuǎn)變?yōu)闅埲逼灞P，為此將一個三格板放在由這3個小棋盤形成的角上，如圖4-3b所示，其中原2k2k棋盤中的殘缺方格落入左上角的2k-12k-1棋盤?？梢圆捎眠@種分割技術(shù)遞歸地覆蓋2k2k殘缺棋盤。當(dāng)棋盤的大小減為11時，遞歸過程終止。此時11的棋盤中僅僅包含一個方格且此方格殘缺，所以無需放置三格板。圖4-1圖4-2圖4-3作業(yè)要求：1、在窗口中畫出初始時的殘缺棋盤（棋盤的格數(shù)可以指定或在某個范圍內(nèi)隨機生成，殘缺格的位置隨機生成）。2、自動進行殘缺棋盤的覆蓋，覆蓋的過