《算法設(shè)計與分析》實驗指導(dǎo)書

PAGEPAGE5《算法設(shè)計與分析》實驗指導(dǎo)書本文檔主要用于《算法設(shè)計與分析》課程的實驗指導(dǎo)。《算法設(shè)計與分析》旨在教會學(xué)生處理各種問題的方法，通過實驗，使學(xué)生能夠把所學(xué)的方法用于具體的問題，并對所用算法進(jìn)行比較分析，從而提高學(xué)生分析問題、解決問題的能力。通過該課程的實驗，使學(xué)生對課堂中所講述的內(nèi)容有一個直觀的認(rèn)識，更好地掌握所學(xué)的知識，培養(yǎng)學(xué)生的實際動手能力，加強(qiáng)學(xué)生創(chuàng)新思維能力的培養(yǎng)。本課程設(shè)計了7個設(shè)計型實驗。實驗內(nèi)容包括用分治法、動態(tài)規(guī)劃、貪心法、回溯法以及分支限界法求解問題。一、實驗內(nèi)容安排序號實驗項目內(nèi)容提要實驗學(xué)時實驗類型每組人數(shù)實驗要求1快速排序問題有n個無序的數(shù)值數(shù)據(jù)，現(xiàn)要求將其排列成一個有序的序列。要求用快速排序方法。2設(shè)計1必做2最少硬

幣問題有n種不同面值的硬幣，各硬幣面值存于數(shù)組T[1:n]；現(xiàn)用這些面值的錢來找錢；各面值的個數(shù)存在數(shù)組Num[1:n]中。對于給定的1≤n≤10，硬幣面值數(shù)組、各面值的個數(shù)及錢數(shù)m，0<=m<=2001，設(shè)計一個算法，計算找錢m的最少硬幣數(shù)。要求用動態(tài)規(guī)劃法。2設(shè)計1必做3租用游

艇問題長江游艇俱樂部在長江上設(shè)置了n個游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1≤i＜j≤n。設(shè)計一個算法，計算出從游艇出租站1到游艇出租站n所需的最少租金。要求用動態(tài)規(guī)劃法。4設(shè)計1必做4汽車加

油問題一輛汽車加滿油后可行駛n公里。旅途中有若干個加油站。設(shè)計一個有效算法，指出應(yīng)在哪些加油站停靠加油，使沿途加油次數(shù)最少。要求用貪心法。2設(shè)計1必做5最小重量機(jī)器設(shè)計問題設(shè)某一機(jī)器由n個部件組成，每一種部件可以從m個不同的供應(yīng)商處購得。設(shè)是從供應(yīng)商j處購得的部件i的重量，是相應(yīng)的價格。設(shè)計一個算法，給出總價格不超過的最小重量機(jī)器設(shè)計。要求用回溯法。3設(shè)計1必做6世界名畫

陳列問題針對世界名畫陳列館問題，設(shè)計一個算法，計算警衛(wèi)機(jī)器人的最佳哨位安排，使得名畫陳列館的每個陳列室都在警衛(wèi)機(jī)器人監(jiān)視之下，且所用的警衛(wèi)機(jī)器人數(shù)目最少。要求用回溯法。3設(shè)計1必做7最佳調(diào)

度問題假設(shè)有n個任務(wù)由k個可并行工作的機(jī)器來完成。完成任務(wù)i需要時間為，設(shè)計完成這n個任務(wù)的最佳調(diào)度算法，使得完成全部任務(wù)的時間最早。要求用分支限界法。2設(shè)計1必做二、實驗基本要求實驗前要求學(xué)生一定要先了解實驗?zāi)康?、?nèi)容、要求以及注意事項，要求學(xué)生熟悉實驗對象，設(shè)計并編寫相應(yīng)的算法。學(xué)生應(yīng)獨立完成所布置實驗內(nèi)容，編寫代碼，運行程序，記錄結(jié)果并撰寫實驗報告。三、實驗報告要求實驗結(jié)束后，應(yīng)及時整理出實驗報告，實驗報告提交書面文檔。四、考核方式理論考試（60％）＋實驗（30％）+作業(yè)（10%）五、實驗內(nèi)容與指導(dǎo)實驗一快速排序問題1．實驗?zāi)康?1)用分治法求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容有n個無序的數(shù)值數(shù)據(jù)，現(xiàn)要求將其排列成一個有序的序列。4.實驗步驟(1)輸入實現(xiàn)該問題的源代碼；(2)輸入測試數(shù)據(jù)，驗證代碼的正確性。5.實驗要求(1)做好實驗預(yù)習(xí)，熟悉本實驗中所使用的開發(fā)環(huán)境。(2)寫出實驗報告①實驗?zāi)康蘑趯嶒瀮?nèi)容③出錯信息及處理方法④實驗結(jié)果實驗二最少硬幣問題1．實驗?zāi)康?1)用動態(tài)規(guī)劃求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容有n種不同面值的硬幣，各硬幣面值存于數(shù)組T[1:n]；現(xiàn)用這些面值的錢來找錢；各面值的個數(shù)存在數(shù)組Num[1:n]中。對于給定的1≤n≤10，硬幣面值數(shù)組、各面值的個數(shù)及錢數(shù)m，0<=m<=2001，設(shè)計一個算法，計算找錢m的最少硬幣數(shù)。4.實驗步驟(1)輸入實現(xiàn)該問題的源代碼；(2)輸入測試數(shù)據(jù)，驗證代碼的正確性。5.實驗要求(1)做好實驗預(yù)習(xí)，熟悉本實驗中所使用的開發(fā)環(huán)境。(2)寫出實驗報告①實驗?zāi)康蘑趯嶒瀮?nèi)容③出錯信息及處理方法④實驗結(jié)果實驗三租用游艇問題1．實驗?zāi)康?1)用動態(tài)規(guī)劃求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容長江游艇俱樂部在長江上設(shè)置了n個游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1≤i＜j≤n。設(shè)計一個算法，計算出從游艇出租站1到游艇出租站n所需的最少租金。要求用動態(tài)規(guī)劃法。4.實驗步驟(1)輸入實現(xiàn)該問題的源代碼；(2)輸入測試數(shù)據(jù)，驗證代碼的正確性。5.實驗要求(1)做好實驗預(yù)習(xí)，熟悉本實驗中所使用的開發(fā)環(huán)境。(2)寫出實驗報告①實驗?zāi)康蘑趯嶒瀮?nèi)容③出錯信息及處理方法④實驗結(jié)果實驗四汽車加油問題1．實驗?zāi)康?1)用貪心法求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容一輛汽車加滿油后可行駛n公里。旅途中有若干個加油站。設(shè)計一個有效算法，指出應(yīng)在哪些加油站?？考佑停寡赝炯佑痛螖?shù)最少。4.實驗步驟(1)輸入實現(xiàn)該問題的源代碼；(2)輸入測試數(shù)據(jù)，驗證代碼的正確性。5.實驗要求(1)做好實驗預(yù)習(xí)，熟悉本實驗中所使用的開發(fā)環(huán)境。(2)寫出實驗報告①實驗?zāi)康蘑趯嶒瀮?nèi)容③出錯信息及處理方法④實驗結(jié)果實驗五最小重量機(jī)器設(shè)計問題1．實驗?zāi)康?1)用回溯法求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容設(shè)某一機(jī)器由n個部件組成，每一種部件可以從m個不同的供應(yīng)商處購得。設(shè)是從供應(yīng)商j處購得的部件i的重量，是相應(yīng)的價格。設(shè)計一個算法，給出總價格不超過的最小重量機(jī)器設(shè)計。4.實驗步驟(1)輸入實現(xiàn)該問題的源代碼；(2)輸入測試數(shù)據(jù)，驗證代碼的正確性。5.實驗要求(1)做好實驗預(yù)習(xí)，熟悉本實驗中所使用的開發(fā)環(huán)境。(2)寫出實驗報告①實驗?zāi)康蘑趯嶒瀮?nèi)容③出錯信息及處理方法④實驗結(jié)果實驗六世界名畫陳列問題1．實驗?zāi)康?1)用回溯法求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容針對世界名畫陳列館問題，設(shè)計一個算法，計算警衛(wèi)機(jī)器人的最佳哨位安排，使得名畫陳列館的每個陳列室都在警衛(wèi)機(jī)器人監(jiān)視之下，且所用的警衛(wèi)機(jī)器人數(shù)目最少。4.實驗步驟(1)輸入實現(xiàn)該問題的源代碼；(2)輸入測試數(shù)據(jù)，驗證代碼的正確性。5.實驗要求(1)做好實驗預(yù)習(xí)，熟悉本實驗中所使用的開發(fā)環(huán)境。(2)寫出實驗報告①實驗?zāi)康蘑趯嶒瀮?nèi)容③出錯信息及處理方法④實驗結(jié)果實驗七最佳調(diào)度問題1．實驗?zāi)康?1)用分支限界法求解該問題。2．實驗環(huán)境PC機(jī)，要求安裝Eclipse軟件或VC++軟件供學(xué)生實驗。3．實驗內(nèi)容假設(shè)有n個任務(wù)由k個可并行工作的機(jī)器來完成。