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