【正文】 算法設(shè)計與分析實驗報告 指導(dǎo)老師：沙莎學(xué) 院：信息科學(xué)與工程學(xué)院班 級：計科0508姓 名：戚婕學(xué) 號：10完成日期：2007年12月目 錄實驗一 分治法 ………………………………………………………………………… 2 實驗要求 ……………………………………………………………………… 2 實驗內(nèi)容 ……………………………………………………………………… 2 核心算法 ……………………………………………………………………… 2 程序代碼 ……………………………………………………………………… 4 實驗結(jié)果 ……………………………………………………………………… 8實驗二 貪心法 ……………………………………………………………………… 10 實驗要求 …………………………………………………………………… 10 實驗內(nèi)容 …………………………………………………………………… 10 核心算法 …………………………………………………………………… 10 程序代碼 …………………………………………………………………… 12 實驗結(jié)果 …………………………………………………………………… 18實驗三 動態(tài)規(guī)劃 ………………………………………………………………… 20 實驗要求 …………………………………………………………………… 20 實驗內(nèi)容 …………………………………………………………………… 20 核心算法 …………………………………………………………………… 20 程序代碼 …………………………………………………………………… 21 實驗結(jié)果 …………………………………………………………………… 24實驗四 深度優(yōu)先搜索 …………………………………………………………… 26 實驗要求 …………………………………………………………………… 26 實驗內(nèi)容 …………………………………………………………………… 26 核心算法 …………………………………………………………………… 26 程序代碼 …………………………………………………………………… 27 實驗結(jié)果 …………………………………………………………………… 28實驗五 回溯法 ……………………………………………………………………… 30 實驗要求 …………………………………………………………………… 30 實驗內(nèi)容 …………………………………………………………………… 30 核心算法 …………………………………………………………………… 30 程序代碼 …………………………………………………………………… 31 實驗結(jié)果 …………………………………………………………………… 33實驗一 分治法1. 了解用分治法求解的問題：當(dāng)要求解一個輸入規(guī)模為n，且n的取值相當(dāng)大的問題時，如果問題可以分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1k≤n，而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。那末，對于這類問題分治法是十分有效的。2. 掌握分治法的一般控制流程。DanC(p,q) global n，A[1:n]。 integer m,p,q。 // 1163。p163。q163。n if Small(p,q) then return G(p,q)。 else m=Divide(p,q)。 // p163。mq return Combine(DanC(p,m),DanC(m+1,q))。 endifend DanC3．實現(xiàn)典型的分治算法的編程與上機(jī)實驗，驗證算法的時間復(fù)雜性函數(shù)。1. 編程實現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計數(shù)功能，輸出排序結(jié)果和比較次數(shù)。2. 輸入10組相同的數(shù)據(jù)，驗證排序結(jié)果和完成排序的比較次數(shù)。3. 與復(fù)雜性函數(shù)所計算的比較次數(shù)比較。4. 用表格列出比較結(jié)果。5. 給出文字分析。1. 歸并排序算法procedure MERGESORT(low，high) //A(low；high)是一個全程數(shù)組，它含有highlow+1≥0個待排序的元素// integer low，high； if lowhigh； then mid← ， //求這個集合的分割點// call MERGESORT(low，mid) //將一個子集合排序// call MERGESORT(mid+1，high) //將另一個子集合排序 call MERGE(low，mid，high) //歸并兩個已排序的子集合// endif end MERGESORT歸并兩個已排序的集合 procedure MERGE(low，mid，high) //A(low：high)是一個全程數(shù)組// //輔助數(shù)組B(low；high)// integer h，i，j，k； h←low；i←low；j←mid+1； while h≤mid and j≤high do //當(dāng)兩個集合都沒取盡時// if A(h)≤A(j) then B(i) ←A(h)；h←h+1 else B(i) ←A(j)；j←j+1 endif i←i+1 repeat if hmid then for k←j to high do //處理剩余的元素// B(i) ←A(k)；i←i+1 repeat else for k←h to mid do B(i) ←A(k)；i←i+1 repeat endif 將已歸并的集合復(fù)制到A end MERGE2. 快速排序算法QuickSort(p,q) //將數(shù)組A[1:n]中的元素 A[p], A[p+1], 188。 , A[q]按不降次序排列， 并假定A[n+1]是一個確定的、且大于 A[1:n]中所有的數(shù)。// int p,q。 global n, A[1:n]。 if pq then j=Partition(p, q+1)。 // 劃分后j成為劃分元素的位置 QuickSort(p,j1)。 QuickSort(j+1,q)。 endif end QuickSortprocedure PARTITION(m，p) //退出過程時，p帶著劃分元素所在的下標(biāo)位置。// integer m，p，i；global A(m：p1) v←A(m)；i←m //A(m)是劃分元素// loop loop i←i+1 until A(i)≥v repeat //i由左向右移// loop p←p1 until A(p)≤v repeat //p由右向左移// if ip then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)換位// else exit endif repeat A(m) ←A(p)；A(p) ←v //劃分元素在位置p// End PARTITION1. 歸并排序includeincludeincludeincludedefine M 11typedef int KeyType。typedef int ElemType。struct rec{ KeyType key。 ElemType data。 }。typedef rec sqlist[M]。class guibing{public: guibing(sqlist b) { for(int i=0。iM。i++) r[i]=b[i]。 } void output(sqlist r,int n) { for(int i=0。in。i++) coutsetw(4)r[i].key。 coutendl。 } void xuanze(sqlist b,int m,int n) { int i,j,k。 for(i=m。in1。i++) { k=i。 for(j=i。jn。j++)