分治法~線性時間選擇(共5頁)

1、計算機算法(sun f)設(shè)計與分析實 驗 報 告實驗名稱：線性時間選擇問題實驗地點：所使用的開發(fā)工具及環(huán)境：實驗?zāi)康模菏煜ふ莆辗种嗡惴ㄔO(shè)計技術(shù)二、實驗內(nèi)容：1、按教材所授內(nèi)容要求，完成“線性時間選擇問題”算法。得到一個完整正確的程序。2、問題規(guī)模：不少于20003、輸出最終結(jié)果?；舅枷?、原理和算法描述： 基本思想：將n個輸入元素劃分成 n/5個組，每組有5個元素，除最后一組可能不是5個元素之外用任意一種算法，將每組的元素排好序，并取出每組的中位數(shù)，共 n/5個。調(diào)用Select找出這 n/5個元素的中位數(shù)，如果 n/5是偶數(shù)就找兩個中位數(shù)中較大的一個。在這里我用的排序的方法是快速排序。算法描

2、述：template Type Select(Type a,int p,int r,int k)int i;if(r-p75)Qsort(a,p,r);return ap+k-1;/(r-p-4)/5相當(dāng)于n-5for(i=0; i=(r-p-4)/5; i+)/將元素每5個分成一組，分別排序，并將該組中位數(shù)與ap+i交換位置/使所有中位數(shù)都排列在數(shù)組最左側(cè)，以便進一步查找中位數(shù)的中位數(shù)Qsort(a,p+5*i,p+5*i+4);Swap(ap+5*i+2,ap+i);/找中位數(shù)的中位數(shù)Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10); i = Part

3、ition(a,p,r,x);int j = i-p+1;if(k=j)return Select(a,p,i,k);elsereturn Select(a,i+1,r,k-j);源程序清單：#include#include#include#include#includetemplate void Swap(Type &x,Type &y);inline int Random(int x, int y);template void Qsort(Type a ,int p,int r);template int Partition(Type a,int p,int r,Type x);templ

4、ate Type Select(Type a,int p,int r,int k);void main()int a2000;srand(unsigned)time(NULL);for(int i=0; i2000; i+)ai = Random(0,2000);coutai:ai ;coutendl;cout第800小元素是Select(a,0,1999,800)endl;/重新排序，對比結(jié)果Qsort(a,0,1999);for( i=0; i2000; i+)coutai:ai ;coutendl;template void Swap(Type &x,Type &y)Type temp

5、= x;x = y;y = temp;inline int Random(int x, int y) int ran_num = rand() % (y - x) + x; return ran_num;template void Qsort(Type a ,int p,int r)if(pr)Type x;int q=Partition(a,p,r,x);Qsort(a,p,q-1);Qsort(a,q+1,r);template int Partition(Type a,int p,int r,Type x)int i = p;int j = r + 1; x=ap;while(true)

6、while(a+ix&ix);if(i=j) break;Swap(ai,aj);ap=aj;aj=x;return j;template Type Select(Type a,int p,int r,int k)int i;if(r-p75)Qsort(a,p,r);return ap+k-1;/(r-p-4)/5相當(dāng)于n-5for(i=0; i=(r-p-4)/5; i+)/將元素每5個分成一組，分別排序，并將該組中位數(shù)與ap+i交換位置/使所有中位數(shù)都排列在數(shù)組最左側(cè)，以便進一步查找中位數(shù)的中位數(shù)Qsort(a,p+5*i,p+5*i+4);Swap(ap+5*i+2,ap+i);/找中

7、位數(shù)的中位數(shù)Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10); i = Partition(a,p,r,x);int j = i-p+1;if(k=j)return Select(a,p,i,k);elsereturn Select(a,i+1,r,k-j);程序運行結(jié)果（包括上機調(diào)試的情況、調(diào)試所遇到的問題是如何解決的，并對調(diào)試過程中的問題進行分析，對執(zhí)行結(jié)果進行分析。）： 在本次實驗中遇到了一些問題。在寫select方法調(diào)用的時候調(diào)用不了，然后產(chǎn)生隨機數(shù)很多的時候會出現(xiàn)問題。六、實驗總結(jié)： 本次實驗要求我們掌握線性時間選擇問題。通過調(diào)用select方法，并且通過一種排序的方法。經(jīng)過實驗后，我