計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案匯 沈孝鈞 第1-8章

PAGE2第1章 概述假設(shè)f(n)和g(n)為兩個(gè)定義域?yàn)樽匀粩?shù)的正函數(shù)。證明f(n)+g(n)=(max(f(n),g(n)))。證明：因?yàn)閷?duì)任一n≥0，max(f(n),g(n))≤f(n)+g(n)≤2max(f(n),g(n))，所以有f(n)+g(n)=O(max(f(n),g(n)))和f(n)+g(n)=(max(f(n),g(n)))，也就是f(n)+g(n)=(max(f(n),g(n)))。假設(shè)f(n)=(p(n))，g(n)=(q(n))，并且都是正函數(shù)。證明以下結(jié)論。f(n)+g(n)=(p(n)+q(n))f(n)g(n)=(p(n)q(n))f(n)/g(n)=(p(n)/q(n))證明：因?yàn)閒(n)=(p(n))，g(n)=(q(n))，所以存在常數(shù)a0,b0,c0,d0和n0使得當(dāng)n≥n0時(shí)有ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)。從以上關(guān)系可知，當(dāng)n≥n0時(shí)，ap(n)+cq(n)≤f(n)+g(n)≤bp(n)+dq(n)。讓u=min(a,c),v=max(b,d)，上式可寫為u(p(n)+q(n))≤f(n)+g(n)≤v(p(n)+q(n))所以有f(n)+g(n)=(p(n)+q(n))。由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n)，我們可得，當(dāng)n≥n0時(shí)，ap(n)cq(n)≤f(n)g(n)≤bp(n)dq(n)。讓u=ac,v=bd，上式可寫為u(p(n)q(n))≤f(n)g(n)≤v(p(n)q(n))。所以有f(n)g(n)=(p(n)q(n))由ap(n)≤f(n)≤bp(n)和cq(n)≤g(n)≤dq(n),我們可得，當(dāng)n≥n0時(shí)，ap(n)/dq(n)≤f(n)/g(n)≤bp(n)/cq(n)。讓u=a/d,v=b/c，上式可寫為u(p(n)/q(n))≤f(n)/g(n)≤v(f(n)/q(n))。所以有f(n)/g(n)=(p(n)/q(n))。對(duì)以下每個(gè)函數(shù)，用theta()記號(hào)表示與其同階的只含一項(xiàng)的函數(shù)。例如，f(n)=(n+1)3可表示為f(n)=(n3)。(a)f(n)=n2+nlgn(b)f(n)=n(c)f(n)=(解：(a)f(n)=n2+nlgn=Q(n2)(b)f(n)=n(nlgn+2n)lg2n+n=Q((c)f(n)=(n2+lgn)(n+1)n+n用theta()記號(hào)表示對(duì)下面一段程序中語句x?x+1被執(zhí)行的次數(shù)的估計(jì)。fori?1tonforj?ito3ix?x+1; endforendfor解：T(n)=i=1=i=1=2n(n+1)2+=Q(n2)。對(duì)以下每個(gè)級(jí)數(shù)和T(n)，用theta()記號(hào)表示與其同階的只含一項(xiàng)的函數(shù)。T(n)=k=1T(n)=k=1解：(a)因?yàn)門(n)=k=1nk3lgk+1kT(n)<ck=1nklgk<c=cn2lgn。所以有T(n)=O(n又因?yàn)門(n)=k=1nΘ(klgk)T(n)>dk=1nklgk>dk=n/2nklgk>dk=n/2nn/2lgn/2=dn所以有T(n)=(n2lgn)和T(n)=(n2lgn)。(b)T(n)=k=1nk+klgk+83k2lgk+5k+1在我們討論例1.3的線性搜索算法的平均復(fù)雜度時(shí)，我們假設(shè)數(shù)字x總可以在數(shù)組A中找到。這簡(jiǎn)化了問題。如果我們假定，x不出現(xiàn)在數(shù)組A中的概率是Pr(xA[1..n])=0.2，而x等于A中任一個(gè)數(shù)的概率相同，即Pr(x=A[1])=Pr(x=A[2])=…=Pr(x=A[n])，求線性搜索算法的平均復(fù)雜度。解：平均復(fù)雜度是：0.2n+1-0.2n(1+2+…+n)=0.2n+0.8n+12=0.6第2章 分治法用分治法設(shè)計(jì)一個(gè)算法找出數(shù)組A[1..n]中的最大的數(shù)，并分析所需的比較次數(shù)。解：以下用分治法的算法是作用在數(shù)組A[p,r]上的，p≤r。在調(diào)用該算法時(shí)，只須置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ǔ)：因?yàn)門(1)=0，所以T(n)=n–1顯然在n=1時(shí)正確。歸納步驟：由遞推關(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è)計(jì)一個(gè)算法同時(shí)找出數(shù)組A[1..n]中的最大和第二大的數(shù)，n2，并分析所需的比較次數(shù)。解：以下分治法的算法是作用在數(shù)組A[p,r]上的,p≤r。在調(diào)用該算法時(shí)，只須置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ǔ)：因?yàn)門(1)=0所以T(n)=2n–2顯然在n=1時(shí)正確。歸納步驟：由遞推關(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天中的股票價(jià)格記錄在數(shù)組A[1..n]中。我們希望從中找出兩天的價(jià)格，其價(jià)格的增幅最大。也就是說，我們希望找到A[i]和A[j]，i<j，使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1i<jn}。試設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)或更好的分治算法。解：以下算法找出數(shù)組A[p..r]中序號(hào)i和j使得M=A[j]–A[i]的值最大，pi<jr。Divide-Conquer-Max-profit(p,r,m,i,j)//假設(shè)r3pifp=r thenm?-￥ exit //m=-￥表示只有一天的價(jià)格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)后即可找到對(duì)數(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是兩個(gè)nn矩陣。眾所周知，計(jì)算乘積C=AB通常需要(n3)次乘法和加法。基於分治術(shù)的Strassen算法可以改進(jìn)這個(gè)復(fù)雜度。下面是這個(gè)算法。為簡(jiǎn)化起見，我們假設(shè)n=2k。Strassen’salgorithm(A,B,n);將A和B各自劃分為4個(gè)n/2n/2的矩陣如下。A=A11A12A按下面公式遞歸計(jì)算出7個(gè)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)。按下面公式計(jì)算出4個(gè)n/2n/2的矩陣。C11=P+S–T+V

; C12=R+T

;C21=Q+S; C22=P+R–Q+U;輸出結(jié)果如下。C=AB=C11請(qǐng)分析Strassen算法的復(fù)雜度。你不必證明其正確性。解: 將A和B各自劃分為4個(gè)n/2′n/2的矩陣后，第2步和第3步遞歸地進(jìn)行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時(shí)，式（2.1）給出T(0)=0。因?yàn)閘g(0+1)=0，命題T(n)lg(n+1)正確。當(dāng)n=1時(shí)，T(1)=T(0)+1=1。因?yàn)閘g(1+1)=1，命題T(n)lg(n+1)也正確。歸納步驟：假設(shè)當(dāng)n=0，1，2，…，k-1（k2）時(shí)我們有T(n)lg(n+1)。我們證明當(dāng)n=k時(shí)也有T(n)lg(n+1)。由遞推關(guān)系，我們有T(k)=T(?k/2?)+1。因?yàn)閗2，有?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是一個(gè)奇數(shù)，我們有：T(k)lg(2?k/2?+2)=lg(2(k-1)/2?+2)=lg(k+1)。 如果k是一個(gè)偶數(shù)，我們有：T(k)lg(2?k/2?+2)。=lg(k+2)=lg(k+1)。（因?yàn)閗+1是奇數(shù)，向上取整后，兩者相等。）歸納成功。用替換法獲得以下遞推關(guān)系的一個(gè)漸近上界。(a) T(n)=T(n/2)+2T(n/4)解: 我們歸納證明，存在一個(gè)正數(shù)c使得T(n)≤cn。歸納基礎(chǔ)：顯然我們可以找到正數(shù)c，使得在n=1，2，3，4時(shí)，T(n)≤cn。歸納步驟：假設(shè)存在正數(shù)c，當(dāng)n=1，2，3，4，5，…，k-1（k5）時(shí)我們有T(n)￡cn。我們證明當(dāng)n=k時(shí)也有T(n)￡cn。因?yàn)楫?dāng)n5時(shí)有n/2<n，n/4<n，由歸納假設(shè)有T(n/2)￡cn/2和T(n/4)cn/4。把這兩個(gè)關(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解：我們歸納證明，存在一個(gè)正數(shù)c使得在n≥1時(shí)有T(n)￡c(n-10)lg(n–10)。歸納基礎(chǔ)：這樣的正數(shù)c在n20時(shí)顯然可以找到，使得T(n)￡c(n-10)lg(n–10)。歸納步驟：設(shè)存在正數(shù)c，當(dāng)n=1，2，…，k-1（k21）時(shí)我們有T(n)￡c(n-10)lg(n–10)。我們證明當(dāng)n=k時(shí)也有T(n)￡c(n-10)lg(n–10)。我們可設(shè)c>10。首先，因?yàn)閗-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)。把這個(gè)關(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) (因?yàn)楱C10n+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時(shí)有T(n)c2n。歸納基礎(chǔ)：我們可假定當(dāng)n≤5時(shí)，存在正數(shù)c>1使得T(n)c2n。歸納步驟：假定當(dāng)n=1，2，…，k-1(k6)時(shí)，T(n)c2n。我們證明當(dāng)n=k時(shí)仍有T(n)c2n。由歸納假設(shè)，我們有T(n/2)c2n/2。因此，由遞推關(guān)系，我們可得：T(n)=nT(n/2)+ncn2n/2+n 很容易觀察到，當(dāng)n6時(shí)，n2n/2–1，我們有T(n)cn2n/2+nc(2n/2–1)2n/2+nc2n–c2n/2+n<c2n (因?yà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時(shí)有T(n)c2n。歸納基礎(chǔ)：當(dāng)n=1和n=2時(shí)，取c=5，顯然有T(n)<52n。歸納步驟：假定當(dāng)n=1，2，…，k-1時(shí)，我們有T(n)52n。我們證明當(dāng)n=k時(shí)仍有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 因?yàn)楫?dāng)n>1時(shí)，顯然有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時(shí)有T(n)c2n。歸納基礎(chǔ)：我們可假定當(dāng)n≤30時(shí)，存在正數(shù)c>1使得T(n)c2n。歸納步驟：假定當(dāng)n=1，2，…，k-1(k31)時(shí)，存在正數(shù)c>1使得T(n)c2n。我們證明當(dāng)n=k時(shí)仍有T(n)c2n。由歸納假設(shè)，我們有T(n/2)c2n/2，因此，由遞推關(guān)系，我們可得：T(n)=5n2T(n/2)+n35n2c2n/2+n3。因?yàn)楫?dāng)n>30時(shí)，顯然有n32n/2–1，所以，當(dāng)n>30時(shí)，我們有T(n)5n2c2n/2+n3n3c2n/2+n3(2n/2–1)c2n/2+n3c2n–c2n/2+n3c2n (因?yàn)閚32n/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)。因?yàn)閗=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)=32T(3k-2)+3k(k-1)=...=3kT(30)+3klg3[11+12+…=(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)=(n2(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。因?yàn)閘gba=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。因?yàn)閒(n)=5n=Θ(nlogba)，所以有T(n)=Θ(nlogbalgn)=(n0.5lg(g)a=4,b=2,logba=2。因?yàn)閒(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)n2所以有T(n)=(n2lgn)。*(c)k=2nklgk證明: 令T(n)=k=2nklgk并假定T(n)=k=2nklgk>k=2nkT(n)=k=2nklgk=k=2nklgk+k=n+1<k=2nk<k=2nk<k=2nk<k=2nk+=O(n)+O(n2=O(n2 所以有T(n)=Q(n2lg用積分法證明1k+2k+3k+…+nk=(nk+1)，這里k是任一個(gè)固定的正整數(shù)。證明： 因?yàn)閕-1ixkdx<i0nxkdx<i=1n1k+1nk+1<i=1nik<1k+1[(n+因?yàn)閚k+1=((n+1)k+1)，我們有i=1nik=1k+2k+3k+…+nk=(n假設(shè)我們開一部卡車從城市A到城市B，中間一共經(jīng)過n個(gè)蘋果市場(chǎng)，包括城市A和城市B的蘋果市場(chǎng)，并且編號(hào)為1到n。在市場(chǎng)i，1≤i≤n，從顧客的觀點(diǎn)看，其每市斤的買入價(jià)B[i]和賣出價(jià)S[i]都已知，單位是元。下圖給出了一個(gè)n=6的例子。現(xiàn)在我們計(jì)劃找一個(gè)市場(chǎng)i買蘋果，然后再找一個(gè)市場(chǎng)ji把蘋果賣掉使得賺的錢最多(如果根本賺不到錢，則使虧損越小越好)。我們假設(shè)卡車不可以向回開，并且只做一次買賣。例如，在上面的例子中，最好的方案是在市場(chǎng)4買蘋果而在市場(chǎng)6賣出去，這樣做每斤可賺7-2=5元錢。請(qǐng)?jiān)O(shè)計(jì)一個(gè)分治算法找出市場(chǎng)i和j使得利潤(rùn)最大或虧損最小，并分析算法復(fù)雜度。解：我們?cè)O(shè)計(jì)一個(gè)在市場(chǎng)p到市場(chǎng)r之間進(jìn)行買賣的最佳解，1prn,然后調(diào)用這個(gè)算法時(shí)置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] //只有一個(gè)市場(chǎng)情形 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)上面的算法對(duì)應(yīng)的遞推關(guān)系是T(n)=T(n/2)+T(n/2)+(n)=(nlgn)。注：上面的算法可改進(jìn)為O(n)，我們略去討論。假設(shè)n個(gè)學(xué)生S[i]的身高h(yuǎn)eight[i]不同,1≤i≤n，并且已排序?yàn)閔eight[1]<height[2]<…<height[n]。另外，他們的性別對(duì)應(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]可組成一對(duì)合格的舞伴。請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(n)的算法來計(jì)算在這n個(gè)學(xué)生中有多少個(gè)不同的合格的配對(duì)方案。解：我們用分治法為學(xué)生序列S[p..r]設(shè)計(jì)一個(gè)計(jì)算配對(duì)方案?jìng)€(gè)數(shù)的算法，然后調(diào)用這個(gè)算法時(shí)置p=1和r=n即可。這個(gè)算法在計(jì)算配對(duì)方案?jìng)€(gè)數(shù)(number-pairs)時(shí)，同時(shí)算出S[p..r]中有多少個(gè)女生和多少個(gè)男生。Dancing-pairs(p,r,number-pairs,number-F,number-M) //假設(shè)rpifp=r then number-pairs0 //只有一個(gè)學(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],請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法來找出其中最長(zhǎng)一段遞增(不減)序列段，即找出兩個(gè)序號(hào)ij,使得A[i]A[i+1]A[i+2]…A[j],并使j-i+1最大。解：我們用分治法為序列A[p..r],p<r,設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法來找出其中最長(zhǎng)遞增序列段，然后調(diào)用這個(gè)算法時(shí)置p=1和r=n即可。Longest-increasing-segment(A[],p,r,d,i,j)//假設(shè)rp,A[i]到A[j]是最長(zhǎng)遞增序列段，長(zhǎng)為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個(gè)人家，它們與西頭的距離順序?yàn)镠[1]<H[2]<…<H[n]。另外，街上有m個(gè)學(xué)校，m<n,它們與西頭的距離順序?yàn)镾[1]<S[2]<…<S[m]。假設(shè)每家都有學(xué)生，并且步行到最近的學(xué)校上學(xué)。假設(shè)某家與西頭的距離是x,請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(lgm)的算法來確定這家的學(xué)生應(yīng)該去哪所學(xué)校和步行的距離有多遠(yuǎn)。請(qǐng)用Nearest-school(S[1..m],k,d,x)作為你的算法的名字。其中，k表示S[k]是要去的學(xué)校，d表示從x到S[k]的距離。下面是一個(gè)利用(a)中的算法而設(shè)計(jì)的分治法算法。它確定這n家中哪家學(xué)生步行的距離最遠(yuǎn)，有多遠(yuǎn)，和去哪所學(xué)校。調(diào)用這個(gè)算法時(shí)置i=1和j=n即可。請(qǐng)證明這個(gè)算法的復(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的距離最遠(yuǎn)，該距離為dist。解：(a) 我們考慮學(xué)校序列為S[p..r]，算法如下。然后調(diào)用這個(gè)算法時(shí)置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。時(shí)間復(fù)雜度為T(m)T(m/2)+O(1)=O(lgm).(b)根據(jù)算法，我們可得遞推關(guān)系時(shí)間復(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個(gè)人家，它們與西頭的距離順序?yàn)镠[1]<H[2]<…<H[n]。另外，街上有m個(gè)學(xué)校，1m<n,它們與西頭的距離順序?yàn)镾[1]<S[2]<…<S[m]。另外，假設(shè)人家H(k),1kn,有U(k)個(gè)學(xué)生，并且步行到最近的學(xué)校上學(xué)。為確定起見，如果家兩邊的學(xué)校等距離，學(xué)生選西邊的學(xué)校。請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgm)的算法來確定哪個(gè)學(xué)校會(huì)接收最多的學(xué)生。解：我們假設(shè)住家序列為H[u..v]，學(xué)校序列為S[i..j]，用分治法來確定哪個(gè)學(xué)校會(huì)接收最多的學(xué)生。然后，調(diào)用這個(gè)算法時(shí)，置u=1,v=n,i=1,j=m即可。Serve-most-students(S[i..j],H[u..v],k,p) //學(xué)校S[k]會(huì)接收最多的學(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東邊的第一家序號(hào)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)系簡(jiǎn)化為：T(n,m)=T(n1,m/2)+T(n2,m/2)+cn我們對(duì)m用歸納法證明，存在常數(shù)d>c，使得T(n,m)≤dnlgm+d(n+m)。歸納基礎(chǔ)：當(dāng)m=1時(shí)，命題顯然成立。歸納基礎(chǔ)：當(dāng)m>1時(shí)，我們有以下推導(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) 歸納成功。因?yàn)閙<n，T(n,m)=O(nlgm)。給定序列A[1],A[2],…,A[n],請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法來找出其中一段遞增(不減)序列段，即找出兩個(gè)序號(hào)ij,使得A[i]A[i+1]A[i+2]…A[j],并使它們的和，k=ij解： 我們用分治法為序列A[p..r]設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法來找出其中最長(zhǎng)遞增序列,然后調(diào)用這個(gè)算法時(shí)置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],請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法來找出其中兩個(gè)序號(hào)i<j,使得A[i]A[j],并使它們的和，A[i]+A[j]，最小。如果沒有這樣兩個(gè)數(shù)，則輸出+∞。解: 這是和書中例題2.9對(duì)稱的題目，偽碼如下。 Min-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r then M+∞ //只有一個(gè)數(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)時(shí)，原問題得解。算法復(fù)雜度可由下面遞推關(guān)系得到：T(n)=2T(n)+O(n)=O(nlgn)。在序列A[1],A[2],…,A[n]中，一個(gè)數(shù)可能出現(xiàn)若干次。如果一個(gè)數(shù)出現(xiàn)的次數(shù)k超過一半，即k>n/2，那么我們說這個(gè)序列有一個(gè)壟斷數(shù)。請(qǐng)用分治法設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法來判斷一個(gè)給定序列是否有一個(gè)壟斷數(shù)。如果有，報(bào)告這個(gè)數(shù)及其出現(xiàn)次數(shù)k，否則報(bào)告k=-。我們約定，該算法只能用比較序列中兩數(shù)字是否相同來判斷，比較的結(jié)果不報(bào)告誰大誰小，只告訴相同或不相同。當(dāng)比較的兩數(shù)字不是序列中數(shù)字時(shí)，可以報(bào)告大小。解: 算法的偽碼如下，正確性顯然。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]可能，檢查之。 then forjmid+1tor ifA[j]=A[i1] then k1k1+1 endif endfor endif ifk2- then forjptomid ifA[j]=A[i2] then k2k2+1 endif endfor endif ifk1>(p-r+1)/2 then ii1 kk1 else ifk2>(p-r+1)/2 then ii2 kk2 else inil k- endif endifendifEnd該算法的復(fù)雜度為T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。*每個(gè)多米諾骨牌有兩個(gè)正整數(shù)。假設(shè)有n個(gè)多米諾骨牌S1,S2,…,Sn水平地放成一排如下例所示。假設(shè)我們不能改變骨牌之間相對(duì)位置，但可以原地翻轉(zhuǎn)每個(gè)骨牌。我們用L[i]和R[i]分別表示Si(1in)左邊和右邊的數(shù)。例如，在下例中L[1]=5,R[1]=8,L[2]=4,R[2]=2等。如果L[i]<R[i]，我們稱Si被置為狀態(tài)0并記為W[i]=0，翻轉(zhuǎn)后則為狀態(tài)1并記為W[i]=1。例如下例中S1為狀態(tài)0而S2為狀態(tài)1。如果L[i]=R[i]，Si的狀態(tài)可記為W[i]=0或W[i]=1。請(qǐng)用分治法設(shè)計(jì)一個(gè)算法來確定每個(gè)骨牌的狀態(tài)使得M=i=1n-1R[i]×L[i+1]取得最大值解: 這題的主要困難在于，如果我們用常規(guī)的辦法將序列分為兩半求解，那么兩部分的最佳解合在一起不一定給出全局的最佳解。技巧是，我們把問題稍加修改。我們?cè)谠蛄兄幸雰蓚€(gè)非負(fù)整數(shù)u和v,并確定各骨牌狀態(tài)以使得M=u′L[1]+i=1n-1R[i]×L[i+1]+R[n]′v取得最大值。顯然，如果我們能解決這個(gè)修改后的問題，那么當(dāng)我們置u=v=0的話即得出原問題的解。假設(shè)S[p,r]表示從Sp到Sr的骨牌序列，下面的分治算法確定這些骨牌的狀態(tài)使M=u′L[p]+i=pr-1R[i]×L[i+1]+R[r]′v取得最大值。我們假設(shè)Si(1￡i￡n)中兩數(shù)字存放在A[i]和B[i]中并且A[i]￡BMax-Value(u,v,S[p,r],W[p,r],m)ifp>r then m?u′v //骨牌序列為空 exitendif q?x?A[q]y?B[q] //中間骨牌的兩個(gè)數(shù)x和yMax-Value(u,x,S[p,q-1],W1[p,q-1],m1) //x用于左邊序列Max-Value(u,y,S[p,q-1],W2[p,q-1],m2) //y用于左邊序列Max-Value(x,v,S[q+1,r],W3[q+1,r],m3) //x用于右邊序列Max-Value(y,v,S[q+1,r],W4[q+1,r],m4) //y用于右邊序列if(m1+m4)>(m2+m3) //中間骨牌為狀態(tài)0時(shí)較好 then W[p,q-1]?W1[p,q-1] W[q+1,r]?W4[q+1,r] W[q]?0 m?(m1+m4) else W[p,q-1]?W2[p,q-1] //中間骨牌為狀態(tài)1時(shí)較好 W[q+1,r]?W3[q+1,r] W[q]?1 m?(m2+m3)endifEnd算法正確性顯然，當(dāng)我們調(diào)用Max-Value(0,0,S[1,n],W[1,n],m)時(shí)便得到結(jié)果。算法復(fù)雜度為T(n)=4T(n-12)+Q(n)=Q(n2第3章 基于比較的排序給出一例證明在最壞情況下，合并算法至少需要n1+n2-1次比較。解：作為一個(gè)例子，如果數(shù)組A[1..n1]和數(shù)組B[1..n2]中數(shù)滿足以下條件，那么合并算法需要n1+n2-1次比較:A[1]<A[2]<A[3]<…<A[n1-1]<B[1]<B[2]<B[3]<…<B[n2]<A[n1]。(a) 設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法以確定數(shù)組A[1..n]中的n個(gè)數(shù)是否有相同的數(shù)字。 (b) 設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法把數(shù)組A[1..n]中出現(xiàn)奇數(shù)次的數(shù)字挑選出來。解：這兩個(gè)問題可以用排序來解決。我們假定n2。(a)Repeated-Number(A[1..n])Heap-sort(A[1..n]) //用堆排序?qū)[1..n]進(jìn)行排序fori2ton ifA[i]=A[i-1] thenreturn“Yes,A[i]andA[i-1]areidentical.” //報(bào)告A[i]和A[i-1]相同 endifendforreturn“Norepeatednumbers.” //沒有重復(fù)的數(shù)字End因?yàn)樵撍惴ǖ拇蟛糠謺r(shí)間化在第一步的排序，所以算法復(fù)雜度為O(nlgn)。(b)Odd-occurrence(A[1..n])Heap-sort(A[1..n]) //用堆排序?qū)[1..n]進(jìn)行排序sA[1] //A[1]是第一個(gè)要檢查的數(shù)j0 //出現(xiàn)奇數(shù)次的數(shù)將被按序放入B[1..j]oddtruefori:=2ton ifs=A[i] then ifodd=true thenoddfalse elseoddtrue endif else ifodd=false //A[i]有一個(gè)不同的值 then oddtrue sA[i] else jj+1 //odd=true，記錄到B中 B[j]s sA[i] //odd仍然為true，未變 endif endifendforifodd=true //最后一輪中，s=A[n]，此時(shí)處理 then jj+1 B[j]s endifreturnB[1..j]End 因?yàn)樵撍惴ǖ拇蟛糠謺r(shí)間化在第一步的排序，其復(fù)雜度為O(nlgn)，而后面步驟所需時(shí)間為O(n)，所以算法復(fù)雜度為O(nlgn)。(a) 一棵高為h

的堆最少和最多能含有多少個(gè)結(jié)點(diǎn)(包括所有內(nèi)結(jié)點(diǎn)和葉結(jié)點(diǎn))？ (b) 證明一個(gè)含有n個(gè)數(shù)的堆的高為?lgn?。解

: (a) 當(dāng)一棵高為h

的堆是一棵滿二叉樹時(shí)含有最多的結(jié)點(diǎn)。此時(shí)的結(jié)點(diǎn)數(shù)是：Nmax(h)=1+2+22+23...+2h=2h+1–1。 當(dāng)一棵高為h

的堆的底層只含有一個(gè)葉結(jié)點(diǎn)時(shí)，它含有的結(jié)點(diǎn)數(shù)最少。此時(shí)的結(jié)點(diǎn)數(shù)是：Nmin(h)=Nmax(h-1)+1=2h。(b) 設(shè)一個(gè)含有n個(gè)數(shù)的堆的高為h。從上題(a)可知：Nmin(h)￡n￡Nmax(h)，即2h￡n￡2h+1–1，也就是2h￡n<2h+1。由此可得h￡lgn<h+1。所以有h=?lgn?。假設(shè)Heap-Delete(A[1..n],i)表示將A[i]這個(gè)數(shù)從數(shù)組A[1..n]構(gòu)成的堆中刪去，并使所余n-1個(gè)數(shù)形成一個(gè)堆的操作。用偽碼設(shè)計(jì)一個(gè)復(fù)雜度為O(lgn)的算法來實(shí)現(xiàn)Heap-Delete(A[1..n],i)(1in)。解：Heap-Delete(A[1..n],i) //1inkey←A[i]A[i]?A[n]n←n–1ifin //如果i=n+1，則已被刪去 then ifkey>A[i] then Max-Heapify(A[1..n],i) else key←A[i] Heap-Increase-Key(A[1..n],i,key) endifendifEnd假設(shè)Heap-Decrease-Key(A[1..n],i,key)表示在數(shù)組A[1..n]構(gòu)成的堆中把A[i]的值減少為key，并把A[1..n]修復(fù)為一個(gè)堆的操作。用偽碼設(shè)計(jì)一個(gè)復(fù)雜度為O(lgn)的算法來實(shí)現(xiàn)Heap-Decrease-Key(A[1..n],i，key)(1in)。解：Heap-Decrease-Key(A[1..n],i,key) //1inifkey>A[i] thenreturn“error,newkeyislargerthancurrentkey” //錯(cuò)誤，新值大于現(xiàn)有值endifA[i]?keyMax-Heapify(A[1..n],i)End給定一個(gè)排好序的數(shù)組A[1]≤A[2]≤…≤A[n]，第2章里例2.1中的二元搜索算法可以用一棵二元搜索樹來描述。樹中每個(gè)內(nèi)結(jié)點(diǎn)含有一個(gè)數(shù)組中的數(shù)。樹根里的數(shù)是算法進(jìn)行比較的第一個(gè)數(shù)，即A[mid]。如果x=A[mid]，則搜索成功并報(bào)告。否則，根據(jù)結(jié)果是x<A[mid]還是x>A[mid]，算法決定是遞歸搜索左半部分，還是遞歸搜索右半部分。因而這棵二元搜索樹的左右兩子樹可相應(yīng)地遞歸構(gòu)造。下圖給出了當(dāng)n=1，2，3，4時(shí)二元搜索樹的例子。其中葉結(jié)點(diǎn)表示搜索失敗的情況。證明一棵二元搜索樹T的葉結(jié)點(diǎn)只出現(xiàn)在最底下二層。證明一棵含n個(gè)數(shù)的二元搜索樹的高度為h=élg(n+1)ù。解: (a)證明一棵二元搜索樹T的葉結(jié)點(diǎn)只出現(xiàn)在最底二層。我們對(duì)n進(jìn)行數(shù)學(xué)歸納。歸納基礎(chǔ)：當(dāng)n￡4，上面圖例直接證明了這個(gè)結(jié)論。歸納步驟： 假設(shè)當(dāng)n=1，2，…，k-1(k>4)時(shí)，一棵含n個(gè)內(nèi)結(jié)點(diǎn)的二元搜索樹T的葉結(jié)點(diǎn)只出現(xiàn)在最底二層。下面我們證明當(dāng)n=k時(shí)結(jié)論仍正確。我們分兩種情況證明。n是奇數(shù)。在這種情況下，左右兩子樹L和R都含有(n-1)/2個(gè)內(nèi)結(jié)點(diǎn)因而形狀完全相同。由歸納假設(shè)，它們的葉結(jié)點(diǎn)只出現(xiàn)在最底二層。這些葉結(jié)點(diǎn)也就是T的葉結(jié)點(diǎn)。所以結(jié)論正確。n是偶數(shù)。在這種情況下，左子樹含(n-2)/2=n/2-1個(gè)數(shù)字而右子樹含n/2個(gè)數(shù)字。因?yàn)樽笥易訕涠际峭耆鏄?，所以左子樹總共含?n-1)個(gè)結(jié)點(diǎn)而右子樹含(n+1)個(gè)結(jié)點(diǎn)(包括葉結(jié)點(diǎn))。右子樹正好比左子樹多二個(gè)結(jié)點(diǎn)。如果左右兩子樹L和R的高度相等，那么結(jié)論得證。故假定他們高度不等。如下圖所示，右子樹比左子樹必定高一層。因?yàn)橛易訕涞牡讓又辽俸€(gè)葉子，左子樹必須是一個(gè)滿二叉樹，否則它會(huì)比右子樹少至少3個(gè)結(jié)點(diǎn)，不可能。所以左子樹的所有葉子必須在最底層。這就是說，左右子樹的所有葉子都在最底二層。歸納成功。LLRh1h2h1-1證明一棵含n個(gè)數(shù)的二元搜索樹的高度為h=élog(n+1)ù。證明： 因?yàn)橐豢煤琻個(gè)數(shù)的二元搜索樹有(n+1)個(gè)葉子，它總共有2n+1個(gè)結(jié)點(diǎn)。假設(shè)它的高度為h。由(a)部分的解知，它的所有葉子在最底二層。因?yàn)榈讓又辽儆袃蓚€(gè)葉子，但不會(huì)多于2h個(gè)葉子，所以有(1+2+…+2h-1)+2￡2n+1￡1+2+…+2h-1+2h，即2h+1￡2n+1￡2h+1–1，即(2h+2)￡2n+2￡2h+1。由此得 2h-1+1￡(n+1)￡2h，2h-1<(n+1)￡2hh-1<log(n+1)￡hh-1<élog(n+1)ù￡h。所以有h=élog(n+1)ù。*一個(gè)結(jié)點(diǎn)在一棵樹中的高度就是以這個(gè)結(jié)點(diǎn)為根的子樹的高度。證明在一個(gè)有n個(gè)數(shù)字的堆中，高度為h的結(jié)點(diǎn)數(shù)最多為én2h+1ù證明: 設(shè)x是一個(gè)有n個(gè)數(shù)字的堆中高度為h的結(jié)點(diǎn)數(shù)。我們注意到兩棵高為h的子樹的結(jié)點(diǎn)不相交，即一棵高為h的子樹中結(jié)點(diǎn)不屬于任一個(gè)其他的高為h的子樹。另外，因?yàn)樗腥~結(jié)點(diǎn)都在最底兩層，所有高為h的子樹，最多除一個(gè)外，都必定是滿二叉樹。下面的圖清楚地解釋了這一點(diǎn)。唯一可能不是滿二叉樹的子樹唯一可能不是滿二叉樹的子樹一棵高為h的滿二叉樹一共有2h+1-1個(gè)結(jié)點(diǎn)。而一棵不是滿二叉樹的高為h的子樹，也至少有2h個(gè)結(jié)點(diǎn)?，F(xiàn)在，試想把這x個(gè)子樹中除了根以外的結(jié)點(diǎn)從T中刪除，剩下的部分是一個(gè)有x個(gè)葉子的完全二叉樹。這個(gè)樹中除葉子外的內(nèi)結(jié)點(diǎn)數(shù)正好是(x-1)個(gè)。他們正好是T中除高為h的子樹以外的結(jié)點(diǎn)集合。所以我們可得以下不等式：n≥(x-1)+(x-1)(2h+1-1)+2h=(x-1)(2h+1)+2h=x(2h+1)-2h+1+2h≥x(2h+1)-2h因此有x≤(n+2h)/(2h+1)=(n/2h+1)+1/2≤én2h+1ù因?yàn)閤必須是整數(shù)，故有x≤én2h+1(K路合并問題) 利用最小堆(min-heap)設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(nlgk)的算法將k個(gè)排好序的序列合并為單一排好序的序列。這里n是所有k個(gè)序列中數(shù)字的總數(shù)。解: 假定A1，A2，...，Ak為k個(gè)要合并的序列。假設(shè)每個(gè)序列已從小到大排好，算法思路如下：首先，把每個(gè)序列的頭，A1[1],A2[1],...,Ak[1]，即各序列中最小的數(shù)取出并組織為一個(gè)最小堆。那么，堆中的根顯然是所有n個(gè)數(shù)中最小的數(shù)。 然后，每次將堆的根中的數(shù)取出并放到輸出序列中。根中的數(shù)必定是還未輸出的所有數(shù)中最小的數(shù)。如果根中的數(shù)來自序列Aj(1￡j￡k)，那么將根中的數(shù)輸出之后，我們把Aj中下一個(gè)最小的數(shù)，即當(dāng)前Aj的頭從序列Aj取走放到堆的根結(jié)點(diǎn)并將堆修復(fù)。如果序列Aj中沒有數(shù)字了，那么我們把堆的規(guī)模減一并修復(fù)。這時(shí)參加合并的序列少了一個(gè)。因?yàn)槎延筛餍蛄兄凶钚〉臄?shù)組成，在根中的數(shù)顯然是當(dāng)前還未輸出的所有數(shù)中最小的數(shù)，算法顯然正確。下面是這個(gè)算法的偽碼。我們假定初始時(shí)，每個(gè)序列至少有一個(gè)數(shù)字并用一個(gè)特殊記號(hào)￥表示序列結(jié)束。k-Merge(A1,A2,...,Ak)Buildamin-heapH[1..k]fromA1[1],A2[1],...,Ak[1] //由k個(gè)序列頭建堆fori?1tok ifH[i]=Aj[1] thenQ[i]?j //記住堆中第i個(gè)數(shù)是從第j個(gè)序列來的。 endifendforforj?1tok head[j]?2 //head[j]是序列Aj中當(dāng)前剩余部分的首項(xiàng)，即最小數(shù)的位置。endfor i?0 //用于輸出序號(hào)heap-size?kwhileheap-size10 i?i+1 C[i]?H[1] //C是輸出序列。 j?Q[1] p?head[j] ifAj[p]1￥ then H[1]?Aj[p] head[j]?p+1 else H[1]?H[heap-size] Q[1]?Q[heap-size] Heap-size?heap-size-1 endif ifheap-size>0 thenHeapify(H[1..heap-size],1) //注意，移動(dòng)H[k]時(shí)，Q[k]要相應(yīng)更新。 endifendwhileEnd因?yàn)槊枯敵鲆粋€(gè)數(shù)之后我們需要修復(fù)含有不超過k個(gè)元素的堆，其時(shí)間為O(lgk)，所以總的時(shí)間復(fù)雜度為O(nlgk)。大家熟知，數(shù)組A[1..n]形成的堆里，第i個(gè)數(shù)A[i](1≤i≤n)的左兒子、右兒子、及父親的所在位置可以由下面公式算出：Left(A[i])=A[2i]Right(A[i])=A[2i+1]Parent(A[i])=A[?i/2?]但是我們很多時(shí)侯不能把這個(gè)堆存放在從A[1]開始的數(shù)組中，而是存放在從A[p]開始的n個(gè)單元中，即存放在A[p..r]中，這里r=p+n–1。這相當(dāng)于把這n個(gè)數(shù)在數(shù)組中向右平移了(p-1)個(gè)位置。請(qǐng)給出在這種情況下，確定數(shù)字A[i](p≤i≤r)的左兒子、右兒子、及父親的所在位置的公式。解: 我們把A[p..r]一一對(duì)應(yīng)地映射到另一個(gè)數(shù)組B[1..n]中，A[i]=B[i-p+1]，p≤i≤r，而B[j]=A[j+p-1]，1≤j≤n。因此新的公式是：Left(A[i])=Left(B[i-p+1])=B[2(i-p+1)]=B[2i-2p+2]=A[2i–p+1]，Right(A[i])=Right(B[i-p+1])]=B[2(i-p+1)+1]=B[2i–2p+3]=A[2i–p+2]，Parent(A[i])=Parent(B[i-p+1])=B[?(i-p+1)/2?]=A[?(i-p+1)/2+p-1]=A[?(i+p-1)/2?]。證明一個(gè)有n個(gè)數(shù)字的堆的左子樹最多含有2n/3個(gè)結(jié)點(diǎn)。證明: 如下圖所示，我們用L代表左子樹中的結(jié)點(diǎn)數(shù)，用R代表右子樹中的結(jié)點(diǎn)數(shù)。在左子樹中，我們用B代表在底層的葉子結(jié)點(diǎn)數(shù)，而用U代表底層上面的結(jié)點(diǎn)數(shù)，L=U+B。顯然，我們有關(guān)系B≤U+1和U≤R。因而得到L=U+B≤2U+1≤2R+1。因?yàn)長(zhǎng)+R+1=n，所以R=n–L-1。從而有L≤2R+1≤2(n–L-1)+1=2n-2L-1<2n-2L，也就是L<2n/3，即L2n/3。假設(shè)給定一個(gè)n個(gè)數(shù)的數(shù)組A[1..n]和一個(gè)常數(shù)x。我們希望確定數(shù)組中是否存在兩個(gè)數(shù)，A[i]和A[j](1i<jn)，使得A[i]+A[j]=x。設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法解決這個(gè)問題。如果這樣兩個(gè)數(shù)存在，則報(bào)告這兩個(gè)數(shù)，否則報(bào)告不存在。解: 主要思路如下。我們先將數(shù)組A[1..n]從左到右排序?yàn)锳[1]≤A[2]≤A[3]≤…≤A[n]。然后把最小的數(shù)和最大的數(shù)相加(開始是A[1]和A[n]相加)。如果其和等于x，則問題解決。如果其和小于x，則最小的數(shù)不可能在解之中而丟棄。如其和大于x，則最大的數(shù)不可能在解之中而丟棄。每次我們從左丟棄一個(gè)最小數(shù)或從右丟棄一個(gè)最大數(shù)直至找到答案。Search-SUM(A[1..n]，x)Heap-sort(A[1..n])使得A[1]≤A[2]≤A[3]≤…≤A[n]exist?falsei?1j?nwhilei<jandexist=false ifA[i]+A[j]=x then return(true,i,j) else ifA[i]+A[j]<x theni?i+1 elsej?j-1 endif endifendwhilereturn(nosolution)End因?yàn)榕判蛐枰狾(nlgn)時(shí)間而以后的搜索只需要O(n)時(shí)間，上面算法的復(fù)雜度是O(nlgn)。錦標(biāo)賽排序法是一個(gè)基于比較的排序算法。它可以用一個(gè)稱之為錦標(biāo)賽樹(tournamenttree)的完全二叉樹來描述。這個(gè)二叉樹要求正好有n個(gè)葉子來存儲(chǔ)n個(gè)要排序的數(shù)字，并且所有葉子在底層或倒數(shù)第2層。下面是一個(gè)有5個(gè)葉子的一個(gè)錦標(biāo)賽樹圖例。9924710算法開始前，被排序的n個(gè)數(shù)字被放在這n個(gè)葉子中。每個(gè)內(nèi)結(jié)點(diǎn)代表一次比較。每次比較中勝者，即較小的數(shù)，參加下一輪在其父結(jié)點(diǎn)處的比較。在每個(gè)內(nèi)結(jié)點(diǎn)處，當(dāng)它的兩個(gè)子結(jié)點(diǎn)處的比較有了結(jié)果之后，該結(jié)點(diǎn)處的比較即可進(jìn)行。最后，在根結(jié)點(diǎn)處的比較決出冠軍，即最小的數(shù)。因?yàn)橐还灿?n-1)個(gè)內(nèi)結(jié)點(diǎn)，所以只需(n-1)次比較便可以找到最小數(shù)。當(dāng)最小的數(shù)被確定后，即可把它送到輸出序列中。另外，把它原來所在的葉子中的值改為。顯然，重復(fù)上面的過程可得到下一個(gè)最小的數(shù)。如果重復(fù)所有在內(nèi)結(jié)點(diǎn)處的比較去找下一個(gè)最小的數(shù)，我們又需要(n-1)次比較。這個(gè)復(fù)雜度太高。請(qǐng)?jiān)O(shè)計(jì)一個(gè)只需O(lgn)次比較的算法去找下一個(gè)最小的數(shù)。(只須解釋步驟，不要求偽碼。)請(qǐng)用偽碼設(shè)計(jì)一個(gè)用數(shù)組來實(shí)現(xiàn)錦標(biāo)賽排序的算法，使其復(fù)雜度為O(nlgn)。解：在找下一個(gè)最小數(shù)時(shí)，如果我們重復(fù)所有在內(nèi)結(jié)點(diǎn)的比較的話，那么，在大部分結(jié)點(diǎn)處所比較的兩個(gè)數(shù)仍然是在找前一個(gè)最小數(shù)時(shí)進(jìn)行過比較的兩個(gè)數(shù)，這部分比較不需再做。那么，在哪些結(jié)點(diǎn)處所比較的兩個(gè)數(shù)會(huì)有變化呢？容易看出，可能有變化的結(jié)點(diǎn)必定是在從前一個(gè)最小數(shù)所在的葉子到根的這條路徑上。所以我們的算法是，在每個(gè)結(jié)點(diǎn)處記錄每次比較后誰是勝者、誰是敗者。然后在找下一個(gè)最小數(shù)時(shí)，沿著前一個(gè)最小數(shù)所在的葉子到根的這條路徑，在每個(gè)結(jié)點(diǎn)處作一次比較。最后，在根結(jié)點(diǎn)處比較的勝者為下一個(gè)最小數(shù)。因?yàn)橛衝個(gè)葉子的這個(gè)二叉樹的高度是lgn，所以這條路最長(zhǎng)為lgn。因此，找下一個(gè)最小的數(shù)最多只需lgn-1=O(lgn)次比較。假設(shè)要排序的n個(gè)數(shù)放在數(shù)組A[1..n]中。我們用數(shù)組W[1..2n-1]來代表錦標(biāo)賽樹的結(jié)點(diǎn)，做法和堆完全一樣。一開始，這n個(gè)被排數(shù)放在從W[n]到W[2n-1]之中而W[1..n-1]為空。然后從W[n-1]開始到W[1]為止，在每一個(gè)內(nèi)結(jié)點(diǎn)處做比較以求得最小數(shù)。我們用數(shù)組W[1..n-1]記錄各次比較的勝者。排好序的n個(gè)數(shù)輸出在數(shù)組C[1..n]中。在結(jié)點(diǎn)W[i]，1in-1，比較的兩個(gè)數(shù)分別從它兩個(gè)子結(jié)點(diǎn)的勝者，即