實(shí)驗(yàn)五動態(tài)規(guī)劃問題算法設(shè)計.doc

《實(shí)驗(yàn)五動態(tài)規(guī)劃問題算法設(shè)計.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、寧夏師范學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院《算法分析與設(shè)計》實(shí)驗(yàn)報告實(shí)驗(yàn)序號：5　　實(shí)驗(yàn)項(xiàng)目名稱：動態(tài)規(guī)劃問題算法設(shè)計學(xué)　　號姓　　名專業(yè)、班實(shí)驗(yàn)地點(diǎn)指導(dǎo)教師惠云時間一、實(shí)驗(yàn)?zāi)康募耙螅?）掌握使用動態(tài)規(guī)劃方法設(shè)計最優(yōu)值問題的方法；（2）能夠使用動態(tài)規(guī)劃算法設(shè)計策略設(shè)計矩陣連乘和最長公共子序列問題的算法；（3）掌握0-1背包問題的算法設(shè)計方法。二、實(shí)驗(yàn)設(shè)備（環(huán)境）及要求1、環(huán)境要求：硬件：PC（PII以上，128M以上內(nèi)存）、因特網(wǎng)接入；軟件：WindowsXP操作系統(tǒng)、VC++6.0編程環(huán)境。2、實(shí)驗(yàn)要求：(1)獨(dú)立完成實(shí)驗(yàn)，源代碼書寫規(guī)范；(2)程序運(yùn)行結(jié)果以屏幕截圖的方式粘貼在對應(yīng)

2、位置，截圖必須清晰準(zhǔn)確；(3)實(shí)驗(yàn)完成后必須有實(shí)驗(yàn)結(jié)果的分析及本次實(shí)驗(yàn)的總結(jié)。三、實(shí)驗(yàn)內(nèi)容與步驟1、設(shè)計求解n個矩陣連乘的最優(yōu)計算次序問題的程序，并將在最優(yōu)計算次序下所需的乘法次數(shù)及最優(yōu)計算次序在屏幕上顯示。n個矩陣的維數(shù)從鍵盤輸入。2、設(shè)計求解x和y兩個序列的最長公共子序列問題的程序，并將最長公共子序列的長度及最長公共子序列在屏幕上顯示。x和y序列從鍵盤輸入。3、設(shè)計求解0-1背包問題的程序，并將裝入背包的物品的最大價值及最優(yōu)裝入序列在屏幕上顯示。背包的最大容量，物品的重量、價值從鍵盤輸入。四、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理五、分析與討論1、比較備忘錄方法和動態(tài)規(guī)劃方法求矩陣連乘問題的特

3、點(diǎn)。2.分析求最長公共子序列長度和構(gòu)造最長公共子序列兩種算法的時間復(fù)雜度。六、教師評語簽名：日期：年月日成績