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

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

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

3、1324 -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;課后練習(xí)課后練習(xí) 練習(xí)練習(xí)2：分析如下時(shí)間函數(shù)的復(fù)雜度，并說(shuō)明分析如下時(shí)間函數(shù)的復(fù)雜度，并說(shuō)明原因。原因。1. 利用利用遞歸樹(shù)遞歸樹(shù)說(shuō)明以下時(shí)間函數(shù)的復(fù)雜度：說(shuō)明以下時(shí)間函數(shù)的復(fù)雜度： 1)()4(31)1()(nnOnTnOnT2. 利用利用主定理主定理說(shuō)明以下時(shí)間函數(shù)的復(fù)雜度：說(shuō)明以下時(shí)間函數(shù)的復(fù)雜度：T(n) = 16T(n/4) + nT(n) = T(3n/7) + 1T(n) = 3T(n/4)

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

6、T(n/4) + nT(n) = T(3n/7) + 1T(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)有如下的漸近界：有如下的漸近界：（1）若對(duì)于某常數(shù)）若對(duì)于某常數(shù)0，有，有f(n)=O(nlogba-)，則，則T(n)= (nlogba)；（2）若）若f(n)= (nlogba )，則，則T(n)= (nlogbalogn)；（3）若對(duì)于某常數(shù)）若對(duì)于某常

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

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

9、 設(shè)計(jì)算法；設(shè)計(jì)算法； 寫(xiě)出該算法時(shí)間函數(shù)寫(xiě)出該算法時(shí)間函數(shù)T(n)的遞推關(guān)系式；的遞推關(guān)系式； 分析其時(shí)間復(fù)雜度和空間復(fù)雜度。分析其時(shí)間復(fù)雜度和空間復(fù)雜度。關(guān)于集合劃分問(wèn)題的分析關(guān)于集合劃分問(wèn)題的分析 例如：例如：集合集合 1, 2, 3 有五個(gè)劃分有五個(gè)劃分 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ù)輸入：

10、由文件由文件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è)非空子集組成的集合數(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=1F(n,m) = 0, when nm否則否則 F

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

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

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

14、之后）。 如果如果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ù)下去。去。 如果如果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) /求單

15、峰數(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í)間復(fù)雜性分析時(shí)間復(fù)雜性分析 該算法的時(shí)間函數(shù)的遞推式為：該算法的時(shí)間函數(shù)的遞推式為： 1)1()2(1)1()(nOnTnOnT 該算法的時(shí)間復(fù)雜度為：該算法的時(shí)間復(fù)雜度為：O(log2n)課后練習(xí)（選做）課后練習(xí)（選做） 練習(xí)練習(xí)7：假設(shè)你正在為一個(gè)小的投資公司咨詢(xún)，他們有下假設(shè)你正在為一個(gè)小的投資公司咨詢(xún)，他們有下面類(lèi)型的問(wèn)題想

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

17、天賣(mài)出所有這些股。他們想股并且在以后的某天賣(mài)出所有這些股。他們想知道：為了掙到最多的錢(qián)，他們應(yīng)該什么時(shí)候買(mǎi)并且什知道：為了掙到最多的錢(qián)，他們應(yīng)該什么時(shí)候買(mǎi)并且什么時(shí)候應(yīng)該賣(mài)？么時(shí)候應(yīng)該賣(mài)？問(wèn)題分析、舉例說(shuō)明問(wèn)題分析、舉例說(shuō)明 利用利用分治策略分治策略設(shè)計(jì)一個(gè)算法。設(shè)計(jì)一個(gè)算法。 舉例：舉例： 假設(shè)假設(shè)n=3, p(1)=9, p(2)=1, p(3)=5. 那么應(yīng)該得出那么應(yīng)該得出“2買(mǎi)，買(mǎi)，3賣(mài)賣(mài)”的結(jié)論。即，在第的結(jié)論。即，在第2天買(mǎi)并且在第天買(mǎi)并且在第3天賣(mài)意味著每股天賣(mài)意味著每股將掙將掙4美元，是這個(gè)期間最大的收益。美元，是這個(gè)期間最大的收益。 問(wèn)題分析：?jiǎn)栴}分析： 存在一個(gè)簡(jiǎn)單的算法

18、，時(shí)間復(fù)雜度是存在一個(gè)簡(jiǎn)單的算法，時(shí)間復(fù)雜度是O(n2)：對(duì)所有的：對(duì)所有的買(mǎi)買(mǎi)天天/賣(mài)天構(gòu)成的對(duì)賣(mài)天構(gòu)成的對(duì)進(jìn)行嘗試，看看哪個(gè)對(duì)能使用戶(hù)掙到進(jìn)行嘗試，看看哪個(gè)對(duì)能使用戶(hù)掙到最多的錢(qián)。最多的錢(qián)。 假設(shè)在第假設(shè)在第i天買(mǎi)、第天買(mǎi)、第j天賣(mài)可以獲得最大收益：天賣(mài)可以獲得最大收益：最優(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天的集天的集合。合。 分治法策略：分治法策略：

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