貪心算法實例

《貪心算法實例》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實驗一分治與遞歸算法的應(yīng)用一、實驗?zāi)康?．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2．熟練掌握用遞歸設(shè)計分治算法的基本步驟（基準(zhǔn)與遞歸方程）。3．學(xué)會利用分治算法解決實際問題。二、實驗內(nèi)容1.問題描述：線性時間選擇給定n個元素和一個整數(shù)k，要求用O(n)時間找出這n個元素中第k小元素。2．算法描述：Stept1：數(shù)據(jù)的保存，首先將數(shù)據(jù)保存到數(shù)組e[num]中，并輸入k值。Stept2：選擇第一個數(shù)據(jù)作為分界數(shù)據(jù)，將比它小的數(shù)據(jù)儲存在它的左邊，比它大的儲存在右邊，這樣左右子集就是原問題的兩個獨立子問題，在用同樣

2、的方法解決這些子問題，直到每個子集只有一個數(shù)據(jù)，就完成了全部的排序。Stept3：改寫快速排序，記一趟快速排序后，分解出左子集中的元素個數(shù)為nleft，這選擇問題是以下幾種情況：（1）nleft=k-1，則分界數(shù)據(jù)就是選擇問題的解。（2）nleft>k-1，則選擇問題的解繼續(xù)在左子集中找。（3）nleft

3、;//用第1個記錄作為基準(zhǔn)'while(i=tag)j--;//從右向左掃描e[i]=e[j];while(i

4、rt里面的partition,q指向參考數(shù)intnleft=q-lw+1;//l為左數(shù)組長度if(k==nleft)returnelement[q];if(knleft)returnSeltct(element,q+1,hi,k-nleft);}voidmain(){inti=1;intnum;intk;intcn;cout<<"pleaseinputthenumofelement"<>num;cout<<"pleaseinp

5、uttheelements:"<>cn;e[i]=cn;i++;}cout<<"請輸入K值";cin>>k;intmink=Seltct(e,1,num,k);cout<<"thekminnumis:"<