计算机算法基础 第2版 习题及答案 第2章

PAGE19第2章 分治法用分治法设计一个算法找出数组A[1..n]中的最大的数，并分析所需的比较次数。解：以下用分治法的算法是作用在数组A[p,r]上的，p≤r。在调用该算法时，只须置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)表示数组中数字间的比较次数，则有以下递推关系：T(n)=T(n/2)+T(n/2)+1T(1)=0我们用归纳法证明T(n)=n–1。归纳基础：因为T(1)=0，所以T(n)=n–1显然在n=1时正确。归纳步骤：由递推关系和归纳假设我们有以下推导：T(n)=T(n/2)+T(n/2)+1=(n/2-1)+(n/2-1)+1=n/2+n/2-1=n–1。归纳成功。用分治法设计一个算法同时找出数组A[1..n]中的最大和第二大的数，n2，并分析所需的比较次数。解：以下分治法的算法是作用在数组A[p,r]上的,p≤r。在调用该算法时，只须置p=1，r=n即可。Largest-and-second-largest(A[p..r],L,S)//L和S分别为最大和第二大的数ifp=rthenL¬A[p] S¬- //表示没有第二大数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)表示数组中数的比较次数，则有以下递推关系：T(n)=T(ën/2û)+T(én/2ù)+2 T(1)=0它的解可用主方法得到。令n=2k，则有T(n)=2T(n/2)+2=Q(n)。如果想知道更为准确的常数因子，我们可用归纳法证明T(n)=2n–2。归纳基础：因为T(1)=0所以T(n)=2n–2显然在n=1时正确。归纳步骤：由递推关系和归纳假设有以下推导：T(n)=T(ën/2û)+T(én/2ù)+2=(2ën/2û-2)+(2én/2ù-2)+2=(2n-4)+2=2n–2。归纳成功。假设GOOGLE公司在过去n天中的股票价格记录在数组A[1..n]中。我们希望从中找出两天的价格，其价格的增幅最大。也就是说，我们希望找到A[i]和A[j]，i<j，使得M=A[j]–A[i]的值最大，即M=max{A[j]–A[i]|1i<jn}。试设计一个复杂度为O(nlgn)或更好的分治算法。解：以下算法找出数组A[p..r]中序号i和j使得M=A[j]–A[i]的值最大，pi<jr。Divide-Conquer-Max-profit(p,r,m,i,j)//假设r³pifp=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]ifmc³max{ml,mr} thenm¬mc i¬x j¬y elseifml³mr thenm¬ml i¬il j¬jl elsem¬mr i¬ir j¬jr endifendifEnd调用Divide-Conquer-Max-profit(1,n,m,i,j)后即可找到对数组A[1..n]的解。上面算法的复杂度可由下面递推关系求出：T(n)=T(ën/2û)+T(én/2ù)+Q(n)=Q(nlgn)。稍加修改后，我们可以得到O(n)复杂度的分治术算法。我们留给读者思考。设A和B是两个nn矩阵。众所周知，计算乘积C=AB通常需要(n3)次乘法和加法。基於分治术的Strassen算法可以改进这个复杂度。下面是这个算法。为简化起见，我们假设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;输出结果如下。C=AB=C11请分析Strassen算法的复杂度。你不必证明其正确性。解: 将A和B各自划分为4个n/2´n/2的矩阵后，第2步和第3步递归地进行7次n/2´n/2矩阵之间的乘法和18次n/2´n/2矩阵间的加法。所以，我们可以有以下的递推关系：T(n)=7T(n/2)+18n2它的解是T(n)=Q()=Q()。如果我们只考虑乘法次数，那么其递推关系是T(n)=7T(n/2)，它的解仍是T(n)=Q()=Q()。证明式（2.1）满足T(n)=T(ën/2û)+1lg(n+1)。证明：我们用归纳法证明。归纳基础：当n=0时，式（2.1）给出T(0)=0。因为lg(0+1)=0，命题T(n)lg(n+1)正确。当n=1时，T(1)=T(0)+1=1。因为lg(1+1)=1，命题T(n)lg(n+1)也正确。归纳步骤：假设当n=0，1，2，…，k-1（k2）时我们有T(n)lg(n+1)。我们证明当n=k时也有T(n)lg(n+1)。由递推关系，我们有T(k)=T(ëk/2û)+1。因为k2，有ëk/2ûk-1。从归纳假设，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是一个奇数，我们有：T(k)lg(2ëk/2û+2)=lg(2(k-1)/2û+2)=lg(k+1)。 如果k是一个偶数，我们有：T(k)lg(2ëk/2û+2)。=lg(k+2)=lg(k+1)。（因为k+1是奇数，向上取整后，两者相等。）归纳成功。用替換法获得以下递推关系的一个渐近上界。(a) T(n)=T(n/2)+2T(n/4)解: 我们归纳证明，存在一个正数c使得T(n)≤cn。归纳基础：显然我们可以找到正数c，使得在n=1，2，3，4时，T(n)≤cn。归纳步骤：假设存在正数c，当n=1，2，3，4，5，…，k-1（k5）时我们有T(n)£cn。我们证明当n=k时也有T(n)£cn。因为当n5时有n/2<n，n/4<n，由归纳假设有T(n/2)£cn/2和T(n/4)cn/4。把这两个关系代入到原递归关系中，得到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解：我们归纳证明，存在一个正数c使得在n≥1时有T(n)£c(n-10)lg(n–10)。归纳基础：这样的正数c在n20时显然可以找到，使得T(n)£c(n-10)lg(n–10)。归纳步骤：设存在正数c，当n=1，2，…，k-1（k21）时我们有T(n)£c(n-10)lg(n–10)。我们证明当n=k时也有T(n)£c(n-10)lg(n–10)。我们可设c>10。首先，因为k-1≥20，ën/2û10。所以ën/2û+5ën/2û+ën/2û-1k-1。由归纳假设有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)。把这个关系代到原递推关系中，得到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)。证明以下递推关系有T(n)=O(2n)

:(a) T(n)=nT(n/2)+nT(1)=1。解：我们用归纳法证明，存在正数c>0使得当n1时有T(n)c2n。归纳基础：我们可假定当n≤5时，存在正数c>1使得T(n)c2n。归纳步骤：假定当n=1，2，…，k-1(k6)时，T(n)c2n。我们证明当n=k时仍有T(n)c2n。由归纳假设，我们有T(n/2)c2n/2。因此，由递推关系，我们可得：T(n)=nT(n/2)+ncn2n/2+n 很容易观察到，当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。解：我们用归纳法证明，存在正数c>0使得当n1时有T(n)c2n。归纳基础：当n=1和n=2时，取c=5，显然有T(n)<52n。归纳步骤：假定当n=1，2，…，k-1时，我们有T(n)52n。我们证明当n=k时仍有T(n)52n。由归纳假设，我们有T(n-1)52n-1和T(n-2)52n-2。因此，由递推关系，我们可得：T(n)=T(n-1)+T(n-2)+n252n-1+52n-2+n2 因为当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。解：我们用归纳法证明存在正数c>0使得当n1时有T(n)c2n。归纳基础：我们可假定当n≤30时，存在正数c>1使得T(n)c2n。归纳步骤：假定当n=1，2，…，k-1(k31)时，存在正数c>1使得T(n)c2n。我们证明当n=k时仍有T(n)c2n。由归纳假设，我们有T(n/2)c2n/2，因此，由递推关系，我们可得：T(n)=5n2T(n/2)+n35n2c2n/2+n3。因为当n>30时，显然有n32n/2–1，所以，当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)

。用序列求和法解以下递推关系。(a) T(n)=4T(n/2)+n2lgn解：设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解：设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)。用主方法解以下递推关系。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)。解递推关系T(n)=2T(n)+lgn。解：令n=2k，得到T(2k)=2T(2k/2)+k。定义W(k)=T(2k)，我们有如下推导：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是任一个固定的正整数。证明： 因为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假设我们开一部卡车从城市A到城市B，中间一共经过n个苹果市场，包括城市A和城市B的苹果市场，并且编号为1到n。在市场i，1≤i≤n，从顾客的观点看，其每市斤的买入价B[i]和卖出价S[i]都已知，单位是元。下图给出了一个n=6的例子。现在我们计划找一个市场i买苹果，然后再找一个市场ji把苹果卖掉使得赚的钱最多(如果根本赚不到钱，则使亏损越小越好)。我们假设卡车不可以向回开，并且只做一次买卖。例如，在上面的例子中，最好的方案是在市场4买苹果而在市场6卖出去，这样做每斤可赚7-2=5元钱。请设计一个分治算法找出市场i和j使得利润最大或亏损最小，并分析算法复杂度。解：我们设计一个在市场p到市场r之间进行买卖的最佳解，1prn,然后调用这个算法时置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)上面的算法对应的递推关系是T(n)=T(n/2)+T(n/2)+(n)=(nlgn)。注：上面的算法可改进为O(n)，我们略去讨论。假设n个学生S[i]的身高height[i]不同,1≤i≤n，并且已排序为height[1]<height[2]<…<height[n]。另外，他们的性别对应地记录在数组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]可组成一对合格的舞伴。请用分治法设计一个复杂度为O(n)的算法来计算在这n个学生中有多少个不同的合格的配对方案。解：我们用分治法为学生序列S[p..r]设计一个计算配对方案个数的算法，然后调用这个算法时置p=1和r=n即可。这个算法在计算配对方案个数(number-pairs)时，同时算出S[p..r]中有多少个女生和多少个男生。Dancing-pairs(p,r,number-pairs,number-F,number-M) //假设rpifp=r then number-pairs0 //只有一个学生 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算法的复杂度为T(n)=T(n/2)+T(n)+(1)=(n)。给定序列A[1],A[2],…,A[n],请用分治法设计一个复杂度为O(nlgn)的算法来找出其中最长一段递增(不减)序列段，即找出两个序号ij,使得A[i]A[i+1]A[i+2]…A[j],并使j-i+1最大。解：我们用分治法为序列A[p..r],p<r,设计一个复杂度为O(nlgn)的算法来找出其中最长递增序列段，然后调用这个算法时置p=1和r=n即可。Longest-increasing-segment(A[],p,r,d,i,j)//假设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该算法的复杂度为T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。在一条东西方向的大街上有n个人家，它们与西头的距离顺序为H[1]<H[2]<…<H[n]。另外，街上有m个学校，m<n,它们与西头的距离顺序为S[1]<S[2]<…<S[m]。假设每家都有学生，并且步行到最近的学校上学。假设某家与西头的距离是x,请用分治法设计一个复杂度为O(lgm)的算法来确定这家的学生应该去哪所学校和步行的距离有多远。请用Nearest-school(S[1..m],k,d,x)作为你的算法的名字。其中，k表示S[k]是要去的学校，d表示从x到S[k]的距离。下面是一个利用(a)中的算法而设计的分治法算法。它确定这n家中哪家学生步行的距离最远，有多远，和去哪所学校。调用这个算法时置i=1和j=n即可。请证明这个算法的复杂度是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) //调用(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调用Longest-Distance(H[1..n],S[1..m],u,h,dist)后，我们得到从家h到学校u的距离最远，该距离为dist。解：(a) 我们考虑学校序列为S[p..r]，算法如下。然后调用这个算法时置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调用Nearest-school(S[1..m],k,d,x)后，我们得到与x最近的S[k],1km,其距离为d。时间复杂度为T(m)T(m/2)+O(1)=O(lgm).(b)根据算法，我们可得递推关系时间复杂度为T(n)=T(n/2)+T(n/2)+O(1),T(1)=O(lgm)。用求和法，设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个学校，1m<n,它们与西头的距离顺序为S[1]<S[2]<…<S[m]。另外，假设人家H(k),1kn,有U(k)个学生，并且步行到最近的学校上学。为确定起见，如果家两边的学校等距离，学生选西边的学校。请用分治法设计一个复杂度为O(nlgm)的算法来确定哪个学校会接收最多的学生。解：我们假设住家序列为H[u..v]，学校序列为S[i..j]，用分治法来确定哪个学校会接收最多的学生。然后，调用这个算法时，置u=1,v=n,i=1,j=m即可。Serve-most-students(S[i..j],H[u..v],k,p) //学校S[k]会接收最多的学生，人数为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调用Serve-most-students(S[1..m],H[1..n],k,p)即可得到答案。算法复杂度可由如下递归关系求得：T(n,1)=O(n) T(n,m)=T(n1,m/2)+T(n2,m/2)+cn //c是常数，n1+n2=n。令m=2k，可把递推关系简化为：T(n,m)=T(n1,m/2)+T(n2,m/2)+cn我们对m用归纳法证明，存在常数d>c，使得T(n,m)≤dnlgm+d(n+m)。归纳基础：当m=1时，命题显然成立。归纳基础：当m>1时，我们有以下推导： 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 //由归纳假设=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],请用分治法设计一个复杂度为O(nlgn)的算法来找出其中一段递增(不减)序列段，即找出两个序号ij,使得A[i]A[i+1]A[i+2]…A[j],并使它们的和，k=ij解： 我们用分治法为序列A[p..r]设计一个复杂度为O(nlgn)的算法来找出其中最长递增序列,然后调用这个算法时置p=1和r=n即可。max-value-increasing-segment(A[p..r],d,i,j)//假设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该算法的复杂度为T(n)=(T(n/2)+T(n/2)+(n)=(nlgn)。给定序列A[1],A[2],…,A[n],请用分治法设计一个复杂度为O(nlgn)的算法来找出其中两个序号i<j,使得A[i]A[j],并使它们的和，A[i]+A[j]，最小。如果没有这样两个数，则输出+∞。解: 这是和书中例题2.9对称的题目，伪码如下。 Min-Sum-Two-Numbers(A[p..r],i,j,M) //p≤rifp=r then M+∞ //只有一个数 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当我们调用Max-Sum-Two-Numbers(A[1..n],i,j,M)时，原问题得解。算法复杂度可由下面递推关系得到：T(n)=2T(n)+O(n)=O(nlgn)。在序列A[1],A[2],…,A[n]中，一个数可能出现若干次。如果一个数出现的次数k超过一半，即k>n/2，那么我们说这个序列有一个垄断数。请用分治法设计一个复杂度为O(nlgn)的算法来判断一个给定序列是否有一个垄断数。如果有，报告这个数及其出现次数k，否则报告k=-。我们约定，该算法只能用比较序列中两数字是否相同来判断，比较的结果不报告谁大谁小，只告诉相同或不相同。当比较的两数字不是序列中数字时，可以报告大小。解: 算法的伪码如下，正确性显然。Dominating-number(A[p..r],i,k) //如果有，A[i]出现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]可