2010計算機算法分析與設計任務書

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