《演算法設計與分析》
課程實驗指導書
劉莉平編寫
課程編號 320132x1
總學時 48
實驗學時 10
課外學時 20
中南大學軟體學院
2023年11月
實驗學時:2
每組人數:1
實驗型別:2 (1:基礎性 2:綜合性 3:設計性 4:研究性)
實驗要求:1(1:必修 2:選修 3:其它)
實驗類別:2 (1:基礎 2:專業基礎 3:專業 4:其它)
一、實驗目的
1. 了解分治策略演算法思想
2. 掌握快速排序、歸併排序演算法
3. 了解其他分治問題典型演算法
二、實驗內容
1.編寫乙個簡單的程式,實現歸併排序。
2. 編寫一段程式,實現快速排序。
3. 編寫程式實現迴圈賽日程表。設有n=2k個運動員要進行網球迴圈賽。
現要設計乙個滿足以下要求的比賽日程表:(1)每個選手必須與其它n-1個選手各賽一次(2)每個選手一天只能賽一場(3)迴圈賽進行n-1天
三、實驗要求:
1.實驗前必須充分預習;
2. 實驗過程中仔細觀察實驗現象,認真記錄實驗結果;
3. 實驗後每個同學必須要求獨立完成實驗報告。
四、實驗步驟
1.寫出源程式,並編譯執行
2.詳細記錄程式除錯及執行結果
五、實驗報告
1.完成本專案實驗後,學生應提交實驗報告。
2.實驗報告格式與要求見附件。
實驗學時:2
每組人數:1
實驗型別:3 (1:基礎性 2:綜合性 3:設計性 4:研究性)
實驗要求:1(1:必修 2:選修 3:其它)
實驗類別:2 (1:基礎 2:專業基礎 3:專業 4:其它)
一、實驗目的
1. 了解貪心演算法思想
2. 掌握貪心法典型問題,如揹包問題、作業排程問題等。
二、實驗內容
1. 編寫乙個簡單的程式,實現單源最短路徑問題。
2. 編寫一段程式,實現找零。
【問題描述】當前有面值分別為2角5分,1角,5分,1分的硬幣,請給出找n分錢的最佳方案(要求找出的硬幣數目最少)。
3. 編寫程式實現多機排程問題
【問題描述】要求給出一種作業排程方案,使所給的n個作業在盡可能短的時間內由m臺機器加工處理完成。約定,每個作業均可在任何一台機器上加工處理,但未完工前不允許中斷處理。作業不能拆分成更小的子作業。
三、實驗要求:
1.實驗前必須充分預習;
2. 實驗過程中仔細觀察實驗現象,認真記錄實驗結果;
3. 實驗後每個同學必須要求獨立完成實驗報告。
四、實驗步驟
1.寫出源程式,並編譯執行
2.詳細記錄程式除錯及執行結果
五、實驗報告
1.完成本專案實驗後,學生應提交實驗報告。
2.實驗報告格式與要求見附件。
實驗學時:2
每組人數:1
實驗型別:3 (1:基礎性 2:綜合性 3:設計性 4:研究性)
實驗要求:1(1:必修 2:選修 3:其它)
實驗類別:2 (1:基礎 2:專業基礎 3:專業 4:其它)
一、實驗目的
1. 掌握動態規劃方法貪心演算法思想
2. 掌握最優子結構原理
3. 了解動態規劃一般問題
二、實驗內容
1. 編寫乙個簡單的程式,解決0-1揹包問題。設n=5,c=10,w=,v=
2. 合唱隊形安排問題
【問題描述】n位同學站成一排,**老師要請其中的(n-k)位同學出列,使得剩下的k位同學排成合唱隊形。合唱隊形是指這樣的一種隊形:設k位同學從左到右依次編號為1,2…,k,他們的身高分別為t1,t2,…,tk, 則他們的身高滿足t1<...
ti+1>…>tk(1<=i<=k)。已知所有n位同學的身高,計算最少需要幾位同學出列,可以使得剩下的同學排成合唱隊形。
三、實驗要求:
1.實驗前必須充分預習;
2. 實驗過程中仔細觀察實驗現象,認真記錄實驗結果;
3. 實驗後每個同學必須要求獨立完成實驗報告。
四、實驗步驟
1.寫出源程式,並編譯執行
2.詳細記錄程式除錯及執行結果
五、實驗報告
1.完成本專案實驗後,學生應提交實驗報告。
2.實驗報告格式與要求見附件。
實驗學時:2
每組人數:1
實驗型別:3 (1:基礎性 2:綜合性 3:設計性 4:研究性)
實驗要求:1(1:必修 2:選修 3:其它)
實驗類別:2 (1:基礎 2:專業基礎 3:專業 4:其它)
一、實驗目的
1. 掌握回溯演算法思想
2. 掌握回溯遞迴原理
3. 了解回溯法典型問題
二、實驗內容
1. 編寫乙個簡單的程式,解決8皇后問題。
2. 批處理作業排程問題
[問題描述]給定n個作業的集合j=(j1, j2, … , jn)。每乙個作業ji都有兩項任務需要分別在2臺機器上完成。每乙個作業必須先由機器1處理,然後再由機器2處理。
作業ji需要機器i的處理時間為tji,i=1,2, … ,n; j=1,2。
對於乙個確定的作業排程,設fji是作業i在機器i上完成處理的時間。則所有作業在機器2上完成處理的時間和成為該作業排程的完成時間和。
批處理作業排程問題要求對於給定的n個作業,制定乙個最佳的作業排程方案,使其完成時間和達到最小。
要求輸入:
1)作業數 2)每個作業完成時間表:
要求輸出: 1)最佳完成時間 2)最佳排程方案
提示:演算法複雜度為o(n!),建議在測試的時候n值不要太大,可以考慮不要超過12。
3. 數字全排列問題
任意給出從1到n的n個連續的自然數,求出這n個自然數的各種全排列。如n=3時,共有以下6種排列方式:123,132,213,231,312,321。
注意:數字不能重複,n由鍵盤輸入(n<=9)。
三、實驗要求:
1.實驗前必須充分預習;
2. 實驗過程中仔細觀察實驗現象,認真記錄實驗結果;
3. 實驗後每個同學必須要求獨立完成實驗報告。
四、實驗步驟
1.寫出源程式,並編譯執行
2.詳細記錄程式除錯及執行結果
五、實驗報告
1.完成本專案實驗後,學生應提交實驗報告。
2.實驗報告格式與要求見附件。
實驗學時:2
每組人數:1
實驗型別:2 (1:基礎性 2:綜合性 3:設計性 4:研究性)
實驗要求:1(1:必修 2:選修 3:其它)
實驗類別:2 (1:基礎 2:專業基礎 3:專業 4:其它)
一、實驗目的
1. 理解和複習所學各種演算法的概念
2. 掌握和複習所學各種演算法的基本要素
3. 掌握各種演算法的優點和區別
4. 通過應用範例掌握選擇最佳演算法的設計技巧與策略
二、實驗內容
1. 使用貪心演算法、回溯法、分支限界法解決0-1揹包問題;
2. 通過上機實驗進行演算法實現;
3. 儲存和列印出程式的執行結果,並結合程式進行分析,上交實驗報告。
三、實驗要求:
1.實驗前必須充分預習;
2. 實驗過程中仔細觀察實驗現象,認真記錄實驗結果;
3. 實驗後每個同學必須要求獨立完成實驗報告。
四、實驗步驟
1.寫出源程式,並編譯執行
2.詳細記錄程式除錯及執行結果
五、實驗報告
1.完成本專案實驗後,學生應提交實驗報告。
2.實驗報告格式與要求見附件。
附件:1.實驗報告封面
2.實驗報告正文要求
實驗學時實驗地點實驗日期
一、實驗目的
指出此次實驗應該達到的學習目標。
二、實驗內容
指出此次實驗應完成的任務。
三、實驗方法
包括實驗方法、原理、技術、方案等。
四、實驗步驟
指出完成該實驗的操作步驟。
五、實驗結果
記錄實驗輸出資料和結果。
六、實驗結論
對實驗資料和結果進行分析描述,給出實驗取得的成果和結論。
注:有程式的要求附上程式源**,有圖表的要有截圖並有相應的文字說明和分析
七、實驗小結
給出本次實驗的體會,如學會了什麼,遇到哪些問題,如何解決這些問題,存在哪些有待改進的地方。
演算法設計與分析 1
湖南中醫藥大學 2009 2010 學年第一學期 演算法設計與分析 期末考試試卷 班級姓名學號 一 選擇題 10題 2分 20分 1.我們常用演算法的最壞時間來估計演算法的時間複雜性,下面 不是這樣做的原因 a 在實際問題中,演算法的執行時間常常達到這個上界。b 平均執行時間難以計算。c 假設每乙個...
演算法設計與分析課程設計報告簡單示例1
演算法設計與分析課程設計 題目 模擬實現穩定婚姻問題的gale shapley演算法 設計分析測試報告 姓名 鄭展圖 學號 3100608010 班級 軟體1001 指導教師 蔣麗萍 2013年 1 月 9 日 程式演算法設計說明書 一 前言 1.問題描述 穩定婚姻問題 有n男n女,每人都按他對 異...
演算法設計技巧與分析答案
參 第1章演算法分析基本概念 1.1 a 6 b 5 c 6 d 6 1.4演算法執行了7 6 5 4 3 2 1 28次比較 1.5 a 演算法modselectionsort執行的元素賦值的最少次數是0,元素已按非降序排列的時候達到最小值。b 演算法modselectionsort執行的元素賦值...