算法設(shè)計與分析實驗報告

《算法設(shè)計與分析實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、算法設(shè)計與分析實驗報告指導(dǎo)老師：沙莎學(xué)院：信息科學(xué)與工程學(xué)院班級：計科0508姓名：戚婕學(xué)號：10完成日期：2007年12月33目錄實驗一分治法…………………………………………………………………………21.1實驗要求………………………………………………………………………21.2實驗內(nèi)容………………………………………………………………………21.3核心算法………………………………………………………………………21.4程序代碼………………………………………………………………………41.5實驗結(jié)果…………………………

2、……………………………………………8實驗二貪心法………………………………………………………………………102.1實驗要求……………………………………………………………………102.2實驗內(nèi)容……………………………………………………………………102.3核心算法……………………………………………………………………102.4程序代碼……………………………………………………………………122.5實驗結(jié)果……………………………………………………………………18實驗三動態(tài)規(guī)劃……………………………………………………………

3、……203.1實驗要求……………………………………………………………………203.2實驗內(nèi)容……………………………………………………………………203.3核心算法……………………………………………………………………203.4程序代碼……………………………………………………………………213.5實驗結(jié)果……………………………………………………………………24實驗四深度優(yōu)先搜索……………………………………………………………264.1實驗要求……………………………………………………………………264.2實驗內(nèi)容………

4、……………………………………………………………264.3核心算法……………………………………………………………………264.4程序代碼……………………………………………………………………274.5實驗結(jié)果……………………………………………………………………28實驗五回溯法………………………………………………………………………305.1實驗要求……………………………………………………………………305.2實驗內(nèi)容……………………………………………………………………305.3核心算法…………………………………………

5、…………………………305.4程序代碼……………………………………………………………………315.5實驗結(jié)果……………………………………………………………………3333實驗一分治法一.實驗要求1.了解用分治法求解的問題：當(dāng)要求解一個輸入規(guī)模為n，且n的取值相當(dāng)大的問題時，如果問題可以分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1

6、ln，A[1:n];integerm,p,q;//1￡p￡q￡nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p￡m

7、數(shù)所計算的比較次數(shù)比較。4.用表格列出比較結(jié)果。5.給出文字分析。三.程序算法1.歸并排序算法procedureMERGESORT(low，high)//A(low；high)是一個全程數(shù)組，它含有high-low+1≥0個待排序的元素//integerlow，high；iflow

8、igh)//歸并兩個已排序的子集合//endif33endMERGESORT歸并兩個已排序的集合procedureMERGE(low，mid，high)//A(low：high)是一個全程數(shù)組////輔助數(shù)組B(low；high)//integerh，i，j，k；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//當(dāng)兩個集合都沒取盡時//ifA(h)≤