算法設(shè)計(jì)與分析實(shí)驗(yàn)(第2、3章).doc

《算法設(shè)計(jì)與分析實(shí)驗(yàn)(第2、3章).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙(附頁(yè))暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙課程名稱算法設(shè)計(jì)與分析成績(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)學(xué)院信息科學(xué)技術(shù)學(xué)院系計(jì)算機(jī)系專業(yè)軟件工程實(shí)驗(yàn)時(shí)間年月日一、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)涉及用分治策略和動(dòng)態(tài)規(guī)劃算法來(lái)求解優(yōu)化組合問(wèn)題。通過(guò)上機(jī)實(shí)驗(yàn)使學(xué)員學(xué)會(huì)程序的錄入和調(diào)試；通過(guò)實(shí)驗(yàn)結(jié)果的比較，使學(xué)員了解兩種算法的主要特點(diǎn)。二、實(shí)驗(yàn)內(nèi)容：第二章實(shí)驗(yàn)題必做——算法分析題1:線性時(shí)間選擇問(wèn)題l問(wèn)題描述給定線性序集中n個(gè)元素和一個(gè)整數(shù)k,1≤k≤n,要求找出這n個(gè)元素中第k小的元素l主要思路及步驟1.

2、把a(bǔ)數(shù)組中元素分為5個(gè)一組,選每組中位數(shù)后分別將他們移向數(shù)組頭,再用同樣的方法選取中位數(shù)的中位數(shù)x,然后按x把a(bǔ)數(shù)組分為兩個(gè)劃分,重復(fù)上述過(guò)程直至劃分中元素個(gè)數(shù)少于75,返回要求值l算法描述暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙(附頁(yè))TypeSelect(Typea[],intp,intr,intk) { if(r-p<75){ 用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組a[p:r]排序; returna[p+k-1]; }; for(inti=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即上面所說(shuō)的n-

3、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è)計(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)證其是否為以x為基準(zhǔn)元素的劃分。源代碼

4、：:#include#include#includevoidSwap(int*i,int*j){inta;a=*i;暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙(附頁(yè))*i=*j;*j=a;}//交換函數(shù)intPartition(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(

5、int*a,intp,intr){if(p

6、i]x);if(i>=j)break;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ù)組a下標(biāo)p到

7、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為基準(zhǔn)的劃分:",x);for(t=p;t<=r;t++)printf("%