算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

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

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

2、………………………………………102.1實(shí)驗(yàn)要求……………………………………………………………………102.2實(shí)驗(yàn)內(nèi)容……………………………………………………………………102.3核心算法……………………………………………………………………102.4程序代碼……………………………………………………………………122.5實(shí)驗(yàn)結(jié)果……………………………………………………………………18實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃…………………………………………………………………203.1實(shí)驗(yàn)要求……………………………………………………………………203.2實(shí)驗(yàn)內(nèi)容……………………………………………………………………

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

4、……………………………………………………28實(shí)驗(yàn)五回溯法………………………………………………………………………305.1實(shí)驗(yàn)要求……………………………………………………………………305.2實(shí)驗(yàn)內(nèi)容……………………………………………………………………305.3核心算法……………………………………………………………………305.4程序代碼……………………………………………………………………315.5實(shí)驗(yàn)結(jié)果……………………………………………………………………3333實(shí)驗(yàn)一分治法一.實(shí)驗(yàn)要求1.了解用分治法求解的問(wèn)題：當(dāng)要求解一個(gè)輸入規(guī)模為n，且n的取值相當(dāng)大的問(wèn)題時(shí)，如果問(wèn)題可以分成

5、k個(gè)不同子集合，得到k個(gè)不同的可獨(dú)立求解的子問(wèn)題，其中1

6、歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計(jì)數(shù)功能，輸出排序結(jié)果和比較次數(shù)。2.輸入10組相同的數(shù)據(jù)，驗(yàn)證排序結(jié)果和完成排序的比較次數(shù)。3.與復(fù)雜性函數(shù)所計(jì)算的比較次數(shù)比較。4.用表格列出比較結(jié)果。5.給出文字分析。三.程序算法1.歸并排序算法procedureMERGESORT(low，high)//A(low；high)是一個(gè)全程數(shù)組，它含有high-low+1≥0個(gè)待排序的元素//integerlow，high；iflow

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