第十四章優差生評選（分治算法）內容目標：分治算法基本概念優差生評選二分法實現最大子段二分不獨立算法實現第k小元素非等分分治算法實現重難點：各種分治算法設計思想以及應用實現1.功能模塊在一個班中有n個學生參加語文考試，請通過計算找出語文成績最優和最差的學生。2.1分治算法基本概念定義：分治法（DivideandConquer）的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的幾個相似問題，以便各個擊破，分而治之。算法設計思想分治法求解問題的過程是，將整個問題分解成若干個小問題后分而治之，若果分解得到的自問題相對來說還太大，則可以反復使用分治策略將這些子問題分成更小的同類型子問題，直至產生出方便求解的子問題，必要時逐步合并這些子問題的解，從而得到問題的解。分治法的基本步驟在每個遞歸層上有3個步驟。分解：將原問題分解為若干個規模較小，相互獨立，與問題形式相同的子問題；解決：若子問題規模較小而容易被解決則直接解，否則再繼續分解為更小的子問題，直到容易解決；合并：將已求解的各個子問題的解，逐步合并為原問題的解。有時問題分解后，不必求解所有的子問題，也就不必作第三步的操作。例如折半查找，在判別出問題的解在某一個子問題中后，其他的子問題就不必求解了，問題的解就是最后（最?。┑淖訂栴}的解。分治法的這類應用，又稱為“減治法”。2.2分治算法基本概念適合用分治法策略問題：當求解一個輸入規模為n且取值又相當大的問題時，用蠻力策略效率一般得不到保證。若問題能滿足以下幾個條件，就能用分治法來提高解決問題的效率。（1）能將這n個數據分解成k個不同子集合，且得到k個子集合是可以獨立求解的子問題，其中；（2）分解所得到的子問題與原問題具有相似的結構，便于利用遞歸或循環機制；（3）在求出這些子問題的解之后，就可以退出原問題的解。2.3分治算法基本概念算法框架：Dvide-and-Conquer(n)//n為問題規模

{if(n<=n0)//n0為可解子問題的規模{解子問題；

return（子問題的解）；}for（i=1；i<=k；i=i+1）//分解為較小的k個子問題P1，P2，…，Pk {分解原問題為更小的子問題Pi；

yi=Divide-and-Conquer(|Pi|);}//遞歸解決Pi，|Pi|為Pi的規模

T=MERGE(y1,y2,...,yk)

;//合并子問題return(T)

;}

其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。算法MERGE(y1,y2,...,yk)

是該分治法中的合并子集算法，用于將P的子問題P1，P2，...，Pk的相應的解y1,y2,...,yk合并為P的解。在一些問題中不需要這一步。如折半查找、二叉排序樹查找等算法。3.1業務實現---優差生評選二分法：在采用分治算法時，一個問題每次分解成的子問題個數一般是固定的，每個問題的規模也是平均分配的。當每次都將問題分解為原問題規模的一半時，稱為二分法。二分法是分治法較常用的分解方法，數據結構中的折半查找，是采用此算法實現的。優差生評選算法分析：本問題如果用循環法進行求解，要循環n次，并作2n次比較可以找到最大和最小的學生成績。這里用二分法解決該問題，比較次數較少，主要思想如下：（1）將數據等分成兩組（兩組數據可能差1），目的是分別求取其中的最大（?。┲?。（2）遞歸分解直到每組元素的個數<=2，可以簡單找到最大（?。┲怠＃?）回溯時合并問題的解，在兩個子問題的解中大者取大，小者取小，即合并當前問題的解3.2業務實現---優差生評選最大最小值對象類在進行遞歸調用時，將最優和最差學生成績用一個對象進行返回。publicclassFz_Max{ publicdoublemax; publicdoubleMin;

publicFz_Max(doublea,doubleb) { max=a; Min=b; }}

3.3業務實現---優差生評選二分法求解最優最差學生的代碼實現：publicFz_MaxMaxmin(inti,intj){//典型二分求解最大最小值問題

intmid;//局部變量求中值

Fz_Maxjg=newFz_Max(0.0,0.0); Fz_Maxleft=newFz_Max(0.0,0.0); Fz_MaxRight=newFz_Max(0.0,0.0); //局部變量記錄子問題的最大最小值

if(i==j) //若子問題規模為1個元素時直接得解

{ jg.max=a.base_info[i].st_yw; jg.Min=a.base_info[i].st_yw; } elseif(i==j-1) //若子問題為兩個元素時直接求解 if(a.base_info[i].st_yw<a.base_info[j].st_yw) { jg.max=a.base_info[j].st_yw; jg.Min=a.base_info[i].st_yw; }else { jg.max=a.base_info[i].st_yw; jg.Min=a.base_info[j].st_yw; }3.4業務實現---優差生評選二分法求解最優最差學生的代碼實現： else//若子問題為多個元素時

{ mid=(i+j)/2;//求取中間元素位置

left=Maxmin(i,mid);//遞歸求左子問題的解

Right=Maxmin(mid+1,j);//遞歸求右子問題的解

if(left.max>Right.max)//合并子問題的解

jg.max=left.max; else jg.max=Right.max; if(left.Min>Right.Min) jg.Min=Right.Min; else jg.Min=left.Min; } returnjg;}

4.1知識擴展---最大子段問題4.1知識擴展---最大子段問題問題描述：求數列的最大子段和。給定n個元素的整數列（可能為負整數）a1，a2，…，an。求形如：ai，ai+1，…，ajij=1，…，ni<=j的子段，使其和為最大。當所有整數均為負數時定義其最大子段和為0。例如，當（a1，a2，a3，a4，a5，a6）=（-2，11，-4，13，-5，-2）時，最大子段和為：i=2，j=4（下表從1開始）。4.2知識擴展---最大子段問題問題分析：用二分法將實例中的數據分解為兩組（-2，11，-4），（13，-5，-2），第一組子問題的解是11，第2組子問題的解是13，兩個子問題的解不能簡單地得到原問題的解。由此可以看出這個問題不能用二分法分解成獨立的兩個子問題，子問題中還有公共的子問題。這類問題稱為子問題重疊類的問題。 分解方法和上例一樣采用二分法，雖然分解后的問題不獨立，但通過對重疊子問題進行專門處理，并對所有子問題合并進行設計，就可以用二分策略解決此問題。 如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[(n/2)+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有3種情形：情形（1）a[1:n]的最大子段和與a[1:（n/2）]的最大子段和相同。情形（2）a[1:n]的最大子段和與a[(n/2)+1:n]的最大子段和相同。情形（3）a[1:n]的最大子段和為a[i:j]，且1<=i<=(n/2),(n+1)/2<=j<=n。情形（1）和情形（2）可遞歸求得。對于情形（3），序列中的元素a[(n/2)]與a[(n/2)+1]一定在最大子段中。因此，可以計算出a[i:(n/2)]的最大值s1；并計算出a[(n/2)+1:j]中的最大值s2。則s1+s2即為出現情況（3）時的最優值。4.3知識擴展---最大子段問題代碼實現：publicintmax_sub_sum(int[]a,intleft,intright){//求最大子段問題，a是數組，left左邊界，right右邊界

intcenter,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights if(left==right) {//當子段子段只有一個元素時，直接得到結果

if(a[left]>0) returna[left]; else return0; } else {//將子段分解成左右兩個子段

center=(left+right)/2; left_sum=max_sub_sum(a,left,center);//求左子段最大子段

right_sum=max_sub_sum(a,center+1,right);//求右子段最大子段

s1=0; lefts=0; 4.4知識擴展---最大子段問題代碼實現： for(i=center;i>=left;i--)//若最大子段包含中間元素中點向前求子段

{ lefts=lefts+a[i]; if(lefts>s1) s1=lefts; } s2=0; rights=0; for(i=center+1;i<=right;i++)//若最大子段包含中間元素，從中點向后求子段

{ rights=rights+a[i]; if(rights>s2) s2=rights; } if((s1+s2)<left_sum&&right_sum<left_sum)//若最大子段只在左子段

returnleft_sum; if((s1+s2)<right_sum)//若最大子段在右子段

returnright_sum; returns1+s2; //若最大子段包含中間元素

} }

5.1知識擴展---第k小元素問題描述：對于給定一個n個元素的數組a【0，n-1】要求從中尋找該數組的第k小元素。5.2知識擴展---第k小元素問題分析： 本問題不能用二分法分解成獨立的子問題，一種通用的設計策略是蠻力法，本題可以通過對全部數據進行排序后，得到問題的解。即使用較好的排序方法，算法的復雜度為O（nlongn）。 說到排序，快速排序算法其實也屬于分治策略的應用，不過不是對問題進行等份分解的（二分法），而是通過分界數據（支點）將問題分解成獨立的子問題。由于該題要借用此算法，在此先回顧一下快速排序算法。 首先選第一個數作為分界數據，將比它小的數據存放在它的左邊，將比它大的數據存放在它的右邊，它存放在左、右兩個子集之間。這樣左、右子集就是問題分解后的獨立子問題，再用同樣的方法，繼續解決這些子問題，直到每個子集只有一個數據，自然就排好序了，也就完成了全部數據的排序工作。 這里通過改寫快速排序算法，來解決問題。記一趟排序后，分解出左子集中的元素個數為nleft，則選擇問題，可能有以下幾種情形之一：

(1)nleft=k-1，則分解數解釋選擇問題的答案。（2）nleft>k-1，則選擇問題的答案繼續在左子集中找，問題規模變小了。（3）nleft<k-1,則選擇問題的答案繼續在右子集中找，問題變為選擇第k-nleft-1小的數，問題的規模也變小了。5.3知識擴展---第k小元素代碼實現：publicintxz(int[]a,intn,intk){ if(k<1||k>n) return-1;//錯誤

returnselect(a,0,n-1,k);//調用函數，尋找第k小元素}5.4知識擴展---第k小元素代碼實現：publicvoidSwap(refintx,refinty){ intt; t=x; x=y; y=t;}

5.5知識擴展---第k小元素代碼實現：publicintselect(int[]a,intleft,intrigh