《演算法設計與分析》
課程實驗指導書
劉莉平編寫
課程編號 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執行的元素賦值...