本文件主要用於《演算法設計與分析》課程的實驗指導。《演算法設計與分析》旨在教會學生處理各種問題的方法,通過實驗,使學生能夠把所學的方法用於具體的問題,並對所用演算法進行比較分析,從而提高學生分析問題、解決問題的能力。
通過該課程的實驗,使學生對課堂中所講述的內容有乙個直觀的認識,更好地掌握所學的知識,培養學生的實際動手能力,加強學生創新思維能力的培養。
本課程設計了7個設計型實驗。實驗內容包括用分治法、動態規劃、貪心法、回溯法以及分支限界法求解問題。
一、實驗內容安排
二、實驗基本要求
實驗前要求學生一定要先了解實驗目的、內容、要求以及注意事項,要求學生熟悉實驗物件,設計並編寫相應的演算法。學生應獨立完成所布置實驗內容,編寫**,執行程式,記錄結果並撰寫實驗報告。
三、實驗報告要求
實驗結束後,應及時整理出實驗報告,實驗報告提交書面文件。
四、考核方式
理論考試(60%)+實驗(30%)+作業(10%)
五、實驗內容與指導
實驗一快速排序問題
1.實驗目的
(1) 用分治法求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
有n個無序的數值資料,現要求將其排列成乙個有序的序列。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
實驗二最少硬幣問題
1.實驗目的
(1) 用動態規劃求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
有n種不同面值的硬幣,各硬幣面值存於陣列t[1:n];現用這些面值的錢來找錢;各面值的個數存在陣列num[1:n]中。
對於給定的1≤n≤10,硬幣面值陣列、各面值的個數及錢數m,0<=m<=2001,設計乙個演算法,計算找錢m的最少硬幣數。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
實驗三租用遊艇問題
1.實驗目的
(1) 用動態規劃求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
長江遊艇俱樂部在長江上設定了n 個遊艇出租站1,2,…,n。遊客可在這些遊艇出租站租用遊艇,並在下游的任何乙個遊艇出租站歸還遊艇。遊艇出租站i 到遊艇出租站j 之間的租金為r(i,j),1≤i<j≤n。
設計乙個演算法,計算出從遊艇出租站1 到遊艇出租站n 所需的最少租金。要求用動態規劃法。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
實驗四汽車加油問題
1.實驗目的
(1) 用貪心法求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
一輛汽車加滿油後可行駛n公里。旅途中有若干個加油站。設計乙個有效演算法,指出應在哪些加油站停靠加油,使沿途加油次數最少。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
實驗五最小重量機器設計問題
1.實驗目的
(1) 用回溯法求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
設某一機器由n個部件組成,每一種部件可以從m個不同的**商處購得。設是從**商j處購得的部件i的重量,是相應的**。設計乙個演算法,給出總**不超過的最小重量機器設計。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
實驗六世界名畫陳列問題
1.實驗目的
(1) 用回溯法求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
針對世界名畫陳列館問題,設計乙個演算法,計算警衛機械人的最佳哨位安排,使得名畫陳列館的每個陳列室都在警衛機械人監視之下,且所用的警衛機械人數目最少。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
實驗七最佳排程問題
1.實驗目的
(1) 用分支限界法求解該問題。
2.實驗環境
pc機,要求安裝eclipse軟體或vc++軟體供學生實驗。
3.實驗內容
假設有n個任務由k個可並行工作的機器來完成。完成任務i需要時間為,設計完成這n個任務的最佳排程演算法,使得完成全部任務的時間最早。
4. 實驗步驟
(1) 輸入實現該問題的源**;
(2) 輸入測試資料,驗證**的正確性。
5.實驗要求
(1)做好實驗預習,熟悉本實驗中所使用的開發環境。
(2)寫出實驗報告
① 實驗目的
② 實驗內容
③ 出錯資訊及處理方法
④ 實驗結果
320132X1 《演算法分析與設計》實驗指導書
演算法設計與分析 課程實驗指導書 劉莉平編寫 課程編號 320132x1 總學時 48 實驗學時 10 課外學時 20 中南大學軟體學院 2012年11月 實驗學時 2 每組人數 1 實驗型別 2 1 基礎性 2 綜合性 3 設計性 4 研究性 實驗要求 1 1 必修 2 選修 3 其它 實驗類別 ...
shiweijie《演算法分析與設計》實驗指導與報告書
常熟理工學院 演算法分析與設計 實驗指導與報告書 學年第 學期 專業 軟體工程 服務外包 學號 y12309218 姓名 施偉傑 實驗地點 n6 113 指導教師劉在德 電腦科學與工程學院 2011.02 實驗目錄 實驗1 求最大公約數 2 實驗2 斐波那契數列 3 實驗3 最近對問題 4 實驗4 ...
《資料結構與演算法》實驗指導書
鬱松軟體學院 資料結構 是計算機 資訊管理和電子商務專業一門重要的專業技術基礎課程,是計算機 資訊管理和電子商務專業的一門關鍵性課程。本課程較系統地介紹了軟體設計中常用的資料結構以及相應的儲存結構和實現演算法,介紹了常用的多種查詢和排序技術,並做了一些效能分析和比較,內容非常豐富。本課程的學習將為後...