2011算法2遞歸與分治策略

1、12 2Hanoi塔問題 例1：Hanoi塔問題：有A、B、C三根柱子。A上有n個圓盤，自下而上由大到小地疊在一起。ABCn現(xiàn)要將A上的全部圓盤移到B上，并要求：(1)每次只能移動一個圓盤；(2)任何時刻都不允許將較大的圓盤壓在較小的圓盤上；(3)圓盤只能在A、B、C三個柱子間移動。nHanoi塔的解可以很自然地看成這樣一個過程：(1)先將A上面n1個盤移至C。 (2)再將A上剩下的1個盤移至B。 (3)最后將C上的n1個盤移至B。 于是可得到如下的程序：void Hanoi(int n, int Fr, int To, int As) if (n 0) Hanoi(n1, Fro, Ass,

2、 To); Move(Fro, To); Hanoi(n1, Ass, To, Fro) 3 3遞歸的概念 簡單地說，遞歸就是用自己來定義自己。遞歸算法是一個直接或間接地調(diào)用自己的算法。 一般地說，一個遞歸過程P可以表示為基語句S(不含P)和P自身的組合：P (S, P) 這樣的表示包含了過程不終止的可能，因此遞歸算法應更準確地表述為P if B then Q else (S, P) 其中Q也不包含P，B為遞歸終止條件。4 4遞歸元 遞歸算法的思想是將對較大規(guī)模的對象的操作歸結(jié)為對較小規(guī)模的對象實施同樣的操作。 這種規(guī)模的變化就體現(xiàn)在遞歸算法的變元中的一類(一個或幾個)變元上，這類變元被稱之為

3、遞歸元。 遞歸元的變化是在遞歸定義中確定的，它的變化應能導致遞歸算法的終止。 在遞歸算法的設計中遞歸元是非常重要的。5 5常見的遞歸形式 多變元遞歸； 多步遞歸； 嵌套遞歸； 聯(lián)立遞歸 除基本的遞歸形式外，其它常見的遞歸形式有四種，它們是：6 6多變元遞歸 多變元遞歸就是遞歸元多于一個的遞歸。 例2：整數(shù)劃分問題：將一個正整數(shù)n表示為一系列正整數(shù)之和，n = n1 + n2 +nk 其中n1n2nk1, k1。 正整數(shù)n的一個這種表示稱為正整數(shù)n的一個劃分。正整數(shù)n的不同的劃分的個數(shù)成為正整數(shù)n的劃分數(shù)，記作(n)。 例如(6) = 11 ，即整數(shù)6的劃分數(shù)為11種： 6, 5+1, 4+2,

4、 4+1+1, 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1， 1+1+1+1+1+17 7正整數(shù)的劃分 有時候，問題本身具有比較明顯的遞歸關系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設p(n)為正整數(shù)n的劃分數(shù)，則難以直接找到遞歸關系。8 8正整數(shù)的劃分 因此考慮增加一個自變量：在正整數(shù)的所有不同劃分中，將最大加數(shù)n1不大于m的劃分個數(shù)記為q(n, m)，可以建立如下的遞歸關系： 最簡單情形：(1) q(n, 1)=1，q(1, m) =1 n, m1; 遞歸關系： (2) q(n, n) = 1 + q(n, n1)，n1; 產(chǎn)生的新情況

5、： (3) q(n, m) = q(n, m1) + q(nm, m), nm1 (4) q(n, m) = q(n, n), nm。 1 n = 1 或 m = 1 q(n, m) = 1 + q(n, n1) n m q(n, m1)+q(nm, m) nm1 數(shù)記為q(n, m)，可以建立如下的二元遞歸函數(shù)： int q(int n, int m) if (n 1) | (m 1) return 0; if (n = 1) | (m = 1) return 1; if(n 1nFibonacci函數(shù)是一個兩步的遞歸函數(shù)。1010嵌套遞歸 所謂嵌套遞歸是指遞歸調(diào)用中又含有遞歸調(diào)用，又稱為多

6、重遞歸。 例如Ackermann函數(shù)： 2 n=1, m=0 A(n, m) = 1 m= 0, n = 0 n+2 n = 2, m=0 A(A(n-1, m), m-1) n, m = 1nAckermann函數(shù)是一個雙重的遞歸函數(shù)。1111聯(lián)立遞歸 聯(lián)立遞歸是同時定義幾個函數(shù)，它們彼此相互調(diào)用，從而形成遞歸，又稱間接遞歸。12 將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。13 對這k個子

7、問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。14 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2

8、T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)15 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設計思想是，將一個難以直接解決的大問題，分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題

9、，以便各個擊破，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分而治之。16分治法的一般算法 分治法的一般的算法模式為： Divide-and-Conquer(P) /|P|=n0表示P的規(guī)模不超過閾值n0，可直接求解 if (|P|=n0) return Adhoc(P); divide P into smaller subinstants P1, ., Pk; for (i =1; i = k; i+) yi = Divide-and-Conquer(Pi); return Merge(y1, , yk); /算法Merge(y1, , yk)表示將子問題的解合成P的解人們從大量實

10、踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡平衡(balancing)子問題子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。17分治法的時間復雜性 分治法的時間復雜性為： O(1) n = 1T(n) kT(n/m) + f(n) n1其中設子問題規(guī)模為n/m，Merge的時間為f(n)。n求解此遞歸方程可得：T(n) nlogmk logmn1 + kjf(n/mj) j=018該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題的規(guī)?？s小到一定的程度就可以容易地解決；

11、該問題可以分解為若干個規(guī)模較小的相同問題，即該問該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。之間不包含公共的子問題。 因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應用能否利用分治法完全取決于問題是否具有這條特征，如果具備了

12、前兩條特征，而不具備第三條特征，則可以考慮貪心算法貪心算法或動態(tài)規(guī)劃動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃動態(tài)規(guī)劃較好。19分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二

13、個和第三個適用條件。 分析：很顯然此問題分解出的子問題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。分析：分析： 該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題該問題可以分解為若干個規(guī)模較小的相同問題; 分解出的子問題的解可以合并為原問題的解；分解出的子問題的解可以合并為原問題的解； 分解出的各個子問題是相互獨立的。分解出的各個子問題是

14、相互獨立的。 20給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。據(jù)此容易設計出二分搜索算法二分搜索算法：template int BinarySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 算法復雜度分析：算法復雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運算需要