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

1、24 -13 29 113 8765-93614764483675012345678910111213課后練習課后練習練習練習1：給定數(shù)組給定數(shù)組a0:n-1，1. 試設計一個試設計一個分治法分治法算法，找出算法，找出a0:n-1中元素中元素最最大值大值和和最小值最小值；2. 寫出該算法時間函數(shù)寫出該算法時間函數(shù)T(n)的遞推關系式的遞推關系式；3. 分析該算法的時間復雜度和空間復雜度分析該算法的時間復雜度和空間復雜度。 1)1()2(21)1()(nOnTnOnT算法的基本思想：算法的基本思想：如果數(shù)組中只有一個元素，如果數(shù)組中只有一個元素，則該元素即是數(shù)組中最大的元素，否則將數(shù)組則該元素即

2、是數(shù)組中最大的元素，否則將數(shù)組對分為前半部分和后半部分。對分為前半部分和后半部分。用同樣的方法求數(shù)組前半部分的最大值用同樣的方法求數(shù)組前半部分的最大值max1。用同樣的方法求數(shù)組后半部分的最大值用同樣的方法求數(shù)組后半部分的最大值max2。若若max1max2，則，則max1為數(shù)組中的最大為數(shù)組中的最大值；否則值；否則max2為數(shù)組中的最大值。為數(shù)組中的最大值。具體執(zhí)行過程：求最大值具體執(zhí)行過程：求最大值51324 -13 29 113 8765-9361476448367501234567891011121324 -13 29 113 8765-901234563614764483675789

3、1011121324 -13 29 11301238765-945636147644789108367511121324 -130129 11323876545-96361478764491083671112240-1312921133874655367148769441083116712int MAXA( A, i, j) int i, j, max=0, max1=0, max2=0; int A; if( i=j ) max=Ai; else /求數(shù)組前半部分的最大值求數(shù)組前半部分的最大值max1 max1 = MAXA( A, i, (i+j)/2 ); /求數(shù)組后半部分的最大值求數(shù)組

4、后半部分的最大值max2 max2 = MAXA( A, (i+j)/2+1, j ); if( max1 max2 ) max = max1; else max = max2; return max;課后練習課后練習 練習練習2：分析如下時間函數(shù)的復雜度，并說明分析如下時間函數(shù)的復雜度，并說明原因。原因。1. 利用利用遞歸樹遞歸樹說明以下時間函數(shù)的復雜度：說明以下時間函數(shù)的復雜度： 1)()4(31)1()(nnOnTnOnT2. 利用利用主定理主定理說明以下時間函數(shù)的復雜度：說明以下時間函數(shù)的復雜度：T(n) = 16T(n/4) + nT(n) = T(3n/7) + 1T(n) = 3

5、T(n/4) + nlogn 練習練習2：分析如下時間函數(shù)的復雜度，并說明原因。分析如下時間函數(shù)的復雜度，并說明原因。1. 利用利用遞歸樹遞歸樹說明以下時間函數(shù)的復雜度：說明以下時間函數(shù)的復雜度： 1)()4(31)1()(nnOnTnOnT 遞歸樹的高度為：遞歸樹的高度為：log4n+1; 除去葉子結點，樹有除去葉子結點，樹有l(wèi)og4n層，每層結點總數(shù)為：層，每層結點總數(shù)為：)43()43(431(1log224 nnc 最后一層葉子結點數(shù)：最后一層葉子結點數(shù)：3loglog443nn 換換 底底 公公 式式2. 利用利用主定理主定理說明以下時間函數(shù)的復雜度：說明以下時間函數(shù)的復雜度：T(n

6、) = 16T(n/4) + nT(n) = T(3n/7) + 1T(n) = 3T(n/4) + nlogn定理定理（主定理主定理）：）： a1且且b1是常數(shù)，是常數(shù)， f(n)是一個函數(shù)，是一個函數(shù)，T(n)由由如下的遞推式定義：如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，式中，n/b指指 n/b 或或 n/b ，則，則T(n)有如下的漸近界：有如下的漸近界：（1）若對于某常數(shù)）若對于某常數(shù)0，有，有f(n)=O(nlogba-)，則，則T(n)= (nlogba)；（2）若）若f(n)= (nlogba )，則，則T(n)= (nlogbalogn)；（3）若對于某常數(shù)

7、）若對于某常數(shù)0，有，有f(n)= (nlogba+ )，且對于某個常數(shù)，且對于某個常數(shù)c1和所有足夠大的和所有足夠大的n，有，有af(n/b)cf(n)，則，則T(n)= (f(n)。 練習練習3：分析分析Strassen矩陣乘法在時間效率上有何矩陣乘法在時間效率上有何改進，為什么？改進，為什么？ Strassen矩陣乘積分治算法中，用矩陣乘積分治算法中，用了了7次對于次對于n/2階階矩陣乘積的矩陣乘積的遞歸調(diào)用遞歸調(diào)用和和18次次n/2階矩陣的階矩陣的加減運算加減運算。由此可知，該算法的所需的計算時間由此可知，該算法的所需的計算時間T(n)滿足如滿足如下的遞歸方程：下的遞歸方程： 22/7

8、212nnOnTnOnTT(n)=O(nlog7)O(n2.81) 較大的改進較大的改進課后練習課后練習 練習練習4：劃出下列序列在快速排序過程中一次劃出下列序列在快速排序過程中一次劃分的具體步驟。劃分的具體步驟。21 25 49 25* 16 08一次劃分的過程一次劃分的過程初始關鍵字初始關鍵字pivotkey一次交換一次交換二次交換二次交換三次交換三次交換四次交換四次交換完成一趟排序完成一趟排序lowhighlowhighhighlowlowhighhighlowhighlow課后練習課后練習 練習練習5：算法實現(xiàn)題算法實現(xiàn)題2-8（教材第（教材第42頁）集合劃頁）集合劃分問題。分問題。

9、要求：要求： 設計算法；設計算法； 寫出該算法時間函數(shù)寫出該算法時間函數(shù)T(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ù)輸入

10、：數(shù)據(jù)輸入：由文件由文件input.txt 提供輸入數(shù)據(jù)。文件的第提供輸入數(shù)據(jù)。文件的第1 行行是元素個數(shù)是元素個數(shù)n 和非空子集數(shù)和非空子集數(shù)m。 結果輸出：結果輸出：程序運行結束時，將計算出的不同的由程序運行結束時，將計算出的不同的由m個非個非空子集組成的集合數(shù)輸出到文件空子集組成的集合數(shù)輸出到文件output.txt 中。中。 遞歸公式：遞歸公式： 設設n個元素的集合可以劃分為個元素的集合可以劃分為F(n,m)個不同的由個不同的由m個非空子集組成的集合。個非空子集組成的集合。F(n,m) = 1, when n=0, n=m, n=1, or m=1F(n,m) = 0, when nm

11、否則否則 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，3F(3,1)=1;F(3,2)=3;F(3,3)=1; 如果要求如果要求F(4,2)該怎么辦呢？該怎么辦呢？A. 往往里添一個元素里添一個元素4，得到，得到1，2，3，4B. 往往里的任意一個子集添一個里的任意一個子集添一個4，得到，得到1，2，4，3，1，2，3，4，1，3，4，2，1，3，2，4，2，3，4，1，2，3，1

12、，4F(4,2)=F(3,1)+2*F(3,2)1+2*37課后練習（選做）課后練習（選做） 練習練習6：假設有假設有n個項的數(shù)組個項的數(shù)組A，每個項具有一個，每個項具有一個不同的數(shù)。告訴你值不同的數(shù)。告訴你值A1,A2,An的序列是的序列是單單峰峰的：對于某個在的：對于某個在1與與n之間的下標之間的下標p，數(shù)組項的值，數(shù)組項的值增加到增加到A中的位置中的位置p，然后剩下的過程減少直到位，然后剩下的過程減少直到位置置n。 要求：要求： 利用分治策略設計一個算法，讀盡可能少的元利用分治策略設計一個算法，讀盡可能少的元素，找到這個素，找到這個“頂峰頂峰”元素元素p。 分析該算法的時間復雜性。分析該

13、算法的時間復雜性。問題分析問題分析 何為何為“單峰單峰”？ 對于某個在對于某個在1與與n之間的下標之間的下標p，數(shù)組項的值增，數(shù)組項的值增加到加到A中的位置中的位置p，然后剩下的過程減少直到，然后剩下的過程減少直到位置位置n； 即在即在A1到到An的的n個數(shù)中，只有一個極大值個數(shù)中，只有一個極大值Ap； Ap前的元素均小于前的元素均小于Ap，并按升序排列；，并按升序排列； Ap后的元素均小于后的元素均小于Ap，并按降序排列。，并按降序排列。分治法思想分治法思想 查看查看An/2值，分析其是出現(xiàn)在值，分析其是出現(xiàn)在上坡上坡上（上（ An/2在在Ap之之前）還是前）還是下坡下坡上（上（An/2在在

14、Ap之后）。之后）。 如果如果An/2-1An/2An/2+1，那么，那么n/2項一定嚴格位項一定嚴格位于于p的前面，因此可以在的前面，因此可以在n/2+1項到項到n項之間項之間遞歸地繼續(xù)下遞歸地繼續(xù)下去。去。 如果如果An/2-1An/2An/2+1，那么，那么n/2項一定嚴格位項一定嚴格位于于p的后面，因此可以在的后面，因此可以在1項到項到n/2-1項之間項之間遞歸地繼續(xù)下遞歸地繼續(xù)下去。去。 如果如果An/2比比An/2-1和和An/2+1都大，頂峰項實際上就等都大，頂峰項實際上就等于于An/2。具體算法：偽代碼具體算法：偽代碼int Danfeng(int A, int m, int

15、n) /求單峰數(shù)組中的頂峰值求單峰數(shù)組中的頂峰值int k=(m+n)/2;if(k=m&k=n)return Ak;if(Ak-1Ak+1)return Ak;elseif(Ak-1Ak&AkAk&AkAk+1)Danfeng(A, m, k-1);時間復雜性分析時間復雜性分析 該算法的時間函數(shù)的遞推式為：該算法的時間函數(shù)的遞推式為： 1)1()2(1)1()(nOnTnOnT 該算法的時間復雜度為：該算法的時間復雜度為：O(log2n)課后練習（選做）課后練習（選做） 練習練習7：假設你正在為一個小的投資公司咨詢，他們有下假設你正在為一個小的投資公司咨詢，他們有下面

16、類型的問題想要一次又一次的求解。這個問題的一個面類型的問題想要一次又一次的求解。這個問題的一個典型實例如下所述。他們正在做一項模擬，在這項模擬典型實例如下所述。他們正在做一項模擬，在這項模擬中他們從過去的某點開始對一只給定的股票連續(xù)看中他們從過去的某點開始對一只給定的股票連續(xù)看n天。天。讓我們把這些天記為數(shù)讓我們把這些天記為數(shù)i=1,2,n；對每天；對每天i，他們有當天，他們有當天這只股票每股的價格這只股票每股的價格p(i)（簡單起見，假設這個價格在一（簡單起見，假設這個價格在一天之內(nèi)是固定的）。假設在這個時間區(qū)間內(nèi)，某天他們天之內(nèi)是固定的）。假設在這個時間區(qū)間內(nèi)，某天他們想買想買1000股并

17、且在以后的某天賣出所有這些股。他們想股并且在以后的某天賣出所有這些股。他們想知道：為了掙到最多的錢，他們應該什么時候買并且什知道：為了掙到最多的錢，他們應該什么時候買并且什么時候應該賣？么時候應該賣？問題分析、舉例說明問題分析、舉例說明 利用利用分治策略分治策略設計一個算法。設計一個算法。 舉例：舉例： 假設假設n=3, p(1)=9, p(2)=1, p(3)=5. 那么應該得出那么應該得出“2買，買，3賣賣”的結論。即，在第的結論。即，在第2天買并且在第天買并且在第3天賣意味著每股天賣意味著每股將掙將掙4美元，是這個期間最大的收益。美元，是這個期間最大的收益。 問題分析：問題分析： 存在一

18、個簡單的算法，時間復雜度是存在一個簡單的算法，時間復雜度是O(n2)：對所有的：對所有的買買天天/賣天構成的對賣天構成的對進行嘗試，看看哪個對能使用戶掙到進行嘗試，看看哪個對能使用戶掙到最多的錢。最多的錢。 假設在第假設在第i天買、第天買、第j天賣可以獲得最大收益：天賣可以獲得最大收益：最優(yōu)解最優(yōu)解。 怎樣在怎樣在O(nlog2n)時間找到正確的時間找到正確的i和和j。 一共有一共有n天的數(shù)據(jù)，即天的數(shù)據(jù)，即p(1), p(2), , p(i), p(i+1), , p(n-1), p(n)。 設設S是是1天，天，n/2天的集合；天的集合；S是是n/2+1，n天的集天的集合。合。 分治法策略：

19、分治法策略： 或者有一個或者有一個最優(yōu)解最優(yōu)解使投資者在使投資者在n/2結束時持有這只股票：結束時持有這只股票：第第i天買入股票，此時天買入股票，此時in/2；第；第j天賣出股票，此時天賣出股票，此時jn/2+1。 或者沒有：或者沒有： 最優(yōu)解最優(yōu)解在集合在集合S中（中（i與與j均均n/2）：用戶可以在前）：用戶可以在前n/2天天內(nèi)買入股票并賣出；內(nèi)買入股票并賣出； 或者或者最優(yōu)解最優(yōu)解在集合在集合S中（中（ i與與j均均n/2+1）：用戶可以）：用戶可以在后在后n/2天內(nèi)買入股票并賣出。天內(nèi)買入股票并賣出。 則算法是在下面三個可能的解中最好的：則算法是在下面三個可能的解中最好的： S上的最優(yōu)解上的最優(yōu)解 S上的最優(yōu)解上的