算法設計與分析實驗(第2、3章).doc

《算法設計與分析實驗(第2、3章).doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

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

2、n個元素和一個整數(shù)k,1≤k≤n,要求找出這n個元素中第k小的元素l主要思路及步驟1.把a數(shù)組中元素分為5個一組,選每組中位數(shù)后分別將他們移向數(shù)組頭,再用同樣的方法選取中位數(shù)的中位數(shù)x,然后按x把a數(shù)組分為兩個劃分,重復上述過程直至劃分中元素個數(shù)少于75,返回要求值l算法描述暨南大學本科實驗報告專用紙(附頁)TypeSelect(Typea[],intp,intr,intk) { if(r-p<75){ 用某個簡單排序算法對數(shù)組a[p:r]排序; returna[p+k-1]; }; for(int

3、i=0;i<=(r-p-4)/5;i++) 將a[p+5*i]至a[p+5*i+4]的第3小元素 與a[p+i]交換位置; //找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5 Typex=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);inti=Partition(a,p,r,x), j=i-p+1; if(k<=j)returnSelect(a,p,i,k); elsereturnSelect(a,i+1,r,k-j); }l輸入和輸出自行設計數(shù)組a的元素的值，要求元素個數(shù)不

4、少于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的元素，驗證其是否為以x為基準元素的劃分。源代碼：:#include#include#includevoidSwap(int*i,int*j){inta;a=*i;暨南大學本科實驗報告專用紙(附頁)*i=*j;*j=a;}//交換函數(shù)int

5、Partition(int*a,intp,intr){inti=p,j=r+1;intx=a[p];while(true){while(a[++i]x);if(i>=j)break;Swap(&a[i],&a[j]);}a[p]=a[j];a[j]=x;returnj;}voidQuickSort(int*a,intp,intr){if(p

6、1,r);}//快速排列intPartition_S(int*a,intp,intr,intx,int*count){inti,j=p,temp,z=0;for(i=0;i<=r;i++){if(a[i]!=x)z++;else{temp=a[z];a[z]=a[j];a[j]=temp;j++;z++;(*count)++;}}暨南大學本科實驗報告專用紙(附頁)i=p,j=r+1;while(true){while(a[++i]x);if(i>=j)br

7、eak;Swap(&a[i],&a[j]);}a[p]=a[j];a[j]=x;returnj;}//劃分函數(shù)intSelect(int*a,intp,intr,intk){if(r-p<75){QuickSort(a,p,r);returna[p+k-1];}inti,j,t;for(i=0;i<=(r-p-4)/5;i++){QuickSort(a,p+5*i,p+5*i+4);inttemp=a[p+i];a[p+i]=a[p+i*5+2];a[p+i*5+2]=temp;}printf("數(shù)

8、組a下標p到p+(r-p-4)/5的元素");for(i=p;i<=p+(r-p-4)/5;i++)printf("%d",a[i]);//輸出(1)intx=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);printf("擬中位數(shù):%d",x);//輸出(2)intcount=0;i=Partition_S(a,p,r,x,&count);printf("以%d為基準的劃分:",x);for(t=p;t<=r;t++)printf("%