貪心算法實例

1、實驗一分治與遞歸算法的應(yīng)用一、實驗?zāi)康恼莆辗种嗡惴ǖ幕舅枷?分-治-合)、技巧和效率分析方法。熟練掌握用遞歸設(shè)計分治算法的基本步驟(基準與遞歸方程)。學(xué)會利用分治算法解決實際問題。二、實驗內(nèi)容1.問題描述：線性時間選擇給定n個元素和一個整數(shù)k,要求用O(n)時間找出這n個元素中第k小元素。.算法描述：Steptl :數(shù)據(jù)的保存，首先將數(shù)據(jù)保存到數(shù)組enum中，并輸入k值。Stept2 :選擇第一個數(shù)據(jù)作為分界數(shù)據(jù)，將比它小的數(shù)據(jù)儲存在它的左邊，比它大的儲存在 右邊，這樣左右子集就是原問題的兩個獨立子問題，在用同樣的方法解決這些子問題，直到 每個子集只有一個數(shù)據(jù)，就完成了全部的排序。Stept

2、3:改寫快速排序，記一趟快速排序后，分解出左子集中的元素個數(shù)為nleft，這選擇問 題是以下幾種情況：nleft=k-1，則分界數(shù)據(jù)就是選擇問題的解。nleftk-1，則選擇問題的解繼續(xù)在左子集中找。nleftk-1,則選擇問題的解繼續(xù)在右子集中找。這樣問題的規(guī)模就減小了。.測試數(shù)據(jù)5 12 23 10 45 92 3 30K值：34實驗結(jié)果如圖：應(yīng)DiV06.0MSDev98MyProjectsXminDebugyninlcexe please input the num of element B please input the elements: 5 12 23 10 45 92 3 3

3、0請輸入K值3the k min nun is：10 Press anv kev to cuntinue5關(guān)鍵代碼：int partition(int e,inti,int j)int tag=ei;/用第1個記錄作為基準while(ij)/從區(qū)間兩端交替向中間掃描，直至i=j為止while(i=tag)j-;從右向左掃描ei=ej;while(ij&ei=tag)i+;ej=ei;ei=tag;/基準記錄已被最后定位return i;intSeltct(int element,intlw,inthi,int k)if(lw=hi)return elementlw;int q=partitio

4、n(element,lw,hi);/用 quicksort 里面的 partition, q 指向參考數(shù) intnleft=q-lw+1; / l 為左數(shù)組長度if(k=nleft)return elementq;if(knleft)returnSeltct(element,q+1,hi,k-nleft);void main()int i=1;intnum;int k;intcn;coutplease input the num of elementnum;coutplease input the elements:endl;int *e=new intnum;while(icn;ei=cn;i+;