1、暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙(附頁)暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙課程名稱 算法設(shè)計(jì)與分析 成績?cè)u(píng)定 實(shí)驗(yàn)項(xiàng)目名稱 分治策略與動(dòng)態(tài)規(guī)劃 指導(dǎo)教師 李展 實(shí)驗(yàn)項(xiàng)目編號(hào) 01 實(shí)驗(yàn)項(xiàng)目類型 設(shè)計(jì)類 實(shí)驗(yàn)地點(diǎn) 南海樓6樓學(xué)生姓名 陳奕豪 學(xué)號(hào) 2012051351 學(xué)院 信息科學(xué)技術(shù)學(xué)院 系 計(jì)算機(jī)系 專業(yè) 軟件工程 實(shí)驗(yàn)時(shí)間 年 月 日 一、 實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)涉及用分治策略和動(dòng)態(tài)規(guī)劃算法來求解優(yōu)化組合問題。通過上機(jī)實(shí)驗(yàn)使學(xué)員學(xué)會(huì)程序的錄入和調(diào)試；通過實(shí)驗(yàn)結(jié)果的比較，使學(xué)員了解兩種算法的主要特點(diǎn)。二、 實(shí)驗(yàn)內(nèi)容：第二章實(shí)驗(yàn)題必做算法分析題1: 線性時(shí)間選擇問題l 問題描述給定線性序集中n個(gè)元素和一個(gè)整數(shù)k

2、, 1kn, 要求找出這n個(gè)元素中第k小的元素l 主要思路及步驟1. 把a(bǔ)數(shù)組中元素分為5個(gè)一組,選每組中位數(shù)后分別將他們移向數(shù)組頭,再用同樣的方法選取中位數(shù)的中位數(shù)x,然后按x把a(bǔ)數(shù)組分為兩個(gè)劃分,重復(fù)上述過程直至劃分中元素個(gè)數(shù)少于75,返回要求值l 算法描述Type Select(Type a, int p, int r, int k) if (r-p75) 用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組ap:r排序; return ap+k-1; ; for ( int i = 0; i=(r-p-4)/5; i+ ) 將ap+5*i至ap+5*i+4的第3小元素 與ap+i交換位置; /找中位數(shù)的中位數(shù)，r

3、-p-4即上面所說的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p+6)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j);l 輸入和輸出自行設(shè)計(jì)數(shù)組a的元素的值，要求元素個(gè)數(shù)不少于80個(gè)，并實(shí)現(xiàn)以下輸出：（1）輸出數(shù)組a中下標(biāo)范圍從p到p+(r-p-4)/5的元素；（2）輸出x的值，判斷x是否為數(shù)組a中下標(biāo)范圍從p到p+(r-p-4)/5的擬中位數(shù)；（3）輸出數(shù)組a中下標(biāo)范圍從p到r的元素，驗(yàn)

4、證其是否為以x為基準(zhǔn)元素的劃分。源代碼：:#include #include #include void Swap(int *i,int *j)int a;a=*i;*i=*j;*j=a;/交換函數(shù)int Partition(int *a, int p, int r)int i=p,j=r+1;int x=ap;while(true)while(a+ix & ix);if(i=j)break;Swap(&ai,&aj);ap=aj;aj=x;return j;void QuickSort(int *a, int p, int r)if(pr)int q=Partition(a,p,r);Qui

5、ckSort(a,p,q-1);QuickSort(a,q+1,r);/快速排列int Partition_S(int *a, int p, int r, int x,int *count)int i,j=p,temp,z=0;for(i=0;i=r;i+)if(ai!=x)z+;elsetemp=az;az=aj;aj=temp;j+;z+;(*count)+;i=p,j=r+1;while(true)while(a+ix & ix);if(i=j)break;Swap(&ai,&aj);ap=aj;aj=x;return j;/劃分函數(shù)int Select(int *a, int p, i

6、nt r, int k)if(r-p75)QuickSort(a,p,r);return ap+k-1;int i,j,t;for(i=0;i=(r-p-4)/5;i+)QuickSort(a,p+5*i,p+5*i+4);int temp=ap+i;ap+i=ap+i*5+2;ap+i*5+2=temp;printf(數(shù)組a下標(biāo)p到p+(r-p-4)/5的元素);for(i=p;i=p+(r-p-4)/5;i+)printf(%d ,ai);/輸出(1)int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);printf(n擬中位數(shù):%dn,x);/輸出(2)int

7、 count=0;i=Partition_S(a,p,r,x,&count);printf(以%d為基準(zhǔn)的劃分:,x);for(t=p;t=r;t+)printf(%d ,at);/輸出(3)printf(nn);j=i-p;if(k=1 & jk & k=j+count-1)return ai;elsereturn Select(a,i+count,r,k-j-count);int main()int i,n,j;int a80=1059,1285,50,32, 788, 651, 106, 42, 67, 7, 1287, 395, 412, 132, 213, 398, 1750, 40

8、6, 1834, 703, 210, 1102, 1210, 1092, 161, 1736, 578, 965, 1037, 881, 1754, 813, 268, 558, 1961, 1271, 776, 146, 544, 1921, 514, 1049, 636, 1275, 1415, 1294, 929, 765, 472, 187, 1575, 194, 1342, 1309, 1026, 1836, 502, 1412, 289, 161, 137, 1943, 367, 1163, 1047, 896, 132, 1375, 428, 655, 94, 111, 636,

9、 103, 1018, 1099, 479, 465, 346, 1720;printf(輸入k的值:);scanf(%d,&n);int z=n;i=Select(a,0,79,n);QuickSort(a,0,79);/排序,方便查看結(jié)果for(j=0;j80;j+)printf( %d,aj);printf(n);printf(第%d小的數(shù)是%dn,z, i);return 0;實(shí)驗(yàn)截圖：l 實(shí)驗(yàn)總結(jié)基本熟悉線性時(shí)間選擇算法的結(jié)構(gòu)第三章實(shí)驗(yàn)題選做算法實(shí)現(xiàn)題2: 二維0-1背包問題（P79 3-4）l 問題描述l 分析與解答要求：給出最優(yōu)值的遞歸關(guān)系l 算法描述l 輸入和輸出要求：物品不少

10、于10個(gè)，輸出最優(yōu)值數(shù)組的全部值和最后的最優(yōu)解算法實(shí)現(xiàn)：#include int m100100100;int min(int i,int j)return ij?i:j;void Knapsack(int *v,int *w,int c,int *b,int d,int n)int min(int i,int j);int max(int i,int j); int i,j,k; int jMax=min(wn-1,c);/可選物品只有nint kMax=min(bn-1,d);/同上 for(j=0;j=jMax;j+) for(k=kMax;k=d;k+) mnjk=0;/可選物品只有n

11、且重量不足 for(j=jMax;j=c;j+) for(k=0;k=kMax;k+) mnjk=0;/可選物品只有n且體積不足 for(j=wn;j=c;j+) for(k=bn;k1;i-) jMax=min(wi-1,c); kMax=min(bi-1,d); for(j=0;j=jMax;j+) for(k=0;k=d;k+) mijk=mi+1jk; for(j=0;j=c;j+) for(k=0;k=kMax;k+) mijk=mi+1jk; for(j=wi;j=c;j+) for(k=bi;k=w1&d=b1) m1cd=max(m1cd,m2c-w1d-b1+v1);void Traceback(int *w,int c,int *b,int d,int n,int *x) for(int i=1;in;i+) if(micd=mi+1cd) xi=0; else xi=1; c-=wi; d-=bi; xn=(mncd) ? 1:0;int main() int n,c,d,i; printf(請(qǐng)輸入物品個(gè)數(shù)、背包容量、背包容積:); scanf(%d %d %d,&n,&c,&d); int v100,w100,b100,x100; printf(請(qǐng)輸入每個(gè)物品的價(jià)值、重量、體積：n); for(i=1