計算機算法基礎(chǔ) 第2版 習(xí)題及答案 第2章

PAGE19第2章 分治法用分治法設(shè)計一個算法找出數(shù)組A[1..n]中的最大的數(shù)，并分析所需的比較次數(shù)。解：以下用分治法的算法是作用在數(shù)組A[p,r]上的，p≤r。在調(diào)用該算法時，只須置p=1，r=n即可。Maximum(A[p..r],Max)ifp=rthenMaxA[p] exitendifq(p+r)/2Maximum(A[p..q],Max1)Maximum(A[q+1,r],Max2)Maxmax{Max1,Max2}End 我們用T(n)表示數(shù)組中數(shù)字間的比較次數(shù)，則有以下遞推關(guān)系：T(n)=T(n/2)+T(n/2)+1T(1)=0我們用歸納法證明T(n)=n–1。歸納基礎(chǔ)：因為T(1)=0，所以T(n)=n–1顯然在n=1時正確。歸納步驟：由遞推關(guān)系和歸納假設(shè)我們有以下推導(dǎo)：T(n)=T(n/2)+T(n/2)+1=(n/2-1)+(n/2-1)+1=n/2+n/2-1=n–1。歸納成功。用分治法設(shè)計一個算法同時找出數(shù)組A[1..n]中的最大和第二大的數(shù)，n2，并分析所需的比較次數(shù)。解：以下分治法的算法是作用在數(shù)組A[p,r]上的,p≤r。在調(diào)用該算法時，只須置p=1，r=n即可。Largest-and-second-largest(A[p..r],L,S)//L和S分別為最大和第二大的數(shù)ifp=rthenL?A[p] S?- //表示沒有第二大數(shù)endifq??(p+r)/2?Largest-and-second-largest(A[p..q],L1,S1)Largest-and-second-largest(A[q+1..r],L2,S2)ifL1>L2thenL?L1 S?max{L2,S1}elseL?L2 S?max{L1,S2}endif End我們用T(n)表示數(shù)組中數(shù)的比較次數(shù)，則有以下遞推關(guān)系：T(n)=T(?n/2?)+T(én/2ù)+2 T(1)=0它的解可用主方法得到。令n=2k，則有T(n)=2T(n/2)+2=Q(n)。如果想知道更為準(zhǔn)確的常數(shù)因子，我們可用歸納法證明T(n)=2n–2。歸納基礎(chǔ)：因為T(1)=0所以T(n)=2n–2顯然在n=1時正確。歸納步驟：由遞推關(guān)系和歸納假設(shè)有以下推導(dǎo)：T(n)=T(?n/2?)+T(én/2ù)+2=(2?n/2?-2)+(2én/2ù-2)+2=(2n-4)+2=2n–2。歸納成功。假設(shè)GOOGLE公司在過去n天中的股票價格記錄在數(shù)組A[1..n]中。我們希望從中找出兩天的價格，其價格的增幅最大。也就是說，我們希望找到A[i]和A[j]，i<j，使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1i<jn}。試設(shè)計一個復(fù)雜度為O(nlgn)或更好的分治算法。解：以下算法找出數(shù)組A[p..r]中序號i和j使得M=A[j]–A[i]的值最大，pi<jr。Divide-Conquer-Max-profit(p,r,m,i,j)//假設(shè)r3pifp=r thenm?-￥ exit //m=-￥表示只有一天的價格endifq=?(p+r)/2?Divide-Conquer-Max-profit(p,q,ml,il,jl)Divide-Conquer-Max-profit(q+1,r,mr,ir,jr)FindxsuchthatA[x]=min(A[p],…,A[q])FindysuchthatA[y]=max(A[q+1],…,A[r])mc?A[y]–A[x]ifmc3max{ml,mr} thenm?mc i?x j?y elseifml3mr thenm?ml i?il j?jl elsem?mr i?ir j?jr endifendifEnd調(diào)用Divide-Conquer-Max-profit(1,n,m,i,j)后即可找到對數(shù)組A[1..n]的解。上面算法的復(fù)雜度可由下面遞推關(guān)系求出：T(n)=T(?n/2?)+T(én/2ù)+Q(n)=Q(nlgn)。稍加修改后，我們可以得到O(n)復(fù)雜度的分治術(shù)算法。我們留給讀者思考。設(shè)A和B是兩個nn矩陣。眾所周知，計算乘積C=AB通常需要(n3)次乘法和加法?；斗种涡g(shù)的Strassen算法可以改進這個復(fù)雜度。下面是這個算法。為簡化起見，我們假設(shè)n=2k。Strassen’salgorithm(A,B,n);將A和B各自劃分為4個n/2n/2的矩陣如下。A=A11A12A21按下面公式遞歸計算出7個n/2n/2的矩陣。P=(A11+A22)(B11+B22); Q=(A21+A22)B11;R=A11(B12–B22); S=A22(B21-B11);T=(A11+A22)B22; U=(A21-A11)(B11+B12);V=(A12–A22)(B21+B22)。按下面公式計算出4個n/2n/2的矩陣。C11=P+S–T+V

; C12=R+T

;C21=Q+S; C22=P+R–Q+U;輸出結(jié)果如下。C=AB=C11請分析Strassen算法的復(fù)雜度。你不必證明其正確性。解: 將A和B各自劃分為4個n/2′n/2的矩陣后，第2步和第3步遞歸地進行7次n/2′n/2矩陣之間的乘法和18次n/2′n/2矩陣間的加法。所以，我們可以有以下的遞推關(guān)系：T(n)=7T(n/2)+18n2它的解是T(n)=Q()=Q()。如果我們只考慮乘法次數(shù)，那么其遞推關(guān)系是T(n)=7T(n/2)，它的解仍是T(n)=Q()=Q()。證明式（2.1）滿足T(n)=T(?n/2?)+1lg(n+1)。證明：我們用歸納法證明。歸納基礎(chǔ)：當(dāng)n=0時，式（2.1）給出T(0)=0。因為lg(0+1)=0，命題T(n)lg(n+1)正確。當(dāng)n=1時，T(1)=T(0)+1=1。因為lg(1+1)=1，命題T(n)lg(n+1)也正確。歸納步驟：假設(shè)當(dāng)n=0，1，2，…，k-1（k2）時我們有T(n)lg(n+1)。我們證明當(dāng)n=k時也有T(n)lg(n+1)。由遞推關(guān)系，我們有T(k)=T(?k/2?)+1。因為k2，有?k/2?k-1。從歸納假設(shè)，T(?k/2?)lg(?k/2?+1)，從而有：T(k)=T(?k/2?)+1lg(?k/2?+1)+1=lg(?k/2?+1)+1=lg(?k/2?+1)+lg2=lg(2?k/2?+2)。如果k是一個奇數(shù)，我們有：T(k)lg(2?k/2?+2)=lg(2(k-1)/2?+2)=lg(k+1)。 如果k是一個偶數(shù)，我們有：T(k)lg(2?k/2?+2)。=lg(k+2)=lg(k+1)。（因為k+1是奇數(shù)，向上取整后，兩者相等。）歸納成功。用替換法獲得以下遞推關(guān)系的一個漸近上界。(a) T(n)=T(n/2)+2T(n/4)解: 我們歸納證明，存在一個正數(shù)c使得T(n)≤cn。歸納基礎(chǔ)：顯然我們可以找到正數(shù)c，使得在n=1，2，3，4時，T(n)≤cn。歸納步驟：假設(shè)存在正數(shù)c，當(dāng)n=1，2，3，4，5，…，k-1（k5）時我們有T(n)￡cn。我們證明當(dāng)n=k時也有T(n)￡cn。因為當(dāng)n5時有n/2<n，n/4<n，由歸納假設(shè)有T(n/2)￡cn/2和T(n/4)cn/4。把這兩個關(guān)系代入到原遞歸關(guān)系中，得到T(n)=T(n/2)+2T(n/4)cn/2+2cn/4=cn。歸納成功，所以有T(n)=O(n)。(b) T(n)=2T(?n/2?+5)+n解：我們歸納證明，存在一個正數(shù)c使得在n≥1時有T(n)￡c(n-10)lg(n–10)。歸納基礎(chǔ)：這樣的正數(shù)c在n20時顯然可以找到，使得T(n)￡c(n-10)lg(n–10)。歸納步驟：設(shè)存在正數(shù)c，當(dāng)n=1，2，…，k-1（k21）時我們有T(n)￡c(n-10)lg(n–10)。我們證明當(dāng)n=k時也有T(n)￡c(n-10)lg(n–10)。我們可設(shè)c>10。首先，因為k-1≥20，?n/2?10。所以?n/2?+5?n/2?+?n/2?-1k-1。由歸納假設(shè)有T(?n/2?+5)￡c[(?n/2?+5)-10]lg[(?n/2?+5)-10]，即T(?n/2?+5)￡c(?n/2?-5)lg(?n/2?-5)。把這個關(guān)系代到原遞推關(guān)系中，得到T(n)=2T(?n/2?+5)+n￡2c(?n/2?-5)lg(?n/2?-5)+nc(n–10)lg(n/2-5)+n=c(n–10)lg[(n-10)/2]+n=c(n–10)[lg(n-10)-1]+n=c(n–10)lg(n-10)–c(n–10)+n<c(n–10)lg(n-10)–10(n–10)+n<c(n–10)lg(n-10) (因為–10n+100+n=100-9n<0)所以有T(n)￡c(n-10)lg(n–10)=O(nlgn)。證明以下遞推關(guān)系有T(n)=O(2n)

:(a) T(n)=nT(n/2)+nT(1)=1。解：我們用歸納法證明，存在正數(shù)c>0使得當(dāng)n1時有T(n)c2n。歸納基礎(chǔ)：我們可假定當(dāng)n≤5時，存在正數(shù)c>1使得T(n)c2n。歸納步驟：假定當(dāng)n=1，2，…，k-1(k6)時，T(n)c2n。我們證明當(dāng)n=k時仍有T(n)c2n。由歸納假設(shè)，我們有T(n/2)c2n/2。因此，由遞推關(guān)系，我們可得：T(n)=nT(n/2)+ncn2n/2+n 很容易觀察到，當(dāng)n6時，n2n/2–1，我們有T(n)cn2n/2+nc(2n/2–1)2n/2+nc2n–c2n/2+n<c2n (因為n<2n/2和c>1)所以T(n)=O(2n)

。(b) T(n)=T(n-1)+T(n-2)+n2T(1)=1，T(2)=2。解：我們用歸納法證明，存在正數(shù)c>0使得當(dāng)n1時有T(n)c2n。歸納基礎(chǔ)：當(dāng)n=1和n=2時，取c=5，顯然有T(n)<52n。歸納步驟：假定當(dāng)n=1，2，…，k-1時，我們有T(n)52n。我們證明當(dāng)n=k時仍有T(n)52n。由歸納假設(shè)，我們有T(n-1)52n-1和T(n-2)52n-2。因此，由遞推關(guān)系，我們可得：T(n)=T(n-1)+T(n-2)+n252n-1+52n-2+n2 因為當(dāng)n>1時，顯然有n252n-2，所以我們有T(n)52n-1+52n-2+n252n-1+52n-2+52n-2=52n歸納成功，所以T(n)=O(2n)

。(c) T(n)=5n2T(n/2)+n3T(1)=1。解：我們用歸納法證明存在正數(shù)c>0使得當(dāng)n1時有T(n)c2n。歸納基礎(chǔ)：我們可假定當(dāng)n≤30時，存在正數(shù)c>1使得T(n)c2n。歸納步驟：假定當(dāng)n=1，2，…，k-1(k31)時，存在正數(shù)c>1使得T(n)c2n。我們證明當(dāng)n=k時仍有T(n)c2n。由歸納假設(shè)，我們有T(n/2)c2n/2，因此，由遞推關(guān)系，我們可得：T(n)=5n2T(n/2)+n35n2c2n/2+n3。因為當(dāng)n>30時，顯然有n32n/2–1，所以，當(dāng)n>30時，我們有T(n)5n2c2n/2+n3n3c2n/2+n3(2n/2–1)c2n/2+n3c2n–c2n/2+n3c2n (因為n32n/2-1和c>1)所以T(n)=O(2n)

。用序列求和法解以下遞推關(guān)系。(a) T(n)=4T(n/2)+n2lgn解：設(shè)n=2k，得到T(2k)=4T(2k-1)+22klg2k。令W(k)=T(2k)，得到W(k)=4W(k-1)+k4k。用序列求和法，得到以下演算：W(k)=4W(k-1)+k4k=4[4W(k-2)+(k-1)4(k-1)]+k4k=42W(k-2)+(k-1)4k+k4k =42[4W(k-3)+(k-2)4(k-2)]+(k-1)4k+k4k=... =4kW(0)+4k+24k+...+(k-2)4k+(k-1)4k+k4k=4kW(0)+4k(1+2+...+(k-2)+(k-1)+k)=4kW(0)+4k(k(k+1)/2)=(22kk2)。因為k=lgn，故有T(n)=(n2(lgn)2)。(b) T(n)=3T(n/3)+n解：設(shè)n=3k，得T(3k)=3T(3k-1)+3k 用序列求和法，得到以下演算：T(3k)=3T(3k-1)+3=3[3T(3k-2)+3k-1(k-1)lg=32T(3k-2)+3k(k-1)lg=...=3kT(30)+3klg3[11+12+…+1=(3klg3=(nlglgn)。用主方法解以下遞推關(guān)系。T(n)=4T(n/2)+nT(n)=4T(n/2)+n2T(n)=4T(n/2)+n3T(n)=7T(n/2)+n2T(n)=4T(n/3)+nT(n)=3T(n/9)+5nT(n)=4T(n/2)+n2n解：(a)a=4,b=2,logba=2。顯然，可令=0.5使f(n)=n=O(n2-)=O(n1.5)。所以T(n)=(n2)。(b)a=4,b=2,logba=2。顯然，f(n)=n2=(nlgba)。所以T(n)=(n2lg(c)a=4,b=2,logba=2。顯然，可令=0.5使f(n)=n3=(n2+)=(n2.5)。再有af(n/b)=4(n/2)3=0.5n30.5f(n)。所以T(n)=(f(n))=(n3)。(d)a=7,b=2,logba=2.81。因為lgba=log27>2，所以T(n)=Q(nlg2(e)a=4,b=3,logba=1.26。顯然，可令e=0.1>0使f(n)=n=O(n1.26-)。所以有T(n)=Θ(nlogba)=Q((f)a=3,b=9,logba=0.5。因為f(n)=5n=Θ(nlogba)，所以有T(n)=Θ(nlogbalgn)=(n0.5lgn)(g)a=4,b=2,logba=2。因為f(n)=n2n=n5/2=W(n2+0.1)，再有af(n/b)=4n22n2=12n2ncf(n)，這里cT(n)=Q(f(n))=(n2n)。解遞推關(guān)系T(n)=2T(n)+lgn。解：令n=2k，得到T(2k)=2T(2k/2)+k。定義W(k)=T(2k)，我們有如下推導(dǎo)：W(k)=2W(k/2)+k=(klgk)。 因此，T(n)=(klgk)=(lgnlglgn)。證明以下序列和的公式的正確性。(a)k=1nk2k=(n-1)2n+1+2證明：令T(n)=k=1nT(n)=2T(n)-T(n)=k=1nk=[n2n+1+k=2n(k-1)2k]=n2n+1–2-k=2=n2n+1–2–(2n+1–4)=(n-1)2n+1+2。(b)k=1nklgk=(n證明:令T(n)=k=1n首先我們有T(n)=k=1nklgkk=1nklgn=lgnk=1T(n)=k=1nklgkk=n/2nklgkk=n/2n(n2lgn2)n2lgn所以有T(n)=(n2lgn)。*(c)k=2nklgk證明: 令T(n)=k=2nklgk并假定nT(n)=k=2nklgk>k=2nklgnT(n)=k=2nklgk=k=2nklgk+k=n+1n(<k=2nk<k=2nk<k=2nk<k=2nk+=O(n)+O(n2=O(n2lg 所以有T(n)=Q(n2lgn用積分法證明1k+2k+3k+…+nk=(nk+1)，這里k是任一個固定的正整數(shù)。證明： 因為i-1ixkdx<i0nxkdx<i=1n1k+1nk+1<i=1nik<1k+1[(n+因為nk+1=((n+1)k+1)，我們有i=1nik=1k+2k+3k+…+nk=(nk假設(shè)我們開一部卡車從城市A到城市B，中間一共經(jīng)過n個蘋果市場，包括城市A和城市B的蘋果市場，并且編號為1到n。在市場i，1≤i≤n，從顧客的觀點看，其每市斤的買入價B[i]和賣出價S[i]都已知，單位是元。下圖給出了一個n=6的例子?，F(xiàn)在我們計劃找一個市場i買蘋果，然后再找一個市場ji把蘋果賣掉使得賺的錢最多(如果根本賺不到錢，則使虧損越小越好)。我們假設(shè)卡車不可以向回開，并且只做一次買賣。例如，在上面的例子中，最好的方案是在市場4買蘋果而在市場6賣出去，這樣做每斤可賺7-2=5元錢。請設(shè)計一個分治算法找出市場i和j使得利潤最大或虧損最小，并分析算法復(fù)雜度。解：我們設(shè)計一個在市場p到市場r之間進行買賣的最佳解，1prn,然后調(diào)用這個算法時置p=1和r=n即可。注意，題目要求ji，所以i=j是允許的。D&C-Max-Apple-Profit(B[],S[],p,r,M,i,j)ifp=r then MS[p]–B[p] //只有一個市場情形 ip jp else q(p+q)/2 D&C-Max-Apple-Profit(B[],S[],p,q,Ml,il,jl) D&C-Max-Apple-Profit(B[],S[],q+1,r,Mr,ir,jr) findleftsuchthatB[left]=min{B[u]|puq} findrightsuchthatS[right]=max{S[u]|q+1ur} McS[right]–B[left] ifMc>max{Ml,Mr} then MMc ileft jright else ifMl>Mr then MMl iil jjl else MMr iir jjr endif endifendifreturn(M,i,j)上面的算法對應(yīng)的遞推關(guān)系是T(n)=T(n/2)+T(n/2)+(n)=(nlgn)。注：上面的算法可改進為O(n)，我們略去討論。假設(shè)n個學(xué)生S[i]的身高height[i]不同,1≤i≤n，并且已排序為height[1]<height[2]<…<height[n]。另外，他們的性別對應(yīng)地記錄在數(shù)組sex[1..n]中，sex[i]=F表示S[i]是女生，sex[i]=M表示S[i]是男生，1≤i≤n。如果sex[i]=F，sex[j]=M,并且height[i]<height[j],那么S[i]和S[j]可組成一對合格的舞伴。請用分治法設(shè)計一個復(fù)雜度為O(n)的算法來計算在這n個學(xué)生中有多少個不同的合格的配對方案。解：我們用分治法為學(xué)生序列S[p..r]設(shè)計一個計算配對方案個數(shù)的算法，然后調(diào)用這個算法時置p=1和r=n即可。這個算法在計算配對方案個數(shù)(number-pairs)時，同時算出S[p..r]中有多少個女生和多少個男生。Dancing-pairs(p,r,number-pairs,number-F,number-M) //假設(shè)rpifp=r then number-pairs0 //只有一個學(xué)生 ifsex[p]=F then number-F1 number-M0 else number-F0 number-M1 endif else q=(p+r)/2 Dancing-pairs(p,q,number-pairs-L,number-F-L,number-M-L) Dancing-pairs(q+1,r,number-pairs-R,number-F-R,number-M-R) number-pairsnumber-pairs-L+number-pairs-R+number-F-Lnumber-M-R number-Fnumber-F-L+number-F-R number-Mnumber-M-L+number-M-RendifEnd算法的復(fù)雜度為T(n)=T(n/2)+T(n)+(1)=(n)。給定序列A[1],A[2],…,A[n],請用分治法設(shè)計一個復(fù)雜度為O(nlgn)的算法來找出其中最長一段遞增(不減)序列段，即找出兩個序號ij,使得A[i]A[i+1]A[i+2]…A[j],并使j-i+1最大。解：我們用分治法為序列A[p..r],p<r,設(shè)計一個復(fù)雜度為O(nlgn)的算法來找出其中最長遞增序列段，然后調(diào)用這個算法時置p=1和r=n即可。Longest-increasing-segment(A[],p,r,d,i,j)//假設(shè)rp,A[i]到A[j]是最長遞增序列段，長為d=j-i+1。ifp=r then d1 ijp else q=(p+r)/2 Longest-increasing-segment(A[],p,q,dl,il,jl) Longest-increasing-segment(A[],q+1,r,dr,ir,jr) icq while (ic–1)pandA[ic-1]A[ic] icic–1 endwhile jcq while(jc+1)randA[jc+1]A[jc] jcjc+1 endwhile dcjc–ic+1 ifdcmax{dl,dr} then ddc iic jjc else ifdldr then ddl iil jjl else ddr iir jjr endif endifendifEnd該算法的復(fù)雜度為T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。在一條東西方向的大街上有n個人家，它們與西頭的距離順序為H[1]<H[2]<…<H[n]。另外，街上有m個學(xué)校，m<n,它們與西頭的距離順序為S[1]<S[2]<…<S[m]。假設(shè)每家都有學(xué)生，并且步行到最近的學(xué)校上學(xué)。假設(shè)某家與西頭的距離是x,請用分治法設(shè)計一個復(fù)雜度為O(lgm)的算法來確定這家的學(xué)生應(yīng)該去哪所學(xué)校和步行的距離有多遠。請用Nearest-school(S[1..m],k,d,x)作為你的算法的名字。其中，k表示S[k]是要去的學(xué)校，d表示從x到S[k]的距離。下面是一個利用(a)中的算法而設(shè)計的分治法算法。它確定這n家中哪家學(xué)生步行的距離最遠，有多遠，和去哪所學(xué)校。調(diào)用這個算法時置i=1和j=n即可。請證明這個算法的復(fù)雜度是O(nlgm)。Longest-Distance(H[i..j],S[1..m],u,h,dist) //S[u],h和dist是答案,ijifi=j then xH[i] Nearest-school(S[1..m],k,d,x) //調(diào)用(a)中的算法 uk hi distd else mid(i+j)/2 Longest-Distance(H[i..mid],S[1..m],u-L,h-L,dist-L) Longest-Distance(H[mid+1..j],S[1..m],u-R,h-R,dist-R) ifdist-L>dist-R then uu-L hh-L distdist-L else uu-R hh-R distdist-R endifendifEnd調(diào)用Longest-Distance(H[1..n],S[1..m],u,h,dist)后，我們得到從家h到學(xué)校u的距離最遠，該距離為dist。解：(a) 我們考慮學(xué)校序列為S[p..r]，算法如下。然后調(diào)用這個算法時置p=1和r=m即可。Nearest-school(S[p..r],k,d,x) //p≤r,S[k]和d是答案。ifp=r then kp d|S[k]–x| else mid(p+r)/2 if|S[mid]–x|≤|S[mid+1]–x| thennearest-school(S[p..mid],k,d,x) elsenearest-school(S[mid+1..r],k,d,x) endifendifEnd調(diào)用Nearest-school(S[1..m],k,d,x)后，我們得到與x最近的S[k],1km,其距離為d。時間復(fù)雜度為T(m)T(m/2)+O(1)=O(lgm).(b)根據(jù)算法，我們可得遞推關(guān)系時間復(fù)雜度為T(n)=T(n/2)+T(n/2)+O(1),T(1)=O(lgm)。用求和法，設(shè)n=2k。T(n)=2T(n/2)+O(1)=22T(n/4)+O(1)+O(1)=…=2kT(1)+O(k)=O(nlgm)。*在一條東西方向的大街上有n個人家，它們與西頭的距離順序為H[1]<H[2]<…<H[n]。另外，街上有m個學(xué)校，1m<n,它們與西頭的距離順序為S[1]<S[2]<…<S[m]。另外，假設(shè)人家H(k),1kn,有U(k)個學(xué)生，并且步行到最近的學(xué)校上學(xué)。為確定起見，如果家兩邊的學(xué)校等距離，學(xué)生選西邊的學(xué)校。請用分治法設(shè)計一個復(fù)雜度為O(nlgm)的算法來確定哪個學(xué)校會接收最多的學(xué)生。解：我們假設(shè)住家序列為H[u..v]，學(xué)校序列為S[i..j]，用分治法來確定哪個學(xué)校會接收最多的學(xué)生。然后，調(diào)用這個算法時，置u=1,v=n,i=1,j=m即可。Serve-most-students(S[i..j],H[u..v],k,p) //學(xué)校S[k]會接收最多的學(xué)生，人數(shù)為p。ifu>v //意味著沒有人家，或者沒有人家離S[i..j]最近 then k0 p0 returnendififi=j then ki pt=u returnendifmid-school(i+j)/2mid-line(S[mid-school]+S[mid-school+1])/2huwhile H[h]≤mid-line hh+1 //找出在mid-line東邊的第一家序號endwhileServe-most-students(S[i..mid-school],H[u..h-1],k1,p1)Serve-most-students(S[mid-school+1,j],H[h..v],k2,p2)ifp1>p2 then kk1 pp1 else kk2 pp2endifEnd調(diào)用Serve-most-students(S[1..m],H[1..n],k,p)即可得到答案。算法復(fù)雜度可由如下遞歸關(guān)系求得：T(n,1)=O(n) T(n,m)=T(n1,m/2)+T(n2,m/2)+cn //c是常數(shù)，n1+n2=n。令m=2k，可把遞推關(guān)系簡化為：T(n,m)=T(n1,m/2)+T(n2,m/2)+cn我們對m用歸納法證明，存在常數(shù)d>c，使得T(n,m)≤dnlgm+d(n+m)。歸納基礎(chǔ)：當(dāng)m=1時，命題顯然成立。歸納基礎(chǔ)：當(dāng)m>1時，我們有以下推導(dǎo)： T(n,m)=T(n1,m/2)+T(n2,m/2)+cn≤[dn1lg(m/2)+d(n1+m/2)]+[dn2lg(m/2)+d(n2+m/2)]+cn //由歸納假設(shè)=dn1(lgm-1)+d(n1+m/2)+dn2(lgm-1)+d(n2+m/2)+cn=dn1lgm+dn2lgm+dm+cn<dnlgm+d(n+m) 歸納成功。因為m<n，T(n,m)=O(nlgm)。給定序列A[1],A[2],…,A[n],請用分治法設(shè)計一個復(fù)雜度為O(nlgn)的算法來找出其中一段遞增(不減)序列段，即找出兩個序號ij,使得A[i]A[i+1]A[i+2]…A[j],并使它們的和，k=ij解： 我們用分治法為序列A[p..r]設(shè)計一個復(fù)雜度為O(nlgn)的算法來找出其中最長遞增序列,然后調(diào)用這個算法時置p=1和r=n即可。max-value-increasing-segment(A[p..r],d,i,j)//假設(shè)rp,A[i]到A[j]是輸出遞增序列段，其和為d=k=ijifp=r then dA[p] ijp else q=(p+r)/2 Max-value-increasing-segment(A[p..q],dl,il,jl) Max-value-increasing-segment(A[q+1..r],dr,ir,jr) ifA[q]>0 then icq dcA[q] while(ic–1)pandA[ic-1]A[ic]andA[ic-1]>0 icic–1 dcdc+A[ic] endwhile jcq while(jc+1)randA[jc+1]A[jc] jcjc+1 dcdc+A[jc] endwhile else dc- endif ifdcMax{dl,dr} then ddc iic jjc else ifdldr then ddl iil jjl else ddr iir jjr endif endifendifEnd該算法的復(fù)雜度為T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。給定序列A[1],A[2],…,A[n],請用分治法設(shè)計一個復(fù)雜度為O(nlgn)的算法來找出其中兩個序號i<j,使得A[i]A[j],并使它們的和，A[i]+A[j]，最小。如果沒有這樣兩個數(shù)，則輸出+∞。解: 這是和書中例題2.9對稱的題目，偽碼如下。 Min-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r then M+∞ //只有一個數(shù) else mid (p+r)/2 Min-Sum-Two-Numbers(A[p..mid],i1,j1,M1) Min-Sum-Two-Numbers(A[mid+1..r],i2,j2,M2) findi3suchthatA[i3]=min{A[k]|p≤k≤mid} S{A[k]|mid+1≤k≤r,A[i3]≤A[k]} ifS= thenM3+∞ else findj3suchthatA[j3]=min{A[k]|A[k]S} M3A[i3]+A[j3] endif ifM3<M2andM3<M1 then MM3 ii3 jj3 else ifM2<M1 then MM2 ii2 jj2 else MM1 ifM≠+∞ then ii1 jj2 endif endif endifendifEnd當(dāng)我們調(diào)用Max-Sum-Two-Numbers(A[1..n],i,j,M)時，原問題得解。算法復(fù)雜度可由下面遞推關(guān)系得到：T(n)=2T(n)+O(n)=O(nlgn)。在序列A[1],A[2],…,A[n]中，一個數(shù)可能出現(xiàn)若干次。如果一個數(shù)出現(xiàn)的次數(shù)k超過一半，即k>n/2，那么我們說這個序列有一個壟斷數(shù)。請用分治法設(shè)計一個復(fù)雜度為O(nlgn)的算法來判斷一個給定序列是否有一個壟斷數(shù)。如果有，報告這個數(shù)及其出現(xiàn)次數(shù)k，否則報告k=-。我們約定，該算法只能用比較序列中兩數(shù)字是否相同來判斷，比較的結(jié)果不報告誰大誰小，只告訴相同或不相同。當(dāng)比較的兩數(shù)字不是序列中數(shù)字時，可以報告大小。解: 算法的偽碼如下，正確性顯然。Dominating-number(A[p..r],i,k) //如果有，A[i]出現(xiàn)k>n/2次，否則i=nil，k=-ifp=r then ip k1 else mid (p+r)/2 Dominating-number(A[p..mid],i1,k1) Dominating-number(A[mid+1,r],i2,k2) ifk1- //只有A[i1]和A[i2]可