算法設計與分析實驗

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

2、第k小的元素l 主要思路及步驟1. 把a數(shù)組中元素分為5個一組,選每組中位數(shù)后分別將他們移向數(shù)組頭,再用同樣的方法選取中位數(shù)的中位數(shù)x,然后按x把a數(shù)組分為兩個劃分,重復上述過程直至劃分中元素個數(shù)少于75,返回要求值l 算法描述Type Select(Type a, int p, int r, int k) if (r-p<75) 用某個簡單排序算法對數(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-p-4即上面所說

3、的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ù)組a的元素的值，要求元素個數(shù)不少于80個，并實現(xiàn)以下輸出：（1）輸出數(shù)組a中下標范圍從p到p+(r-p-4)/5的元素；（2）輸出x的值，判斷x是否為數(shù)組a中下標范圍從p到p+(r-p-4)/5的擬中位數(shù)；（3）輸出數(shù)組a中下標范圍從p到r的元素，驗證其是否為

4、以x為基準元素的劃分。源代碼：:#include <stdlib.h>#include <time.h>#include <stdio.h>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+i<x && i<r);while(a-j>x);if(i>=j)break;Swap(&ai,&aj);ap=

5、aj;aj=x;return j;void QuickSort(int *a, int p, int r)if(p<r)int q=Partition(a,p,r);QuickSort(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)whi

6、le(a+i<x && i<r);while(a-j>x);if(i>=j)break;Swap(&ai,&aj);ap=aj;aj=x;return j;/劃分函數(shù)int Select(int *a, int p, int r, int k)if(r-p<75)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;

7、printf("數(shù)組a下標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 count=0;i=Partition_S(a,p,r,x,&count);printf("以%d為基準的劃分:",x);for(t=p;t<=r;t+)printf("%d &qu

8、ot;,at);/輸出(3)printf("nn");j=i-p;if(k<=j) return Select(a,p,i-1,k);else if(count>=1 && j<k && 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, 17

9、50, 406, 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

10、, 636, 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);/排序,方便查看結果for(j=0;j<80;j+)printf(" %d",aj);printf("n");printf("第%d小的數(shù)是%dn",z, i);return 0;實驗截圖：l 實驗總結基本熟悉線性時間選擇算法的結構第三章實驗題

11、選做算法實現(xiàn)題2: 二維0-1背包問題（P79 3-4）l 問題描述l 分析與解答要求：給出最優(yōu)值的遞歸關系l 算法描述l 輸入和輸出要求：物品不少于10個，輸出最優(yōu)值數(shù)組的全部值和最后的最優(yōu)解算法實現(xiàn)：#include <stdio.h>int m100100100;int min(int i,int j)return i<j?i:j;int max(int i,int j)return i>j?i:j;void Knapsack(int *v,int *w,int c,int *b,int d,int n)int min(int i,int j);int max(i

12、nt 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且重量不足 for(j=jMax;j<=c;j+) for(k=0;k<=kMax;k+) mnjk=0;/可選物品只有n且體積不足 for(j=wn;j<=c;j+) for(k=bn;k<=d;k+) mnjk=vn;/可選物品只有n且能裝下 for(i=n-1;i>1;i-) jMax

13、=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<=d;k+) mijk=max(mi+1jk,mi+1j-wik-bi+vi); m1cd=m2cd; if(c>=w1&&d>=b1) m1cd=max(m1cd,m2c-w1d-b1+v1);void Trac

14、eback(int *w,int c,int *b,int d,int n,int *x) for(int i=1;i<n;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("請輸入物品個數(shù)、背包容量、背包容積:"); scanf("%d %d %d",&n,&c,&d); int v100,w100,b100,x100; printf("請輸入每個物品的價值、重量、體積：n"); for(i=1;i<=n;i+) scanf("%d %d %