算法設(shè)計(jì)課程設(shè)計(jì)任務(wù)書(shū)

1、算法設(shè)計(jì)與分析課程設(shè)計(jì)任務(wù)書(shū)所屬學(xué)期：10-11-2 下達(dá)時(shí)間：完成班級(jí)：信本08【設(shè)計(jì)目的】本課程設(shè)計(jì)是信息與計(jì)算科學(xué)專業(yè)重要的實(shí)踐性環(huán)節(jié)之一，是在學(xué)生學(xué)習(xí)完算法設(shè)計(jì) 與分析課程后進(jìn)行的一次全面的綜合練習(xí)。本課程設(shè)計(jì)的目的和任務(wù)：（1）鞏固和加深學(xué) 生對(duì)本課程的基本知識(shí)的理解和掌握；（3）掌握基本算法的設(shè)計(jì)與實(shí)現(xiàn)；（3）掌握算法設(shè)計(jì) 的基本思想；（4）提高解決實(shí)際問(wèn)題的能力；（5）掌握書(shū)寫(xiě)程序設(shè)計(jì)說(shuō)明文檔的能力?！驹O(shè)計(jì)內(nèi)容與任務(wù)】題目一：五子棋游戲軟件設(shè)計(jì)設(shè)計(jì)內(nèi)容：設(shè)計(jì)一程序能完成五子棋游戲功能。五子棋規(guī)則：雙方各執(zhí)一色棋子，輪流下子（即將棋子放在棋盤 的任一空交叉點(diǎn)上），直到有一方的棋子有

2、5個(gè)排成一線（無(wú)論是橫向、豎向還是斜向均可），則棋局結(jié) 束，該方勝利。設(shè)計(jì)要求：（1）設(shè)計(jì)游戲的核心算法；（2）設(shè)計(jì)可視化的界面且雙方所使用的兩色棋子和彩色棋盤得體大方、比例恰當(dāng)；（3）雙方輪流用鍵盤或鼠標(biāo)下子。只有當(dāng)鼠標(biāo)單擊在棋盤網(wǎng)格交叉點(diǎn)附近時(shí)才可下子，點(diǎn)擊其他地方及已有子的位置不能下子，且應(yīng)給出相應(yīng)提示；（4）在適當(dāng)位置可顯示比賽結(jié)果，比賽中能隨時(shí)存儲(chǔ)當(dāng)前棋局。題目二：象棋游戲軟件設(shè)計(jì)設(shè)計(jì)內(nèi)容：中國(guó)象棋是中國(guó)一種流傳十分廣泛的游戲。下棋雙方根據(jù)自己對(duì)棋局形式的理解和對(duì)棋藝規(guī)律的掌 握，調(diào)動(dòng)車馬，組織兵力，協(xié)調(diào)作戰(zhàn)在棋盤一一這塊特定的戰(zhàn)場(chǎng)上進(jìn)行著象征性的軍事戰(zhàn)斗。設(shè)計(jì)軟件能 實(shí)現(xiàn)此游戲。游

3、戲規(guī)則：“將”或“帥”的移動(dòng)范圍只能在王宮內(nèi)，移動(dòng)規(guī)則為每一步只可以水平或垂直移動(dòng)一點(diǎn)?！笆俊钡囊苿?dòng)范圍只能在王宮內(nèi)，移動(dòng)規(guī)則為每一步只可以沿對(duì)角線方向移動(dòng)一點(diǎn)?！跋蟆钡囊苿?dòng)范圍為河界的一側(cè)，移動(dòng)規(guī)則為每一步只可以沿對(duì)角線方向移動(dòng)兩點(diǎn)，另外，在移動(dòng)的 過(guò)程中不能夠穿越障礙?！榜R”的移動(dòng)范圍為任何位置，移動(dòng)規(guī)則為每一步只可以水平或垂直移動(dòng)一點(diǎn)，再按對(duì)角線方面向左 或者右移動(dòng)。另外，在移動(dòng)的過(guò)程中不能夠穿越障礙?！败嚒钡囊苿?dòng)范圍為任何位置，移動(dòng)規(guī)則為可以水平或垂直方向移動(dòng)任意個(gè)無(wú)阻礙的點(diǎn)?！芭凇钡囊苿?dòng)范圍為任何位置，移動(dòng)規(guī)則為和車相似，但它必須跳過(guò)一個(gè)棋子來(lái)吃掉對(duì)方的一個(gè)棋子?！氨钡囊苿?dòng)范圍為任

4、何位置，移動(dòng)規(guī)則：每步只能向前移動(dòng)一點(diǎn)。過(guò)河以后，它便增加了向左右移 動(dòng)的能力，兵不允許向后移動(dòng)。設(shè)計(jì)要求：設(shè)計(jì)游戲的核心算法；設(shè)計(jì)可視化的界面且雙方所使用的兩色棋子和彩色棋盤得體大方、比例恰當(dāng)；棋子活動(dòng)的場(chǎng)所棋盤，在長(zhǎng)方形的平面上，繪九條平行的豎線和十條平行的橫線相交組成，共 九十個(gè)交叉點(diǎn)，棋子就擺在這些交叉點(diǎn)上。中間第五、第六兩橫線之間未畫(huà)豎線的空白地帶，稱為河界 ，整個(gè)棋盤就以河界分為相等的兩部分；兩方“將”“帥”坐鎮(zhèn)。各棋子為：紅方：帥(1)、仕(2)、相(2)、車(2)、馬(2)、炮(2)、兵(5)黑方：將(1)、士 (2)、象(2)、車(2)、馬(2)、炮(2)、卒(5)雙方輪流用

5、鍵盤或鼠標(biāo)下子。只有當(dāng)鼠標(biāo)單擊在棋盤網(wǎng)格交叉點(diǎn)附近時(shí)才可下子，點(diǎn)擊其他地方及已有子的位置不能下子，且應(yīng)給出相應(yīng)提示；在適當(dāng)位置可顯示比賽結(jié)果，比賽中能隨時(shí)存儲(chǔ)當(dāng)前棋局。題目三：跳棋游戲軟件設(shè)計(jì)設(shè)計(jì)內(nèi)容：跳棋在我國(guó)是一項(xiàng)老少皆宜、流傳廣泛的益智型棋類游戲。由于其規(guī)則簡(jiǎn)單，一玩就懂，一輩子都不 會(huì)忘，所以幾乎每個(gè)人從小到大都下過(guò)跳棋。設(shè)計(jì)一程序能完成跳棋游戲功能。跳棋規(guī)則和勝負(fù)判定方法如下：首先，游戲參與人數(shù)必須是偶數(shù)，即2人、4人或者6人，然后與對(duì)角線的一方對(duì)抗。棋子的移動(dòng)可 以一步步在有直線連接的相鄰六個(gè)方向進(jìn)行，如果相鄰位置上有任何方的一個(gè)棋子，該位置直線方向下一 個(gè)位置是空的，則可以直接跳

6、到該空位上，跳的過(guò)程中，只要相同條件滿足就可以連續(xù)進(jìn)行。誰(shuí)最先 把正對(duì)面的陣地全部占領(lǐng)，誰(shuí)就取得勝利。設(shè)計(jì)要求：設(shè)計(jì)游戲的核心算法；設(shè)計(jì)可視化的界面且雙方所使用的兩色棋子和彩色棋盤得體大方、比例恰當(dāng)；雙方輪流用鼠標(biāo)出子；在適當(dāng)位置可顯示比賽結(jié)果，比賽中能隨時(shí)存儲(chǔ)當(dāng)前棋局。題目四：24點(diǎn)游戲軟件設(shè)計(jì)設(shè)計(jì)內(nèi)容：24點(diǎn)游戲?yàn)殡S機(jī)產(chǎn)生的四個(gè)數(shù)，通過(guò)四則計(jì)算(每個(gè)數(shù)只能使用一次)，使其結(jié)果為24.本游戲?qū)ε?養(yǎng)人們的注意力、計(jì)算力(尤其是心算能力)，開(kāi)闊人們的思路，大有益處。游戲規(guī)則為：每次由計(jì)算機(jī)隨機(jī)給出1至10四個(gè)數(shù)字，使用這些數(shù)字計(jì)算，使結(jié)果等于24。要求：只能使用加、減、乘、除四種運(yùn)算；每一數(shù)字

7、必須且只能使用一次。如果用戶能做題目，則可以通過(guò)把數(shù)字拖到兩個(gè)方框中，并選擇一種運(yùn)算來(lái)顯示他的計(jì)算步驟。 每一步驟，只能計(jì)算兩個(gè)方框中的數(shù)字，其結(jié)果能用于下一步。例如，如果給出數(shù)字1、2、3和4；可以這樣做：步驟 1： 3*4=12步驟 2： 2*12=24步驟3： 24*1=24(每一數(shù)字必須被使用一次)有時(shí)不能從諸如1、1、1、1或者9、9、9、9的四個(gè)數(shù)中得到結(jié)果“24”，當(dāng)遇到困難或確信不能得 到數(shù)字“ 24 ”時(shí)，可以點(diǎn)按“幫助”按鈕查看答案或者點(diǎn)按“開(kāi)始”按鈕做下一道題。設(shè)計(jì)要求：設(shè)計(jì)游戲的核心算法；設(shè)計(jì)可視化的界面；能隨機(jī)產(chǎn)生4個(gè)1位數(shù)并顯示；用戶能利用鼠標(biāo)或鍵盤選擇給出的數(shù)和運(yùn)

8、算符；程序能判別正誤并計(jì)分；能給出幫助和能重產(chǎn)生數(shù)。題目五：利用貪婪算法實(shí)現(xiàn)多種實(shí)際問(wèn)題設(shè)計(jì)內(nèi)容：給出多種可以用貪婪算法解決的典型問(wèn)題，并分析、證明、編程。設(shè)計(jì)要求：貪婪算法的基本思想；給出背包問(wèn)題的貪婪算法；給出有限期計(jì)算機(jī)作業(yè)調(diào)度的貪婪算法；給出上面兩個(gè)算法的證明；給出上面兩個(gè)算法的程序。給出時(shí)間復(fù)雜度。題目六：遞歸算法的應(yīng)用設(shè)計(jì)內(nèi)容：實(shí)現(xiàn)多種問(wèn)題的遞歸算法并分析、總結(jié)，給出結(jié)論。設(shè)計(jì)要求：給出01背包問(wèn)題的遞歸算法和程序；給出n階hanoi塔的遞歸算法和程序；給出棋子移動(dòng)的遞歸算法和程序；給出n個(gè)元素全排列的遞歸算法和程序；總結(jié)哪些問(wèn)題可能用遞歸算法實(shí)現(xiàn)。題目七：回溯法的應(yīng)用設(shè)計(jì)內(nèi)容：給

9、出多種可以用貪婪算法解決的典型問(wèn)題，并分析、編程和總結(jié)。設(shè)計(jì)要求：給出回溯法的基本思想；給出n后問(wèn)題的回溯算法和程序；給出子集和樹(shù)問(wèn)題的回溯算法和程序；給出哈密頓回路的回溯算法和程序。題目八：動(dòng)態(tài)規(guī)劃算法的應(yīng)用設(shè)計(jì)內(nèi)容：實(shí)現(xiàn)多種問(wèn)題的動(dòng)態(tài)規(guī)劃算法并分析、編程和總結(jié)，給出結(jié)論。設(shè)計(jì)要求：給出動(dòng)態(tài)規(guī)劃的基本思想；給出最小代價(jià)子母樹(shù)的動(dòng)態(tài)規(guī)劃算法和程序；給出最短路徑的動(dòng)態(tài)規(guī)劃算法和程序；給出最優(yōu)樹(shù)的動(dòng)態(tài)規(guī)劃算法和程序。題目九：分治法的應(yīng)用設(shè)計(jì)內(nèi)容：利用分治法實(shí)現(xiàn)多種問(wèn)題，并分析、編程和總結(jié)，給出結(jié)論。設(shè)計(jì)要求：給出分治法思想；給出數(shù)據(jù)查找的算法和程序；給出合并排序算法和程序；給出快速排序算法和程序；

10、給出矩陣乘法的分治算法和程序；給出多項(xiàng)式乘法的分治法和程序；給出分治法的時(shí)間復(fù)雜度。題目十一：用二分搜索法查找數(shù)據(jù)設(shè)計(jì)內(nèi)容：折半查找法也稱為二分查找法或二分搜索法，它充分利用了元素間的次序關(guān)系，采用分治策略而較快 地查找數(shù)據(jù)。現(xiàn)要求給出一個(gè)待查找的實(shí)例，并給出二分搜索算法，編寫(xiě)程序利用此算法實(shí)現(xiàn)查找。設(shè)計(jì)要求：給出分治思想；給出一個(gè)實(shí)際應(yīng)用；給出二分搜索算法；編程實(shí)現(xiàn)算法；給出算法的時(shí)間復(fù)雜度分析。題目十二：用探索(窮舉)法求解貨郎擔(dān)問(wèn)題設(shè)計(jì)內(nèi)容：貨郎擔(dān)問(wèn)題又稱推銷員問(wèn)題，是組合數(shù)學(xué)中的一個(gè)著名問(wèn)題。求解四個(gè)城市的貨郎擔(dān)問(wèn)題，距離關(guān)系 如下：1到2、3、4城的距離分別為6、7、92到1、3、4

11、城的距離分別為8、9、73到1、2、4城的距離分別為5、8、84到1、2、3城的距離分別為6、5、5當(dāng)推銷員從1城出發(fā)，經(jīng)過(guò)每個(gè)城市一次且僅一次，最后回到1城，問(wèn)按照怎樣的路線走，使總的行 程距離最短。設(shè)計(jì)要求：給出求解算法；編程實(shí)現(xiàn)此算法；以圖形化界面各城市間及各城市間的路徑和距離；給出時(shí)間復(fù)雜度分析。題目十三：用分支限界法求解0/1背包問(wèn)題設(shè)計(jì)內(nèi)容：分枝限界是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè) 活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所 有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出(最優(yōu))可

12、行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后 從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng) 表為空，擴(kuò)充過(guò)程才結(jié)束。現(xiàn)要求給出一個(gè)具體的0/1背包問(wèn)題，并用分支限界法求解之。設(shè)計(jì)要求：給出一個(gè)實(shí)例；編寫(xiě)算法；編程實(shí)現(xiàn)；給出分析。十四.自命題【設(shè)計(jì)要求】1、分析課程設(shè)計(jì)題目的要求2、寫(xiě)出詳細(xì)設(shè)計(jì)說(shuō)明3、編寫(xiě)程序代碼，調(diào)試程序使其能正確運(yùn)行4、設(shè)計(jì)完成的軟件要便于操作和使用5、設(shè)計(jì)完成后提交課程設(shè)計(jì)報(bào)告，課程設(shè)計(jì)報(bào)告內(nèi)容包括：課程設(shè)計(jì)目的、設(shè)計(jì)任務(wù)與 要求、設(shè)計(jì)說(shuō)明書(shū)、設(shè)計(jì)成果和設(shè)計(jì)心得五個(gè)部分，具體要求見(jiàn)設(shè)計(jì)報(bào)告模板。6、分組：最多兩個(gè)人一組，提供一份設(shè)計(jì)說(shuō)明書(shū)，并注明任務(wù)分工。每組題目不能相 同?！驹O(shè)計(jì)時(shí)間】13周-16周【設(shè)計(jì)報(bào)告】設(shè)計(jì)報(bào)告內(nèi)容不少3000字。其正文一般有如下幾個(gè)方面的內(nèi)容：1、課程設(shè)計(jì)名稱、班級(jí)號(hào)、學(xué)號(hào)、學(xué)生姓名和課程設(shè)計(jì)起止日期2、課程設(shè)計(jì)目的和要求3、課程設(shè)計(jì)任務(wù)內(nèi)容4、詳細(xì)設(shè)計(jì)說(shuō)明5、軟件使用說(shuō)明6、課程設(shè)計(jì)心得與體會(huì)7、附錄1：參考文獻(xiàn)8、附錄2：部分程序清單（帶有較詳細(xì)的注釋）【提交要求】（1）每組需獨(dú)立提交書(shū)面設(shè)計(jì)報(bào)告書(shū)，要求編排格式統(tǒng)一、規(guī)范、內(nèi)容充實(shí)（3）提交日期：第17周以前，以班為