第2章 遞歸與分治-作業(yè)答案

MAXA(A,i,j){inti,j,max=0,max1=0,max2=0;

intA[];if(i==j)max=A[i];else//求數(shù)組前半部分的最大值max1 {max1=MAXA(A,i,(i+j)/2);

//求數(shù)組后半部分的最大值max2 max2=MAXA(A,(i+j)/2+1,j); if(max1>max2)max=max1; elsemax=max2; }returnmax;}課后練習練習2：分析如下時間函數(shù)的復雜度，并說明原因。1.利用遞歸樹說明以下時間函數(shù)的復雜度：2.利用主定理說明以下時間函數(shù)的復雜度：T(n)=16T(n/4)+nT(n)=T(3n/7)+1T(n)=3T(n/4)+nlogn練習2：分析如下時間函數(shù)的復雜度，并說明原因。1.利用遞歸樹說明以下時間函數(shù)的復雜度：遞歸樹的高度為：log4n+1;除去葉子結(jié)點，樹有l(wèi)og4n層，每層結(jié)點總數(shù)為：最后一層葉子結(jié)點數(shù)：換底公式2.利用主定理說明以下時間函數(shù)的復雜度：T(n)=16T(n/4)+nT(n)=T(3n/7)+1T(n)=3T(n/4)+nlogn定理（主定理）：a≥1且b>1是常數(shù)，f(n)是一個函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界：（1）若對于某常數(shù)?>0，有f(n)=O(nlogba-?)，則T(n)=(nlogba)；（2）若f(n)=(nlogba)，則T(n)=(nlogbalogn)；（3）若對于某常數(shù)?>0，有f(n)=(nlogba+?

)，且對于某個常數(shù)c<1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=(f(n))。練習3：分析Strassen矩陣乘法在時間效率上有何改進，為什么？Strassen矩陣乘積分治算法中，用了7次對于n/2階矩陣乘積的遞歸調(diào)用和18次n/2階矩陣的加減運算。由此可知，該算法的所需的計算時間T(n)滿足如下的遞歸方程：T(n)=O(nlog7)≈O(n2.81)較大的改進課后練習練習4：劃出下列序列在快速排序過程中一次劃分的具體步驟。21254925*1608一次劃分的過程2108254925*16初始關(guān)鍵字08254925*1608254925*1608254925*1621212108254925*162108254925*1621pivotkey一次交換二次交換三次交換四次交換完成一趟排序lowhighlowhighhighlowlowhighhighlowhighlow課后練習練習5：算法實現(xiàn)題2-8（教材第42頁）集合劃分問題。要求：設(shè)計算法；寫出該算法時間函數(shù)T(n)的遞推關(guān)系式；分析其時間復雜度和空間復雜度。關(guān)于集合劃分問題的分析例如：集合{1,2,3}有五個劃分{{1},{2},{3}}，{{1,2},{3}}，{{1,3},{2}}，{{1},{2,3}}，{{1,2,3}}。算法設(shè)計要求：給定正整數(shù)n和m，計算出n個元素的集合{1,2,.,n}可以劃分為多少個不同的由m個非空子集組成的集合。數(shù)據(jù)輸入：由文件input.txt

提供輸入數(shù)據(jù)。文件的第1行是元素個數(shù)n和非空子集數(shù)m。結(jié)果輸出：程序運行結(jié)束時，將計算出的不同的由m個非空子集組成的集合數(shù)輸出到文件output.txt

中。遞歸公式：設(shè)n個元素的集合可以劃分為F(n,m)個不同的由m個非空子集組成的集合。F(n,m)=1,whenn=0,n=m,n=1,orm=1F(n,m)=0,whenn<m否則F(n,m)=F(n-1,m-1)+m*F(n-1,m)考慮3個元素的集合，可劃分為①1個子集的集合：{{1，2，3}}②2個子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}}③3個子集的集合：{{1}，{2}，{3}}∴F(3,1)=1;F(3,2)=3;F(3,3)=1;如果要求F(4,2)該怎么辦呢？A.往①里添一個元素{4}，得到{{1，2，3}，{4}}B.往②里的任意一個子集添一個4，得到{{1，2，4}，{3}}，{{1，2}，{3，4}}，{{1，3，4}，{2}}，{{1，3}，{2，4}}，{{2，3，4}，{1}}，{{2，3}，{1，4}}∴F(4,2)=F(3,1)+2*F(3,2)＝1+2*3＝7課后練習（選做）練習6：假設(shè)有n個項的數(shù)組A，每個項具有一個不同的數(shù)。告訴你值A(chǔ)[1],A[2],…,A[n]的序列是單峰的：對于某個在1與n之間的下標p，數(shù)組項的值增加到A中的位置p，然后剩下的過程減少直到位置n。要求：利用分治策略設(shè)計一個算法，讀盡可能少的元素，找到這個“頂峰”元素p。分析該算法的時間復雜性。問題分析何為“單峰”？對于某個在1與n之間的下標p，數(shù)組項的值增加到A中的位置p，然后剩下的過程減少直到位置n；即在A[1]到A[n]的n個數(shù)中，只有一個極大值A(chǔ)[p]；A[p]前的元素均小于A[p]，并按升序排列；A[p]后的元素均小于A[p]，并按降序排列。分治法思想查看A[n/2]值，分析其是出現(xiàn)在上坡上（A[n/2]在A[p]之前）還是下坡上（A[n/2]在A[p]之后）。如果A[n/2-1]＜A[n/2]＜A[n/2+1]，那么n/2項一定嚴格位于p的前面，因此可以在n/2+1項到n項之間遞歸地繼續(xù)下去。如果A[n/2-1]＞A[n/2]＞A[n/2+1]，那么n/2項一定嚴格位于p的后面，因此可以在1項到n/2-1項之間遞歸地繼續(xù)下去。如果A[n/2]比A[n/2-1]和A[n/2+1]都大，頂峰項實際上就等于A[n/2]。具體算法：偽代碼int

Danfeng(intA[],intm,intn){//求單峰數(shù)組中的頂峰值

intk=(m+n)/2;

if(k==m&&k==n) returnA[k]; if(A[k-1]<A[k]&&A[k]>A[k+1]) returnA[k]; else { if(A[k-1]<A[k]&&A[k]<A[k+1])

Danfeng(A[],k+1,n); if(A[k-1]>A[k]&&A[k]>A[k+1])

Danfeng(A[],m,k-1); }}時間復雜性分析該算法的時間函數(shù)的遞推式為：該算法的時間復雜度為：O(log2n)課后練習（選做）練習7：假設(shè)你正在為一個小的投資公司咨詢，他們有下面類型的問題想要一次又一次的求解。這個問題的一個典型實例如下所述。他們正在做一項模擬，在這項模擬中他們從過去的某點開始對一只給定的股票連續(xù)看n天。讓我們把這些天記為數(shù)i=1,2,…,n；對每天i，他們有當天這只股票每股的價格p(i)（簡單起見，假設(shè)這個價格在一天之內(nèi)是固定的）。假設(shè)在這個時間區(qū)間內(nèi)，某天他們想買1000股并且在以后的某天賣出所有這些股。他們想知道：為了掙到最多的錢，他們應(yīng)該什么時候買并且什么時候應(yīng)該賣？問題分析、舉例說明利用分治策略設(shè)計一個算法。舉例：假設(shè)n=3,p(1)=9,p(2)=1,p(3)=5.那么應(yīng)該得出“2買，3賣”的結(jié)論。即，在第2天買并且在第3天賣意味著每股將掙4美元，是這個期間最大的收益。問題分析：存在一個簡單的算法，時間復雜度是O(n2)：對所有的買天/賣天構(gòu)成的對進行嘗試，看看哪個對能使用戶掙到最多的錢。假設(shè)在第i天買、第j天賣可以獲得最大收益：最優(yōu)解。怎樣在O(nlog2n)時間找到正確的i和j。一共有n天的數(shù)據(jù)，即p(1),p(2),……,p(i),p(i+1),……,p(n-1),p(n)。設(shè)S是1天，……，n/2天的集合；S’是n/2+1，……，n天的集合。分治法策略：或者有一個最優(yōu)解使投資者在n/2結(jié)束時持有這只股票：第i天買入股票，此時i≤n/2；第j天賣出股票，此時j≥n/2+1。或者沒有：最優(yōu)解在集合S中（i與j均≤n/2）：用戶可以在前n/2天內(nèi)買入股票并賣出；或者最優(yōu)解在集合S’中（i與j均≥n/2+1）：用戶可以在后n/2天內(nèi)買入股票并賣出。則算法是在下面三個可能的解中最好的：S上的最優(yōu)解S’上的最優(yōu)解p(j)-p(i)的最大值，對所有的i∈S且j∈S’前兩個選擇中的每一個在T(n/2)時間內(nèi)被遞歸地計算；第三個選擇通過找S中的最小與S’中的最大而計算，該操作需要O(n)時間。則運行時間的遞推關(guān)系式是：則算法的時間復雜度為：O(nlog2n)。具體算法：偽代碼int

MaxProfit(intp[],intm,intn){ //求第m到第n天內(nèi)一次買賣股票的最大收益

inti=m,j=(m+n)/2+1;//在第i天買入股票，并在第j天賣出股票

intk;

intmax1,max2,max3; //三個可能的最優(yōu)解

max1=MaxProfit(p,m,(m+n)/2);