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

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

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

3、-9 0123456 3614764483675 78910111213 24 -13 29 113 0123 8765-9 456 36147644 78910 83675 111213 24 -13 01 29 113 23 8765 45 -9 6 3614 78 7644 910 8367 1112 24 0 -13 1 29 2 113 3 87 4 65 5 36 7 14 8 76 9 44 10 83 11 67 12 int MAXA( A, i, j) int i, j, max=0, max1=0, max2=0; int A; if( i=j ) max=Ai; els

4、e /求數(shù)組前半部分的最大值求數(shù)組前半部分的最大值max1 max1 = MAXA( A, i, (i+j)/2 ); /求數(shù)組后半部分的最大值求數(shù)組后半部分的最大值max2 max2 = MAXA( A, (i+j)/2+1, j ); if( max1 max2 ) max = max1; else max = max2; return max; 課后練習(xí)課后練習(xí) 練習(xí)練習(xí)2：分析如下時(shí)間函數(shù)的復(fù)雜度，并說明分析如下時(shí)間函數(shù)的復(fù)雜度，并說明 原因。原因。 1. 利用利用遞歸樹遞歸樹說明以下時(shí)間函數(shù)的復(fù)雜度：說明以下時(shí)間函數(shù)的復(fù)雜度： 1)() 4 (3 1)1( )( nnO n T nO

5、 nT 2. 利用利用主定理主定理說明以下時(shí)間函數(shù)的復(fù)雜度：說明以下時(shí)間函數(shù)的復(fù)雜度： T(n) = 16T(n/4) + n T(n) = T(3n/7) + 1 T(n) = 3T(n/4) + nlogn 練習(xí)練習(xí)2：分析如下時(shí)間函數(shù)的復(fù)雜度，并說明原因。分析如下時(shí)間函數(shù)的復(fù)雜度，并說明原因。 1. 利用利用遞歸樹遞歸樹說明以下時(shí)間函數(shù)的復(fù)雜度：說明以下時(shí)間函數(shù)的復(fù)雜度： 1)() 4 (3 1)1( )( nnO n T nO nT 遞歸樹的高度為：遞歸樹的高度為：log4n+1; 除去葉子結(jié)點(diǎn)，樹有除去葉子結(jié)點(diǎn)，樹有l(wèi)og4n層，每層結(jié)點(diǎn)總數(shù)為：層，每層結(jié)點(diǎn)總數(shù)為： ) 4 3 ()

6、 4 3 ( 4 3 1( 1log2 2 4 n nc 最后一層葉子結(jié)點(diǎn)數(shù)：最后一層葉子結(jié)點(diǎn)數(shù)： 3loglog 44 3n n 換換 底底 公公 式式 2. 利用利用主定理主定理說明以下時(shí)間函數(shù)的復(fù)雜度：說明以下時(shí)間函數(shù)的復(fù)雜度： T(n) = 16T(n/4) + n T(n) = T(3n/7) + 1 T(n) = 3T(n/4) + nlogn 定理定理（主定理主定理）：）： a1且且b1是常數(shù)，是常數(shù)， f(n)是一個(gè)函數(shù)，是一個(gè)函數(shù)，T(n)由由 如下的遞推式定義：如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，式中，n/b指指 n/b 或或 n/b ，則，則T(n

7、)有如下的漸近界：有如下的漸近界： （1）若對于某常數(shù)）若對于某常數(shù)0，有，有f(n)=O(nlogba-)，則，則T(n)= (nlogba)； （2）若）若f(n)= (nlogba )，則，則T(n)= (nlogbalogn)； （3）若對于某常數(shù)）若對于某常數(shù)0，有，有f(n)= (nlogba+ )，且對于某個(gè)常數(shù)，且對于某個(gè)常數(shù) c1和所有足夠大的和所有足夠大的n，有，有af(n/b)cf(n)，則，則T(n)= (f(n)。 練習(xí)練習(xí)3：分析分析Strassen矩陣乘法在時(shí)間效率上有何矩陣乘法在時(shí)間效率上有何 改進(jìn)，為什么？改進(jìn)，為什么？ Strassen矩陣乘積分治算法中，用

8、了矩陣乘積分治算法中，用了7次對于次對于n/2階階 矩陣乘積的矩陣乘積的遞歸調(diào)用遞歸調(diào)用和和18次次n/2階矩陣的階矩陣的加減運(yùn)算加減運(yùn)算。 由此可知，該算法的所需的計(jì)算時(shí)間由此可知，該算法的所需的計(jì)算時(shí)間T(n)滿足如滿足如 下的遞歸方程：下的遞歸方程： 22/7 21 2 nnOnT nO nT T(n)=O(nlog7)O(n2.81) 較大的改進(jìn)較大的改進(jìn) 課后練習(xí)課后練習(xí) 練習(xí)練習(xí)4：劃出下列序列在快速排序過程中一次劃出下列序列在快速排序過程中一次 劃分的具體步驟。劃分的具體步驟。 21 25 49 25* 16 08 一次劃分的過程一次劃分的過程 初始關(guān)鍵字初始關(guān)鍵字 pivotk

9、ey 一次交換一次交換 二次交換二次交換 三次交換三次交換 四次交換四次交換 完成一趟排序完成一趟排序 low high low high high low low high high low high low 課后練習(xí)課后練習(xí) 練習(xí)練習(xí)5：算法實(shí)現(xiàn)題算法實(shí)現(xiàn)題2-8（教材第（教材第42頁）集合劃頁）集合劃 分問題。分問題。 要求：要求： 設(shè)計(jì)算法；設(shè)計(jì)算法； 寫出該算法時(shí)間函數(shù)寫出該算法時(shí)間函數(shù)T(n)的遞推關(guān)系式；的遞推關(guān)系式； 分析其時(shí)間復(fù)雜度和空間復(fù)雜度。分析其時(shí)間復(fù)雜度和空間復(fù)雜度。 關(guān)于集合劃分問題的分析關(guān)于集合劃分問題的分析 例如：例如：集合集合 1, 2, 3 有五個(gè)劃分有五個(gè)

10、劃分 1, 2, 3 ， 1, 2, 3 ， 1, 3, 2 ， 1, 2, 3 ， 1, 2, 3 。 算法設(shè)計(jì)要求：算法設(shè)計(jì)要求：給定正整數(shù)給定正整數(shù)n 和和m，計(jì)算出，計(jì)算出n 個(gè)元素的集個(gè)元素的集 合合1,2,., n 可以劃分為多少個(gè)可以劃分為多少個(gè)不同的由不同的由m 個(gè)非空子集組成個(gè)非空子集組成 的集合的集合。 數(shù)據(jù)輸入：數(shù)據(jù)輸入：由文件由文件input.txt 提供輸入數(shù)據(jù)。文件的第提供輸入數(shù)據(jù)。文件的第1 行行 是元素個(gè)數(shù)是元素個(gè)數(shù)n 和非空子集數(shù)和非空子集數(shù)m。 結(jié)果輸出：結(jié)果輸出：程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的不同的由程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的不同的由m個(gè)非個(gè)非 空子集組成的集

11、合數(shù)輸出到文件空子集組成的集合數(shù)輸出到文件output.txt 中。中。 遞歸公式：遞歸公式： 設(shè)設(shè)n個(gè)元素的集合可以劃分為個(gè)元素的集合可以劃分為F(n,m)個(gè)不同的由個(gè)不同的由 m個(gè)非空子集組成的集合。個(gè)非空子集組成的集合。 F(n,m) = 1, when n=0, n=m, n=1, or m=1 F(n,m) = 0, when nm 否則否則 F(n,m)=F(n-1,m-1)+m*F(n-1,m) 考慮考慮3個(gè)元素的集合，可劃分為個(gè)元素的集合，可劃分為 1個(gè)子集的集合：個(gè)子集的集合：1，2，3 2個(gè)子集的集合：個(gè)子集的集合：1，2，3，1，3，2， 2，3，1 3個(gè)子集的集合：個(gè)子

12、集的集合：1，2，3 F(3,1)=1;F(3,2)=3;F(3,3)=1; 如果要求如果要求F(4,2)該怎么辦呢？該怎么辦呢？ A. 往往里添一個(gè)元素里添一個(gè)元素4，得到，得到1，2，3，4 B. 往往里的任意一個(gè)子集添一個(gè)里的任意一個(gè)子集添一個(gè)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*37 課后練習(xí)（選做）課后練習(xí)（選做） 練習(xí)練習(xí)6：假設(shè)有假設(shè)有n個(gè)項(xiàng)的數(shù)組個(gè)項(xiàng)的數(shù)組A，每個(gè)項(xiàng)具有一個(gè)，每個(gè)項(xiàng)具有一個(gè) 不同的數(shù)。告訴你值不同的數(shù)。告訴你值A(chǔ)1,A2,An的序列是

13、的序列是單單 峰峰的：對于某個(gè)在的：對于某個(gè)在1與與n之間的下標(biāo)之間的下標(biāo)p，數(shù)組項(xiàng)的值，數(shù)組項(xiàng)的值 增加到增加到A中的位置中的位置p，然后剩下的過程減少直到位，然后剩下的過程減少直到位 置置n。 要求：要求： 利用分治策略設(shè)計(jì)一個(gè)算法，讀盡可能少的元利用分治策略設(shè)計(jì)一個(gè)算法，讀盡可能少的元 素，找到這個(gè)素，找到這個(gè)“頂峰頂峰”元素元素p。 分析該算法的時(shí)間復(fù)雜性。分析該算法的時(shí)間復(fù)雜性。 問題分析問題分析 何為何為“單峰單峰”？ 對于某個(gè)在對于某個(gè)在1與與n之間的下標(biāo)之間的下標(biāo)p，數(shù)組項(xiàng)的值增，數(shù)組項(xiàng)的值增 加到加到A中的位置中的位置p，然后剩下的過程減少直到，然后剩下的過程減少直到 位置位

14、置n； 即在即在A1到到An的的n個(gè)數(shù)中，只有一個(gè)極大值個(gè)數(shù)中，只有一個(gè)極大值 Ap； Ap前的元素均小于前的元素均小于Ap，并按升序排列；，并按升序排列； Ap后的元素均小于后的元素均小于Ap，并按降序排列。，并按降序排列。 分治法思想分治法思想 查看查看An/2值，分析其是出現(xiàn)在值，分析其是出現(xiàn)在上坡上坡上（上（ An/2在在Ap之之 前）還是前）還是下坡下坡上（上（An/2在在Ap之后）。之后）。 如果如果An/2-1An/2An/2+1，那么，那么n/2項(xiàng)一定嚴(yán)格位項(xiàng)一定嚴(yán)格位 于于p的前面，因此可以在的前面，因此可以在n/2+1項(xiàng)到項(xiàng)到n項(xiàng)之間項(xiàng)之間遞歸地繼續(xù)下遞歸地繼續(xù)下 去。去。

15、 如果如果An/2-1An/2An/2+1，那么，那么n/2項(xiàng)一定嚴(yán)格位項(xiàng)一定嚴(yán)格位 于于p的后面，因此可以在的后面，因此可以在1項(xiàng)到項(xiàng)到n/2-1項(xiàng)之間項(xiàng)之間遞歸地繼續(xù)下遞歸地繼續(xù)下 去。去。 如果如果An/2比比An/2-1和和An/2+1都大，頂峰項(xiàng)實(shí)際上就等都大，頂峰項(xiàng)實(shí)際上就等 于于An/2。 具體算法：偽代碼具體算法：偽代碼 int Danfeng(int A, int m, int n) /求單峰數(shù)組中的頂峰值求單峰數(shù)組中的頂峰值 int k=(m+n)/2; if(k=m if(Ak-1Ak+1)return Ak; else if(Ak-1Ak 時(shí)間復(fù)雜性分析時(shí)間復(fù)雜性分析

16、該算法的時(shí)間函數(shù)的遞推式為：該算法的時(shí)間函數(shù)的遞推式為： 1)1() 2 ( 1)1( )( nO n T nO nT 該算法的時(shí)間復(fù)雜度為：該算法的時(shí)間復(fù)雜度為：O(log2n) 課后練習(xí)（選做）課后練習(xí)（選做） 練習(xí)練習(xí)7：假設(shè)你正在為一個(gè)小的投資公司咨詢，他們有下假設(shè)你正在為一個(gè)小的投資公司咨詢，他們有下 面類型的問題想要一次又一次的求解。這個(gè)問題的一個(gè)面類型的問題想要一次又一次的求解。這個(gè)問題的一個(gè) 典型實(shí)例如下所述。他們正在做一項(xiàng)模擬，在這項(xiàng)模擬典型實(shí)例如下所述。他們正在做一項(xiàng)模擬，在這項(xiàng)模擬 中他們從過去的某點(diǎn)開始對一只給定的股票連續(xù)看中他們從過去的某點(diǎn)開始對一只給定的股票連續(xù)看n

17、天。天。 讓我們把這些天記為數(shù)讓我們把這些天記為數(shù)i=1,2,n；對每天；對每天i，他們有當(dāng)天，他們有當(dāng)天 這只股票每股的價(jià)格這只股票每股的價(jià)格p(i)（簡單起見，假設(shè)這個(gè)價(jià)格在一（簡單起見，假設(shè)這個(gè)價(jià)格在一 天之內(nèi)是固定的）。假設(shè)在這個(gè)時(shí)間區(qū)間內(nèi)，某天他們天之內(nèi)是固定的）。假設(shè)在這個(gè)時(shí)間區(qū)間內(nèi)，某天他們 想買想買1000股并且在以后的某天賣出所有這些股。他們想股并且在以后的某天賣出所有這些股。他們想 知道：為了掙到最多的錢，他們應(yīng)該什么時(shí)候買并且什知道：為了掙到最多的錢，他們應(yīng)該什么時(shí)候買并且什 么時(shí)候應(yīng)該賣？么時(shí)候應(yīng)該賣？ 問題分析、舉例說明問題分析、舉例說明 利用利用分治策略分治策略設(shè)計(jì)

18、一個(gè)算法。設(shè)計(jì)一個(gè)算法。 舉例：舉例： 假設(shè)假設(shè)n=3, p(1)=9, p(2)=1, p(3)=5. 那么應(yīng)該得出那么應(yīng)該得出“2買，買，3 賣賣”的結(jié)論。即，在第的結(jié)論。即，在第2天買并且在第天買并且在第3天賣意味著每股天賣意味著每股 將掙將掙4美元，是這個(gè)期間最大的收益。美元，是這個(gè)期間最大的收益。 問題分析：問題分析： 存在一個(gè)簡單的算法，時(shí)間復(fù)雜度是存在一個(gè)簡單的算法，時(shí)間復(fù)雜度是O(n2)：對所有的：對所有的買買 天天/賣天構(gòu)成的對賣天構(gòu)成的對進(jìn)行嘗試，看看哪個(gè)對能使用戶掙到進(jìn)行嘗試，看看哪個(gè)對能使用戶掙到 最多的錢。最多的錢。 假設(shè)在第假設(shè)在第i天買、第天買、第j天賣可以獲得最

19、大收益：天賣可以獲得最大收益：最優(yōu)解最優(yōu)解。 怎樣在怎樣在O(nlog2n)時(shí)間找到正確的時(shí)間找到正確的i和和j。 一共有一共有n天的數(shù)據(jù)，即天的數(shù)據(jù)，即p(1), p(2), , p(i), p(i+1), , p(n- 1), p(n)。 設(shè)設(shè)S是是1天，天，n/2天的集合；天的集合；S是是n/2+1，n天的集天的集 合。合。 分治法策略：分治法策略： 或者有一個(gè)或者有一個(gè)最優(yōu)解最優(yōu)解使投資者在使投資者在n/2結(jié)束時(shí)持有這只股票：結(jié)束時(shí)持有這只股票： 第第i天買入股票，此時(shí)天買入股票，此時(shí)in/2；第；第j天賣出股票，此時(shí)天賣出股票，此時(shí) 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)買入股票并賣出。 則算法是在下面三個(gè)可能的解中最好的：則算法是在下面三個(gè)可能的解中最好的： S上的最優(yōu)解上的最優(yōu)解 S上的最優(yōu)解上的