算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-wenkub
2022-09-02 10:32:01 本頁面
【正文】 排序結(jié)果和完成排序的比較次數(shù)。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è)集合都沒取盡時(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。 if pq then j=Partition(p, q+1)。// 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。 }。i++) r[i]=b[i]。 coutendl。i++) { k=i。 if(k!=i) { rec temp=b[k]。 xuanze(r,m,h)。 for(j=m。k++) { if(r[i].key=r[j].key) { r2[k]=r[i]。 } output(r2,M)。 } while(i=m) { r2[k]=r[i]。 }private: sqlist r。 int i,j=0,k=M/2,n=M。i++) { a[i].key=rand()%80。 (a,M)。 (b,M)。struct rec{ KeyType key。class kuaisu{public: kuaisu(sqlist a,int m):n(m) { for(int i=0。 if(st){ i=part(s,t)。 } int part(int s,int t) { int i,j。p=b[s]。 b[i]=b[j]。 b[j]=b[i]。 } void output() { for(int i=0。 }private: sqlist b。 sqlist a1。in。 (low,high)。}1. 歸并排序2. 快速排序?qū)嶒?yàn)二 貪心法1. 優(yōu)化問題 有n個(gè)輸入，而它的解就由這n個(gè)輸入滿足某些事先給定的約束條件的某個(gè)子集組成，而把滿足約束條件的子集稱為該問題的可行解。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。2）按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序3）依次選擇輸入量加入部分解中。通過具體算法理解如何通過局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)，并驗(yàn)證算法的時(shí)間復(fù)雜性。M是背包的容量大小，而x(1：n)是解向量 real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n；X←0 //將解向量初始化為零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)cu then exit endif X(i) ←1 cu←cuW(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDYKNAPSACKprocedure prim(G,)status←“unseen” // T為空 status[1]←“tree node” // 將1放入Tfor each edge(1,w) do status[w]←“fringe” // 找到T的鄰接點(diǎn) dad[w] ←1。 for(k=0；kn1；k++){ //求T的n1條樹邊 //物品重量 float X。 for(j=2。 while (goods[0].pgoods[i].p) { goods[i+1]=goods[i]。 int i,j。 cu=M。 goods[i].X=1。j=n。 i。i=n。 cout||endl。 goodinfo *goods。// cout請(qǐng)輸入背包的最大容量：。 for(i=1。 cingoods[i].w。//得出物品的效益，重量比 coutendl。 coutpress 0 to exitendl。typedef char VerTexType。typedef struct{ VerTexType vexs[MAX_VERTEX_NUM]。typedef struct{ VerTexType adjvex。G)。void main( void ){ int i, j。 i 。 cout 。)。 char hand, tide。 i 。 } coutendl。 i++) cin[i]。 k = 0。 cinhand。 while (tide != [k]) k++。 k = 0。 k = LocateVex ( G, u )。 close[j].lowcost = [k][j].adj。 close[k].lowcost = 0。 i++) { k = minimum(close)。 coutclose[k].lowcostendl。 j++) { if ([k][j].adj close[j].lowcost) { close[j].adjvex = [k]。 return 0。) { if (client close[j1].lowcost amp。 } j1++。這類問題的解決是多階段的決策過程。子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。即當(dāng)前最優(yōu)只與上一步有關(guān)。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。4. 驗(yàn)證算法的時(shí)間復(fù)雜性。// real COST(n)，integerD(n一1)，P(k)，r，j，k，n COST(n)← 0 for j←n1to 1
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1