2010計算機算法分析與設(shè)計任務(wù)書

算法分析與設(shè)計任務(wù)書算法分析與設(shè)計任務(wù)書 1 課程設(shè)計的目的課程設(shè)計的目的 算法分析與設(shè)計 是信息與計算科學(xué)專業(yè)集中實踐性環(huán)節(jié)之一 是學(xué)習(xí) 完 算法分析與設(shè)計 課程后進行的一次全面的綜合練習(xí) 其目的是 1 要達到理論與實際應(yīng)用相結(jié)合 使學(xué)生能夠?qū)W會常用的幾種算法思想 以及對算法進行分析 能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來 并 培養(yǎng)良好的程序設(shè)計技能 2 在實踐中認(rèn)識為什么要學(xué)習(xí)算法分析與設(shè)計 掌握算法的設(shè)計思想與 程序設(shè)計語言之間的關(guān)系 是前面所學(xué)知識的綜合和回顧 2 課程設(shè)計的基本要求課程設(shè)計的基本要求 1 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法 具備初步的獨立分析和設(shè)計 能力 2 初步掌握軟件開發(fā)過程的問題分析 系統(tǒng)設(shè)計 程序編碼 測試等基 本方法和技能 3 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力 4 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā) 培養(yǎng)軟件工作 者所應(yīng)具備的科學(xué)的工作方法和作風(fēng) 5 設(shè)計的題目要求達到一定工作量 并具有一定的深度和難度 6 編寫出課程設(shè)計說明書 3 課程設(shè)計內(nèi)容及安排課程設(shè)計內(nèi)容及安排 1 問題分析和任務(wù)定義 根據(jù)設(shè)計題目的要求 充分地分析和理解問題 明確問題要求做什么 而不是怎么做 限制條件是什么 2 邏輯設(shè)計 對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型 并按 照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊 定義主程序模塊和各抽象數(shù)據(jù)類型 邏 輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義 包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基 本操作的功能說明 各個主要模塊的算法 并畫出模塊之間的調(diào)用關(guān)系圖 3 詳細設(shè)計 定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽代碼算法 在這個 過程中 要綜合考慮系統(tǒng)功能 使得系統(tǒng)結(jié)構(gòu)清晰 合理 簡單和易于調(diào)試 抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝 基本操作的規(guī)格說明盡可能明確具 體 詳細設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作進行進一步的求精 寫出數(shù)據(jù)存 儲結(jié)構(gòu)的類型定義 寫出函數(shù)形式的算法框架 4 程序編碼 把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序 同時 加入一些注解和斷言 使程序中邏輯概念清楚 5 程序調(diào)試與測試 采用自底向上 分模塊進行 即先調(diào)試低層函數(shù) 能夠熟練掌握調(diào)試工具的各種功能 設(shè)計測試數(shù)據(jù)確定疑點 通過修改程序來 證實它或繞過它 調(diào)試正確后 認(rèn)真整理源程序及其注釋 形成格式和風(fēng)格良 好的源程序清單和結(jié)果 6 結(jié)果分析 程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的 輸入及其輸出結(jié)果 算法的時間 空間復(fù)雜性分析 7 撰寫課程設(shè)計報告 4 課程設(shè)計報告的內(nèi)容課程設(shè)計報告的內(nèi)容 設(shè)計結(jié)束后要寫出課程設(shè)計報告 以作為整個課程設(shè)計評分的書面依據(jù)和 存檔材料 設(shè)計報告以規(guī)定格式的電子文檔書寫 打印并裝訂 排版及圖 表 要清楚 工整 內(nèi)容及要求詳見 課程設(shè)計報告規(guī)范 其中 3 課程設(shè)計 報告內(nèi)容 中一般應(yīng)包括以下內(nèi)容 4 1 需求分析需求分析 以無歧義陳述說明程序設(shè)計的任務(wù) 強調(diào)的是程序要做什么 并明確規(guī)定 1 輸入的形式和輸入值的范圍 2 輸出的形式 3 程序所能達到的功能 4 測試數(shù)據(jù) 包括正確的輸入和輸出結(jié)果 含有錯誤的輸入和輸出結(jié)果 4 2 概要設(shè)計概要設(shè)計 說明本程序中用到的所有抽象數(shù)據(jù)類型的定義 主控程序的流程以及各程 序模塊之間的層次 調(diào)用 關(guān)系 4 3 詳細設(shè)計詳細設(shè)計 實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型 對每個操作只需要寫出偽代碼算法 對主程序和其他模塊也都需要寫出偽代碼算法 偽代碼算法達到的詳細程度建 議為 按照偽代碼算法可以在計算機鍵盤直接輸入高級程序設(shè)計語言程序 可采用流程圖 N S 圖或PAD 圖進行描述 畫出函數(shù)和過程的調(diào)用關(guān)系圖 4 4 調(diào)試分析調(diào)試分析 內(nèi)容包括 調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧 討論和分析 4 5 測試結(jié)果測試結(jié)果 列出你的測試結(jié)果 包括輸入和輸出 這里的測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格 最好多于需求分析中所列 4 6 用戶使用說明用戶使用說明 說明如何使用你編寫的程序 詳細列出每一步的操作步驟 5 課程設(shè)計考核方法及成績評定課程設(shè)計考核方法及成績評定 課程設(shè)計結(jié)束時 要求學(xué)生寫出課程設(shè)計報告 可不附源程序 可運行 的軟件系統(tǒng) 包括源程序 課程設(shè)計成績分兩部分 設(shè)計報告及軟件系統(tǒng)占70 集中上機占30 6 進度安排進度安排 整體設(shè)計和詳細設(shè)計 2天 編寫代碼 2天 調(diào)試和測試 2天 課程設(shè)計報告書寫 1天 演示軟件和答辯 另行安排 7 課程設(shè)計題目課程設(shè)計題目 7 1 棋盤覆蓋棋盤覆蓋 間題描述 在一個2k 2k 個方格組成的棋盤中 恰有一個方格與其它方格不同 稱該 方格為一特殊方格 且稱該棋盤為一特殊棋盤 在棋盤覆蓋問題中 要用圖示 的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格 且任何2個L型骨牌不得重疊覆蓋 基本要求 1 輸入k以及特殊方格所在的行號dr和特殊方格的列號dc 2 要求輸出每一步用什么形態(tài)L型骨牌覆蓋 覆蓋后得到的棋盤圖形 3 如果輸出的結(jié)果只是用矩陣表示則為良好 用圖形表示則為優(yōu) 測試數(shù)據(jù) 實現(xiàn)提示 使用分治策略 把棋盤劃分成4個小棋盤 然后用一個L型骨牌覆蓋將這4個 小棋盤變?yōu)槎季哂刑厥夥礁竦钠灞P 7 2 Hanoi 塔問題 塔問題 問題描述 設(shè)a b c是三個塔座 開始時 在塔座a上有一疊共n個圓盤 這些圓盤自 下而上 由大到小地疊放在一起 各圓盤從小到大編號為1 2 n 要求將塔 座a上的這一疊圓盤移到塔座b上 并仍按同樣順序疊置 在移動圓盤時應(yīng)遵守 以下移動規(guī)則 規(guī)則 1 每次只能移動一個圓盤 規(guī)則 2 任何時刻都部允許將較大的圓盤壓在較小的圓盤之上 規(guī)則 3 在滿足移動規(guī)則 1 和 2 的前提下 可將圓盤移至a b c 中任一塔座上 基本要求 1 設(shè)計出Hannoi塔游戲 供用戶玩 2 提供正確的搬運方法 實現(xiàn)說明 正確的搬運方法使用遞歸方法實現(xiàn) 測試數(shù)據(jù) 7 3 矩陣連乘問題矩陣連乘問題 問題描述 給定n個矩陣 其中和是可乘的 i 1 2 n 1 考察 12 n A AA i A 1i A 這n個矩陣的連乘積 通過加括號方式 找出矩陣乘積所需的最少計 12 n A AA 算量的方法 基本要求 輸入每個矩陣的行和列 要求輸出最少計算量的矩陣乘積方法 如 1234 A A A A 實現(xiàn)說明 使用動態(tài)規(guī)劃方法 7 4 多邊形游戲 多邊形游戲 問題描述 多邊形游戲是一個單人玩的游戲 開始時有一個由n個頂點構(gòu)成的多邊形 每個頂點被賦予一個整數(shù)值 每條邊被賦予一個運算符 或 所有邊 依次用整數(shù)從1到n編號 游戲第1步 將一條邊刪除 隨后n 1步按以下方式操作 選擇一條邊E及由E連接著的2個頂點v1和v2 用一個新的頂點取代邊E及用E連接著的2個頂點v1和v2 將由頂點v1和v2的 整數(shù)值通過邊E上的運算得到的結(jié)果賦予新頂點 最后 所有邊都被刪除 游戲結(jié)束 游戲的得分就是所剩頂點上的整數(shù)值 基本要求 設(shè)計該游戲供用戶玩 對于給定的多邊形 給出最高得分計算 實現(xiàn)說明 使用動態(tài)規(guī)劃方法 7 5 0 1 背包問題背包問題 問題描述 給定n種物品和一背包 物品i的重量是 其價值為 背包的容量為c i w i v 問應(yīng)如何選擇裝入背包種的物品 使得裝入背包種物品的總價值最大 基本要求 使用動態(tài)規(guī)劃 回溯法以及分支界限三種方法實現(xiàn) 測試數(shù)據(jù) 實現(xiàn)提示 7 6 排序方法排序方法 問題描述 給定n個元素 要求對這n個元素進行排序 基本要求 使用多種排序方法 越多越好 比較每種排序方法的時間復(fù)雜度和空間復(fù)雜度 測試數(shù)據(jù) 實現(xiàn)提示 7 7 哈夫曼編碼譯碼器哈夫曼編碼譯碼器 問題描述 設(shè)計一個哈夫曼編碼 譯碼系統(tǒng) 對一個文本文件中的字符進行哈夫曼編碼 生成編碼文件 壓縮文件 后綴名 cod 反過來 可將一個壓縮文件譯碼還原為一個 文本文件 txt 基本要求 1 輸入一個待壓縮的英文文本文件 統(tǒng)計文本文件中各字符的個數(shù)作為 權(quán)值 生成哈夫曼樹 2 將文本文件利用哈夫曼樹進行編碼 生成壓縮文件 后綴名cod 3 輸入一個待解壓的壓縮文件名稱 并利用相應(yīng)的哈夫曼樹將編碼序列 譯碼 實現(xiàn)說明 1 在構(gòu)造哈夫曼樹時 可以利用不同的線性表存放二叉樹 用順序表 單鏈表 循環(huán)單鏈表 雙向鏈表 循環(huán)雙鏈表 2 在構(gòu)造哈夫曼樹時 可以利用優(yōu)先隊列存放二叉樹 順序隊列 鏈隊 列 可以是單鏈表 雙鏈表等 還可以用靜態(tài)結(jié)構(gòu)去實現(xiàn) 可以分別在入隊 列或出隊列時實現(xiàn)優(yōu)先級 3 二叉樹本身也可以用靜態(tài)數(shù)組模擬 4 使用貪心算法 7 8 迷宮問題 迷宮問題 問題描述 設(shè)計一個迷宮并給出正確走法 如 001111111111111 100011111111111 101100001111111 100011100000111 111011111110001 111000000001001 111000000011100 其中0表示可以走 1表示不能走 每一步只能向上下左右移動 基本要求 1 給出迷宮的正確走法 包括沒有解的情況 2 要求界面友好 測試數(shù)據(jù) 實現(xiàn)提示 使用回溯的方法 7 9 繼續(xù)郵資問題繼續(xù)郵資問題 問題描述 假設(shè)某國家發(fā)行了n種不同面值的郵票 并且規(guī)定每張信封上最多只允許貼 m張郵票 連續(xù)郵資問題要求對于給定的n和m的值 給出郵票面值的最佳設(shè)計 在1張信封上貼出從郵資1開始 增量為1的最大連續(xù)郵資區(qū)間 基本要求 輸入任意的m和n都能設(shè)計出最佳的方案 并給出連續(xù)郵資區(qū)間 實現(xiàn)說明 測試數(shù)據(jù) 7 10 圖的圖的 m 著色問題著色問題 問題描述 給定一個地圖 要求給出該地圖的最少著色方案 基本要求 1 把地圖以及最少著色的方案顯示出來則為良好 2 有友好的界面則為優(yōu) 實現(xiàn)說明 7 11 猜數(shù)字游戲 猜數(shù)字游戲 問題描述 孩子想1個由4種顏色組成的序列 4種顏色不一定完全不同 每種顏色只 能是6種顏色之一 方便起見 我們用數(shù)字1到6表示6種顏色 計算機必須根據(jù)孩子的回答找出孩子所想的顏色序列 計算機在屏幕上顯 示一個序列 孩子用鍵盤回答以下兩個問題 猜對的顏色中位置不對的有幾個 猜對的顏色中位置對的有幾個 基本要求 編程使至多6次問答后猜出序列 如果辦不到 至多10次問答后猜出序列 實現(xiàn)說明 測試數(shù)據(jù) 如孩子想的是4655 計算機猜想 顏色對位置錯的數(shù)目 顏色和位置都對的數(shù)目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 4655 0 4 7 12 大整數(shù)計算器大整數(shù)計算器 問題描述 設(shè)計一個計算器實現(xiàn)兩個任意長得整數(shù)的加 減 乘 除 基本要求 設(shè)計一個實現(xiàn)任意長的整數(shù)進行四則運算的演示程序 要求輸入任意長的 整數(shù)進行四則運算 都能得到精確的結(jié)果 實現(xiàn)說明 7 13 查找搜索技術(shù)查找搜索技術(shù) 問題描述 給定任意的數(shù)組 對于給定的數(shù) 查找是否在數(shù)組中 如果在 則返回給 定數(shù)在數(shù)組的位置 不在則返回不在信息 基本要求 1 使用多種搜索方法 越多越好 其中二分搜索技術(shù) 線性時間選擇是 必須的 2 比較每種排序方法的時間復(fù)雜度和空間復(fù)雜度 實現(xiàn)說明 7 14 Tom Jerry 和奶酪 和奶酪 問題描述 貓Tom和鼠Jerry同住在一矩陣地窖中 貓要吃鼠 鼠要吃奶酪 地窖中有2 種地磚 有洞磚與無洞磚 一個洞足以讓鼠鉆入 但貓不能 以菜單形式完成以下任務(wù) 隨機地生成一個地窖 并給貓 鼠和奶酪安排一個位置 如 fffffffffffffff fppppppppppppCf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fppppppppppTppf fffffffffffffff 其中c表示貓 j表示鼠 h表示洞 f表示不能通行 2 鼠先行 貓后行 兩者皆滿足以下規(guī)定 1 必須上 下 左或右移動 2 鼠必須走1步 穿過p或h 3 貓必須走1或2步 穿過p 3 當(dāng)鼠吃到奶酪或貓抓到鼠時 游戲結(jié)束 基本要求 實現(xiàn)說明 7 15 布線問題布線問題 問題描述 印刷電路板將布線區(qū)域劃分成n m個方格陣列 精確的電路布線問題要求 確定連接方格a的中點到方格b的中點的最短布線方案 在布線時 電路只能沿 著直線或直角布線 為了避免線路相交 已布了線的方格做了封鎖標(biāo)記 其他 線路不允許穿過被封鎖的方格 基本要求 1 解決題目的問題 2 提供友好的界面 實現(xiàn)說明 使用分支限界法 7 16 魔方工具包魔方工具包 問題描述 一個魔方是一個由3 3 3個小立方體組成的立方體 最初立方體的6個面 分別涂上不同顏色 我們稱之為 最初魔方 魔方的每一面上的3 3個小立 方體組成它的一層 魔方所能見到的每一層 6個面 都能旋轉(zhuǎn)90 180 270或360度 所有層 的旋轉(zhuǎn)軸都垂直于面且通過其中心 旋轉(zhuǎn)的結(jié)果是另一個魔方 它的所有面的 顏色都改變了 現(xiàn)在我們用字符來代替顏色 U 上 D 下 F 前 B 后 L 左 R 右 任 何一個序列的旋轉(zhuǎn)都能表示成 U R F B L D 中一些字符組成的字符串 其中每 個字符表示它所指定的面順時針旋轉(zhuǎn)90度 基本要求 1 編程完成以下3個任務(wù) 菜單形式 你可以假設(shè)任何輸入的字串長 度都 35 你的算法能處理非法輸入的情況 如 輸入 輸出 L L LL LL LLL LLL LLLL 空串 LLLLL L LLRRRFFFFRLB LLLB HELLO error 2 判斷輸入的2個字串的旋轉(zhuǎn)結(jié)果是否相同 如 輸入一 輸入二 輸出 RU UR no RRFFRRFFRRFFRRFF FFRRFFRR yes RRFFRRFFRRFFRRFF RRFFRRFF no 3 求出輸入字符串至少須使用幾次才能將魔方轉(zhuǎn)回到 最初魔方 一 定大于0 輸入 輸出 L 4 DD 2 BULB 36 RUF 80 BLUFF 180 實現(xiàn)說明 7 17 圖的建立與輸出圖的建立與輸出 問題描述 建立圖的存儲結(jié)構(gòu) 圖的類型可以是有向圖 無向圖 有向網(wǎng) 無向網(wǎng) 學(xué)生可以任選兩種類型 能夠輸入圖的頂點和邊的信息 并存儲到相應(yīng)存儲 結(jié)構(gòu)中 而后輸出圖的鄰接矩陣 基本要求 給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法 并給出遍歷過程的動態(tài)演示效果 實現(xiàn)說明 無 7 18 圖的建立與輸出圖的建立與輸出 問題描述 建立圖的存儲結(jié)構(gòu) 圖的類型可以是有向圖 無向圖 有向網(wǎng) 無向網(wǎng) 學(xué)生可以任選兩種類型 能夠輸入圖的頂點和邊的信息 并存儲到相應(yīng)存儲 結(jié)構(gòu)中 而后輸出圖的鄰接矩陣 基本要求 給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法 并給出遍歷過程的動態(tài)演示效果 實現(xiàn)說明 無 7 19 以隊列實現(xiàn)的仿真技術(shù)預(yù)測理發(fā)館的經(jīng)營狀況 以隊列實現(xiàn)的仿真技術(shù)預(yù)測理發(fā)館的經(jīng)營狀況 問題描述 理發(fā)館一天的工作過程如下 1 理發(fā)館有 N 把理發(fā)椅 可同時為 N 位顧客進行理發(fā) 2 理發(fā)師分三個等級 一級 二級 三級 對應(yīng)不同的服務(wù)收費 3 當(dāng)顧客進門時 需選擇某級別理發(fā)師 只要該級別的理發(fā)師有空椅 則可立即坐下理發(fā) 否則需排隊等候 4 一旦該級別的理發(fā)師有顧客理發(fā)完離去 排在隊頭的顧客便可開始 理發(fā) 5 若理發(fā)館每天連續(xù)營業(yè) T 分鐘 求 1 一天內(nèi)顧客在理發(fā)館內(nèi)的平均逗留時間 2 顧客排隊等候理發(fā)的隊列長度平均值 3 營業(yè)時間到點后仍需完成服務(wù)的收尾工作時間 4 統(tǒng)計每天的營業(yè)額 5 統(tǒng)計每天不同級別理發(fā)師的創(chuàng)收 基本要求 1 模擬理發(fā)館一天的工作過程 必須采用事件驅(qū)動的離散模型 參考教科 書 3 5 節(jié)離散事件模擬 p65 2 每個顧客到達和下一顧客到達時間的間隔應(yīng)是隨機的 3 理發(fā)師編號 理發(fā)師級別和每天的營業(yè)時間由用戶輸入 4 某顧客挑選某一個級別的理發(fā)師而不得時 選第一個隊列排隊等待 5 每個顧客進門時將生成三個隨機數(shù) 1 durtime 進門顧客理發(fā)所需服務(wù)時間 簡稱 理發(fā) 時間 2 intertime 下一顧客將到達的時間間隔 簡稱 間 隔時間 3 select 服務(wù)選項 6 服務(wù)收費 應(yīng)包含服務(wù)時間和理發(fā)師級別兩個因素 7 除了輸出統(tǒng)計的數(shù)據(jù)外 還需