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

PAGE5第5章 中位數(shù)和任一順序數(shù)的選擇用分治法設(shè)計(jì)一個(gè)算法同時(shí)找出數(shù)組A[1..n]中的最大和最小的數(shù)，并分析所需的比較次數(shù)。解： 以下的分治算法是作用在數(shù)組A[p,r]上的(p≤r)。在調(diào)用該算法時(shí)，只須置p=1，r=n即可。Max-Min(A[p..r],Max,Min)ifp=r then Max?A[p] Min?A[p] else q??(p+r)/2? Max-Min(A[p..q],Max1,Min1) Max-Min(A[q+1,r],Max2,Min2) Max=max{Max1,Max2} Min=min{Min1,Min2}endifEnd我們用T(n)表示數(shù)組中數(shù)的比較次數(shù)，則有以下遞推關(guān)系：T(n)=T(?n/2?)+T(én/2ù)+2T(1)=0對(duì)任意的n，我們可用歸納法證明T(n)=2n–2。歸納基礎(chǔ)：因?yàn)門(1)=0和T(2)=2，所以T(n)=2n–2在n=1或n=2時(shí)正確。歸納步驟：假設(shè)當(dāng)n=1，2，…，k-1(k3)時(shí)，有T(n)=2n–2。當(dāng)n=k時(shí)，由遞推關(guān)系和歸納假設(shè)有以下推導(dǎo)：T(n)=T(?n/2?)+T(én/2ù)+2=2?n/2?-2+2én/2ù-2+2=2(?n/2?+én/2ù)-2=2n–2。歸納成功。證明任一基于比較的排序算法在最好情況下至少需要(n-1)次比較才能把一個(gè)n個(gè)數(shù)字的序列排好。我們假定這n個(gè)數(shù)字中可以有相等的數(shù)字，但必須通過比較才能確定兩數(shù)是否相等。證明1: 如果n個(gè)數(shù)字的序列被排好序的話，那么序列中任一順序數(shù)便被確定。所以，如果有一個(gè)基于比較的排序算法能在最好情況下用少于(n-1)次比較把一個(gè)n個(gè)數(shù)字的序列排好的話，我們就可以在最好情況下用少于(n-1)次比較把最大數(shù)找到。這與定理5.2矛盾。證明2: 我們用反證法證。假設(shè)有這么個(gè)算法，它用少于(n-1)次比較把某個(gè)n個(gè)數(shù)字的序列排好。我們用一個(gè)圖來描述這個(gè)排序過程。這個(gè)圖有n個(gè)頂點(diǎn)，分別代表這n個(gè)數(shù)。如果算法在兩個(gè)數(shù)之間作一比較，我們則在代表這兩個(gè)數(shù)的頂點(diǎn)之間畫一條邊。顯然，這個(gè)圖的邊數(shù)少于(n-1)，因此是個(gè)不連通的圖。它含有幾個(gè)連通分支。那么，這個(gè)排序算法不可能正確。這是因?yàn)?，如果我們把不含最大?shù)的一個(gè)連通分支中數(shù)字都加上一個(gè)很大數(shù)，然后讓算法去排序的話，那么算法不會(huì)察覺到這個(gè)變動(dòng)。因此，每次進(jìn)行的比較結(jié)果與對(duì)原序列進(jìn)行的比較結(jié)果完全一樣。這樣，算法對(duì)修改后的序列不可能正確排序。所以，任一基于比較的排序算法在最好情況下至少需要(n-1)次比較才能把一個(gè)n個(gè)數(shù)字的序列排好。根據(jù)5.4.3節(jié)的討論，在n個(gè)數(shù)字中同時(shí)找出最大和第2大的數(shù)字需要的比較次數(shù)不超過n+lgn-2。請(qǐng)給出一個(gè)簡(jiǎn)單例子說明。解：下面的錦標(biāo)賽圖標(biāo)明了在找最大數(shù)時(shí)各結(jié)點(diǎn)上比較的勝者。顯然，第一輪總共進(jìn)行了4次比較后找到最大數(shù)9。當(dāng)最大數(shù)9被找到后，第2輪找第2大數(shù)可從9到根的路徑上找到。它一定是存在于在這路徑上第一輪比較的敗者中，即數(shù)字7，2，6中找到。所以這一輪需要2次比較。注意，在第二輪中，9變成了-，所以在結(jié)點(diǎn)X處，7不需比較而取勝。所以總共需要n+lgn-2=5+lg5-2=6次比較。6629759996X假設(shè)我們要從有n個(gè)不同的數(shù)字的集合A[1..n]中找出1000個(gè)與A[1..n]的中位數(shù)距離最近的數(shù)。我們假定這1000個(gè)數(shù)中包括中位數(shù)本身，并假設(shè)n>>1000。兩個(gè)數(shù)x和y之間的距離定義為它們差的絕對(duì)值|x–y|。請(qǐng)?jiān)O(shè)計(jì)一個(gè)快速而方便的O(n)算法。解：算法的偽碼如下，其正確性從注解可知。Numbers-closest-to-median(A[1..n],1000) x?Select(A[1..n],n,n/2) //先找出中位數(shù)xfori1ton B[i]|A[i]–x|endforBuild-Max-Heap(B[1..1000],1) //用B[i]中頭1000個(gè)數(shù)建堆。fori?1001ton ifB[i]<B[1] then B[1]?B[i] Max-Heapify(B[1..1000],1) endifendforforj?1to1000 ifB[j]=|A[i]–x| thenC[j]A[i] endforreturnC[1..1000]End算法的復(fù)雜度為O(n)。這是因?yàn)榈谝徊叫枰狾(n)時(shí)間，2–4行的循環(huán)需要O(n)時(shí)間，第5行需要O(1)時(shí)間，6–11行的循環(huán)需要(n–1000)次，而每次只需O(1)時(shí)間，第12行的循環(huán)需要O(1)時(shí)間。所以，總的時(shí)間復(fù)雜度是O(n)。假設(shè)我們要從有n個(gè)不同的數(shù)字的集合A[1..n]中找出k個(gè)與A[1..n]的中位數(shù)最近的數(shù)。我們假定這k個(gè)數(shù)中包括中位數(shù)本身，并假設(shè)n>k>>1000。兩個(gè)數(shù)x和y之間的距離定義為它們差的絕對(duì)值|x–y|。請(qǐng)?jiān)O(shè)計(jì)一個(gè)快速而方便的O(n)算法。解：這道題不能用上一題的方法，這是因?yàn)閗不是一個(gè)常數(shù)，用下面算法。k-numbers-closest-to-median(A[1..n],k) x?Select(A[1..n],n,n/2) //先找出中位數(shù)xfori=1ton B[i]?|A[i]–x|endfory?Select(B[1..n],n,k) //調(diào)用書中選擇第k順序數(shù)算法C?fori?1ton ifB[i]≤y then C?Cè{A[i]} endifendforif|C|=k+1 //有可能兩個(gè)數(shù)到x的距離等于y。 then lety=B[j] C=C–{A[j]}endifreturnCEnd算法的復(fù)雜度為O(n)。這是因?yàn)樗惴ǖ牡?-5行需O(n)時(shí)間，第6-11行的循環(huán)有O(n)次而每次只需O(1)時(shí)間。所以，總的時(shí)間復(fù)雜度是O(n)。假設(shè)在一個(gè)東西向的街道上有n個(gè)住戶。它們距離西頭的距離分別是H[i](米)(1￡i￡n)。我們假定這些距離是不相等的，并且沒有從小到大排好序的?，F(xiàn)在要在這個(gè)街上設(shè)一個(gè)郵局使得它到這些住戶的平均距離最小。也就是說，要算出這個(gè)郵局到街西頭的距離x使1≤i≤n|Hi-x|最小。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)解： Post-Office(H[1..n],x)x?Select(H[1..n],n,n/2) //郵局位置就是在中位數(shù)x的地方returnxEnd這個(gè)算法顯然是個(gè)O(n)算法?？烧J(rèn)為郵局建在住戶x的街對(duì)面?，F(xiàn)在證明其正確性。假設(shè)我們把H[1..n]排序后的序列存入數(shù)組A并有A[1]<A[2]<…<A[n]。我們先看一下n為偶數(shù)的情況，假定n=2k。顯然，只要郵局的位置x在A[1]和A[n]之間，都有|A[1]–x|+|A[n]–x|=A[n]–A[1]。不然的話，|A[1]–x|+|A[n]–x|>A[n]–A[1]。所以，如取x在A[1]和A[n]之間(包括A[1]和A[n])，則可保證A[1]和A[n]到郵局的距離和最小。容易看出，對(duì)任何i(1ik)，只要郵局設(shè)在A[i]和A[n+1-i]之間，則可保證A[i]和A[n+1-i]到郵局的距離和最小。所以，如果我們?nèi)在A[k]和A[k+1]之間(包括A[k]和A[k+1])，則可保證1≤i≤n|Hi-x|最小。因?yàn)樗惴ㄈ≈祒=A[k]，現(xiàn)在考慮當(dāng)n為奇數(shù)時(shí)的情況，設(shè)n=2k+1，n/2=k+1。如取x=A[k+1]，那么，如上面所討論，x到除中位數(shù)A[k+1]外其余2k個(gè)點(diǎn)的距離和最小。又因?yàn)閨x-A[k+1]|=0，所以，當(dāng)x=A[k+1]時(shí)，1≤i≤n|HiX[1..n]和Y[1..n]各含排好序的n個(gè)數(shù)字。請(qǐng)?jiān)O(shè)計(jì)一個(gè)復(fù)雜度為O(lgn)的算法找出在數(shù)組X和Y中所有2n個(gè)數(shù)的中位數(shù)。我們假定這2n個(gè)數(shù)都不相等。(提示：如果X[k]是中位數(shù)，它應(yīng)該在Y中什么位置？)解：因?yàn)橹形粩?shù)必需大于n-1個(gè)數(shù)，所以，如果X[k]是中位數(shù)，那么它大于X中k-1個(gè)數(shù)，X[1..k-1]，所以它應(yīng)滿足以下充要條件：Y[n-k]<X[k]<Y[n-k+1]。 （1） 如果不滿足上面關(guān)系，那么X[k]不是中位數(shù)，此時(shí)有兩種情況：X[k]<Y[n-k]。這時(shí)，對(duì)任何j≤k，因X[j]X[k]，X[j]不可能是中位數(shù)。Y[n-k+1]<X[k]。這時(shí)，對(duì)任何k≤j,X[j]不可能是中位數(shù)。根據(jù)這個(gè)觀察，我們可以用二元搜索的方法確定是否X數(shù)組中有中位數(shù)。我們先考察X[(n+1)2]，根據(jù)(1)式，二次比較即可確定X[(n+1)2]是否是中位數(shù)。如果不是，根據(jù)情形是(a)還是(b)，可把搜索范圍縮小一半。這樣，在O(lgn)時(shí)間內(nèi)，可確定X數(shù)組中是否有中位數(shù)。如果沒有，我們?cè)贆z查數(shù)組Y。再用O(lgn)時(shí)間即可找到中位數(shù)。下面是算法的偽碼。Median(X[1..n],Y[1..n],median) //主程序Search(X[1..n],Y[1..n],mx,search) //Search是子程序，其偽碼在后面ifsearch=true then median?mx else Search(Y[1..n],X[1..n],my,search) median?myendifEndSearch(A[a..b],B[1..n],m,search)//這個(gè)子程序檢查數(shù)組A[a..b]中是否有A[1..n]和B[1..n]的中位數(shù)。這里A和B各含排好序的n個(gè)數(shù)字。并且這2n個(gè)數(shù)字都不相等。search?falseifab //如果a>b那么程序不做任何事，search=false k??(a+b)/2? ifA[k]<B[n-k] thenSearch(A[k+1..b],B[1..n],m,search) elseifA[k]>B[n-k+1] thenSearch(A[a..k-1],B[1..n],m,search) else m?A[k] search?true endif endifendifEnd*完成對(duì)5.3.2節(jié)中快選擇算法Quick-Select(A[1..n],n,i)的平均復(fù)雜度的分析。解： 我們證明其平均情況復(fù)雜度為O(n)。我們要考慮各種劃分的結(jié)果，取平均值。為簡(jiǎn)化證明，我們假設(shè)每次劃分后，下一步都取最壞情況，即下一步的搜索都是在較大的子集中進(jìn)行，并且遞歸到最后一個(gè)數(shù)時(shí)才結(jié)束。如果這種情況下得到的平均復(fù)雜度是O(n)的話，那么實(shí)際的平均復(fù)雜度也必為O(n)。假設(shè)在第一次劃分之后，A[1..q-1]中含有k個(gè)元素(k=q-1)，這里k可能為0，1，2，…，(n-1)。我們假定這n種情況機(jī)會(huì)均等，都有1/n的概率發(fā)生。那么，A[q+1..n]就含有(n-1–k)個(gè)元素。當(dāng)k≤(n-1–k)(即k≤n-12時(shí))，下一層遞歸在A[q+1..n]中進(jìn)行，否則在A[1..q-1]中進(jìn)行。假設(shè)T(n)是算法需要的比較次數(shù)，T(1)=0T(n)≤1n[k=0(n-1)/2T(n-1-k)+k==1n[k=n-1(n-1)/2T(k)]+k=(n-1)/2≤2nk=(n-1)/2n-1T(k)+(n–1) 下面我們用歸納法證明(1)式的解T(n)滿足T(n)cn，這里c是一個(gè)大于4的正數(shù)。歸納基礎(chǔ)：當(dāng)n≤3時(shí)，這樣的正數(shù)顯然存在。歸納步驟：假定當(dāng)n≤k-1時(shí)(k>3)，T(n)cn成立。我們證明當(dāng)n=k時(shí)，T(n)cn也成立。從(1)式，我們有如下推導(dǎo)：T(n)≤2nk=(n-1)/2≤2nk=(n-1)/2n-1ck+(n–1) (由歸納假設(shè)T(k=2n(k=1n-1ck-k=1=2cn(n(n-1)2-(n-1)/2(≤2cn(n(n-1)2-((n-1)/2)((n-1)/2-1)2≤cn[n(n-1)-(n–1)(n–3)/4]+(n=cn–c-c4n()+(n–1)=cn–c-cn4+c-3c4n+(≤cn–cn4+n ≤cn (因?yàn)閏大于等于4)歸納成功。所以T(n)=O(n)。因?yàn)閚-1次比較是必需的，我們有T(n)=Q(n)。 假設(shè)在X-Y坐標(biāo)平面上有n個(gè)點(diǎn)，a1=(x1,y1)，a2=(x2,y2)，…，an=(xn,yn)。兩點(diǎn)ai=(xi,yi)和aj=(xj,yj)間的曼哈頓距離（Manhattandistance）定義為：d(ai,aj)=|xi–xj|+|yi–yj|。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)的算法找出一個(gè)中心點(diǎn)z=(x,y)使得這n個(gè)點(diǎn)到點(diǎn)z的平均曼哈頓距離最小。解：這n個(gè)點(diǎn)到點(diǎn)z的平均曼哈頓距離最小，也就是總距離D最小，這里D=k=1nd(ak,z)=k=1 顯然，總距離D最小當(dāng)且僅當(dāng)k=1n|xk–x|最小和k=1n|ykManhattan-center(X[1..n],Y[1..n],x,y)x?Select(X[1..n],n,n/2)y?Select(Y[1..n],n,n/2)returnz=(x,y)End*證明，在最壞情況時(shí)，同時(shí)找出數(shù)組A[1..n]中的最大和最小的數(shù)的算法需要至少2n-2-n/2次比較。本題的結(jié)果證明，第5.2.2節(jié)中的算法是最優(yōu)的。(提示：考慮兩個(gè)集合，L和S，L是可能是最大數(shù)的數(shù)字集合，S是可能是最小數(shù)的數(shù)字集合。一開始，L=S=A[1..n]。對(duì)于任何算法，我們可以如下跟蹤這個(gè)算法：算法做一次比較以后，記下兩個(gè)集合的變化(它們會(huì)減小)。當(dāng)L和S減小到各自只含一個(gè)數(shù)時(shí)，算法才能結(jié)束。例如，L=S={6,3,9,1,12}。比較3和9后，L={6,9,1,12}，S={6,3,1,12}。再比較L中6和9后，L={9,1,12}，S={6,3,1,12}。算一下，至少要多少次比較L和S才會(huì)減小到各自只含一個(gè)數(shù)。)解： 因?yàn)槭亲顗那闆r，我們可假定這n個(gè)數(shù)都不相同。我們考慮兩個(gè)集合，L和S，L是可能是最大數(shù)的數(shù)字集合，S是可能是最小數(shù)的數(shù)字集合。一開始，L=S=A[1..n]。對(duì)于任何算法，我們可以如下跟蹤這個(gè)算法：算法比較一次以后，記下兩個(gè)集合的變化（它們會(huì)減?。?。當(dāng)L和S減小到各自只含一個(gè)數(shù)時(shí)，算法才能結(jié)束。假設(shè)比較兩個(gè)數(shù)a和b的結(jié)果是a<b，那么a可以從集合L中刪去，b可以從集合S中刪去。如果a不在集合L中，那只能刪去b。如果b不在集合S中，那只能刪去a。如果a不在集合L中，而且b不在集合S中，那么a和b都不能刪除，這個(gè)比較算白做了。但是，有一點(diǎn)是清楚的，就是一個(gè)數(shù)參加比較后，它只能出現(xiàn)在最多一個(gè)集合中。下面我們考慮最壞情況。當(dāng)算法比較兩個(gè)數(shù)a和b時(shí)，我們分析如下：如果a和b都還沒有被比較過，它們都出現(xiàn)在集合L和S中。如果a<b，那么a可從L中刪去，b可從S中刪去，一共可刪去兩個(gè)數(shù)。a被比較過，并且aS，但是b沒有被比較過。所以，b出現(xiàn)在L和S中。最壞情況是a<b，那么b可從S中刪去，a不可從S中刪去。這種情況可刪去一個(gè)數(shù)。(對(duì)稱情況是b被比較過，bS，b<a，那么a可從S中刪去，b不可從S中刪去。)a被比較過，并且aL，但是b沒有被比較過。最壞情況是a>b，那么b從L中刪去，a不可從L中刪去。這種情況可刪去一個(gè)數(shù)。(對(duì)稱情況是b被比較過，b>a，那么a可從L中刪去，b不可從L中刪去。)如果a和b都被比較過，并且同屬于L，則a<b時(shí)刪去a，a>b時(shí)刪去b。如果a和b都被比較過，并且同屬于S，則a<b時(shí)刪去b，a>b時(shí)刪去a。如果a和b都被比較過，并且aS，bL。那么如果a<b，沒有數(shù)可以刪去。如果a和b都被比較過，并且aS，bL。最壞情況可以使a>b不會(huì)出現(xiàn)。這是因?yàn)椋诔霈F(xiàn)a>b這種情況前，任何一個(gè)S中數(shù)a與任何一個(gè)L中數(shù)b的比較都是a<b。一旦出現(xiàn)a>b的情況，我們可以把L中每一個(gè)數(shù)都加上一個(gè)很大的數(shù)使得a<b。顯然，這個(gè)變化不會(huì)改變?nèi)魏我呀?jīng)比較的結(jié)果。因?yàn)槲覀兗俣ㄊ亲顗那闆r，我們可以這樣做，所以可假設(shè)a>b情況不會(huì)出現(xiàn)。那么，這個(gè)比較不能刪去任何數(shù)字。由以上分析可知，除第一種情況外，每次比較可讓我們最多刪去一個(gè)數(shù)。因?yàn)榈谝环N情況要求a和b都沒有被比較過，所以最多可以有n/2個(gè)比較是第一種情況。假設(shè)算法一共進(jìn)行了k次第一種情況的比較和m次其它請(qǐng)況的比較，總共是m+k次比較。因?yàn)槲覀冃枰獜募螸和S總共刪除2n-2個(gè)數(shù)字，所以有關(guān)系m+2k2n-2。因此有m+k2n-2-k2n-2-n/2。更詳細(xì)一點(diǎn)，如果n是偶數(shù)，m+k2n-2-n/2=3n-42。否則m+k2n-2-n/2=2n-2-(n-1)/2=3n-32 這個(gè)結(jié)果證明5.2.2節(jié)的算法是最優(yōu)的。下面是一個(gè)同時(shí)找出數(shù)組A[1..n]中的最大數(shù)和最小數(shù)的基于分治法的算法。算法是作用在數(shù)組A[p,r]上的(p≤r)。在調(diào)用該算法時(shí)，只須置p=1，r=n即可。它的正確性顯然。請(qǐng)證明，當(dāng)n2時(shí)，該算法最多需要2n–2–n/3次比較。D&C-Max-Min(A[p..r],max,min)ifr=p then max?min?A[p] return else ifr=p+1 then ifA[p]A[r] then max?A[r] min?A[p] else max?A[p] min?A[r] endif endif returnendif //以上是有一個(gè)數(shù)或兩個(gè)數(shù)時(shí)的情況，也就是底的情況q??(p+r)/2?D&C-Max-Min(A[p..q],max1,min1)D&C-Max-Min(A[q+1,r],max2,min2)maxmax{max1,max2}minmin{min1,min2}End證明：我們用T(n)表示數(shù)組中數(shù)的比較次數(shù)，則有以下遞推關(guān)系：T(n)=T(?n/2?)+T(én/2ù)+2T(1)=0T(2)=1我們用歸納法證明，當(dāng)n2時(shí)，T(n)2n–2-n/3。歸納基礎(chǔ)：因?yàn)門(2)=1，所以T(n)2n–2-n/3ù在n=2時(shí)正確。 又因?yàn)門(3)=T(2)+T(1)+2=1+0+2=3，所以T(n)2n–2-n/3ù在n=3時(shí)也正確歸納步驟：假設(shè)當(dāng)n=2，3，…，k-1(k4)時(shí)，有T(n)2n–2-én/3ù。我們證明，當(dāng)n=k時(shí)，仍然有T(n)2n–2-én/3ù。因?yàn)楱/2ù=ék/2ùk-1，由歸納假設(shè)有：T(én/2ù)2én/2ù–2-één/2ù/3ù，和T(?n/2?)2?n/2?–2-é?n/2?/3ù。由遞推關(guān)系，我們有以下推導(dǎo)：T(n)=T(?n/2?)+T(én/2ù)+2(2én/2ù–2-één/2ù/3ù)+(2?n/2?–2-é?n/2?/3ù)+2=2n–2–(één/2ù/3ù+é?n/2?/3ù)。 (1) 下面我們證明(één/2ù/3ù+é?n/2?/3ù)én/3ù。我們分6種情況。n=6h。我們有：één/2ù/3ù+é?n/2?/3ù=h+h=2hén/3ù。n=6h+1。我們有：één/2ù/3ù+é?n/2?/3ù=é(3h+1)/3ù+é3h/3ù=(h+1)+h=2h+1én/3ù。n=6h+2。我們有：één/2ù/3ù+é?n/2?/3ù=é(3h+1)/3ù+é(3h+1)/3ù=(h+1)+(h+1)=2h+2>én/3ù。n=6h+3。我們有：één/2ù/3ù+é?n/2?/3ù=é(3h+2)/3ù+é(3h+1)/3ù=(h+1)+(h+1)=2h+2>én/3ù。n=6h+4。我們有：één/2ù/3ù+é?n/2?/3ù=é(3h+2)/3ù+é(3h+2)/3ù=(h+1)+(h+1)=2h+2én/3ù。n=6h+5。我們有：één/2ù/3ù+é?n/2?/3ù=é(3h+3)/3ù+é(3h+2)/3ù=(h+1)+(h+1)=2h+2én/3ù。因?yàn)樗星闆r下都有(één/2ù/3ù+é?n/2?/3ù)én/3ù，由(1)式，我們得到：T(n)=T(?n/2?)+T(én/2ù)+2=2n–2–(één/2ù/3ù+é?n/2?/3ù)2n–2–én/3ù。歸納成功。設(shè)計(jì)一個(gè)同時(shí)找出數(shù)組A[1..n]中的最大數(shù)和最小數(shù)的基于分治法的算法，使得該算法最多需要2n–2–n/2次比較。解： Divide-Conquer-Max-Min(