算法遞歸與分治策略上課講義

1、算法遞歸與分治(fn zh)策略第一頁，共23頁。2Hanoi塔問題(wnt) 例1：Hanoi塔問題：有A、B、C三根柱子。A上有n個圓盤(yun pn)，自下而上由大到小地疊在一起。ABCn現(xiàn)要將A上的全部圓盤移到B上，并要求：(1)每次只能移動(ydng)一個圓盤；(2)任何時刻都不允許將較大的圓盤壓在較小的圓盤上；(3)圓盤只能在A、B、C三個柱子間移動(ydng)。nHanoi塔的解可以很自然地看成這樣一個過程：(1)先將A上面n1個盤移至C。 (2)再將A上剩下的1個盤移至B。 (3)最后將C上的n1個盤移至B。 于是可得到如下的程序：void Hanoi(int n, int F

2、r, int To, int As) if (n 0) Hanoi(n1, Fro, Ass, To); Move(Fro, To); Hanoi(n1, Ass, To, Fro) 第二頁，共23頁。3遞歸的概念(ginin) 簡單地說，遞歸就是用自己來定義自己。遞歸算法是一個直接或間接地調(diào)用自己的算法。 一般地說，一個遞歸過程P可以表示為基語句(yj)S(不含P)和P自身的組合： P (S, P) 這樣的表示包含了過程不終止的可能，因此遞歸算法應(yīng)更準(zhǔn)確地表述為P if B then Q else (S, P) 其中(qzhng)Q也不包含P，B為遞歸終止條件。第三頁，共23頁。4遞歸元 遞

3、歸算法的思想是將對較大規(guī)模的對象的操作歸結(jié)為對較小規(guī)模的對象實(shí)施同樣的操作。 這種規(guī)模的變化就體現(xiàn)在遞歸算法的變元中的一類(一個或幾個)變元上，這類變元被稱之為遞歸元。 遞歸元的變化是在遞歸定義中確定的，它的變化應(yīng)能導(dǎo)致遞歸算法的終止(zhngzh)。 在遞歸算法的設(shè)計中遞歸元是非常重要的。第四頁，共23頁。5常見(chn jin)的遞歸形式 多變元遞歸； 多步遞歸； 嵌套遞歸； 聯(lián)立遞歸 除基本的遞歸形式外，其它常見的遞歸形式有四種(s zhn)，它們是：第五頁，共23頁。6多變元遞歸 多變元遞歸就是遞歸元多于(du y)一個的遞歸。 例2：整數(shù)(zhngsh)劃分問題：將一個正整數(shù)(zhn

4、gsh)n表示為一系列正整數(shù)(zhngsh)之和， n = n1 + n2 +nk 其中n1n2nk1, k1。 正整數(shù)n的一個這種表示(biosh)稱為正整數(shù)n的一個劃分。正整數(shù)n的不同的劃分的個數(shù)成為正整數(shù)n的劃分?jǐn)?shù)，記作(n)。 例如(6) = 11 ，即整數(shù)6的劃分?jǐn)?shù)為11種： 6, 5+1, 4+2, 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+1第六頁，共23頁。7正整數(shù)的劃分(hu fn) 有時候，問題本身具有比較(bjio)明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為

5、正整數(shù)n的劃分?jǐn)?shù)，則難以直接找到遞歸關(guān)系。第七頁，共23頁。8正整數(shù)的劃分(hu fn) 因此考慮(kol)增加一個自變量：在正整數(shù)的所有不同劃分中，將最大加數(shù)n1不大于m的劃分個數(shù)記為q(n, m)，可以建立如下的遞歸關(guān)系： 最簡單情形：(1) q(n, 1)=1，q(1, m) =1 n, m1; 遞歸關(guān)系： (2) q(n, n) = 1 + q(n, n1)，n1; 產(chǎn)生的新情況： (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

6、) n m q(n, m1)+q(nm, m) nm1 數(shù)記為q(n, m)，可以建立(jinl)如下的二元遞歸函數(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ù)(hnsh)是一個兩步的遞歸函數(shù)(hnsh)。第九頁，共23頁。10嵌套遞歸 所謂嵌套遞歸是指遞歸調(diào)用中又含有遞歸調(diào)用，又稱為多重遞歸。 例如(lr)Ackermann函數(shù)： 2 n=1, m=0 A(n, m) = 1 m= 0, n = 0 n+2 n = 2, m=0 A(A(n-

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

8、則再劃分為k個子問題，如此(rc)遞歸的進(jìn)行下去，直到問題規(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ī)模的問題的解，自底向上逐步(zhb)求出原來問題的解。第十三頁，共23頁。14 將求出的小規(guī)模的問題的解合并(hbng)為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4

9、)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)第十四頁，共23頁。15 將求出的小規(guī)模的問題(wnt)的解合并為一個更大規(guī)模的問題(wnt)的解，自底向上逐步求出原來問題(wnt)的解。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) 分治法的設(shè)計思想是，將一個難以(nny)直接解決的大問題，分割成一

10、些規(guī)模較小的相同問題，以便各個擊破，分而治之。第十五頁，共23頁。16分治(fn zh)法的一般算法 分治法的一般(ybn)的算法模式為： 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的解人

11、們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子(g zi)問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。第十六頁，共23頁。17分治(fn zh)法的時間復(fù)雜性 分治(fn zh)法的時間復(fù)雜性為： O(1) n = 1T(n) kT(n/m) + f(n) n1其中(qzhng)設(shè)子問題規(guī)模為n/m，Merge的時間為f(n)。n求解此遞歸方程可得：T(n) nlogmk logmn1 + kjf(n/mj) j=0第十七頁，共23頁。1

12、8因?yàn)閱栴}的計算復(fù)雜性一般是隨著問題規(guī)模的增加(zngji)而增加(zngji)，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。第十八頁，共23頁。19分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用(sh

13、yng)條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析：很顯然此問題分解出的子問題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個適用(shyng)條件。給定已按升序排好序的n個元素a0:n-1，現(xiàn)要在這n個元素中找出一特定元素x。分析： 該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題; 分解出的子問

14、題的解可以合并為原問題的解； 分解出的各個子問題是相互獨(dú)立的。 第十九頁，共23頁。20給定已按升序排好序的n個元素(yun s)a0:n-1，現(xiàn)要在這n個元素(yun s)中找出一特定元素(yun s)x。據(jù)此容易(rngy)設(shè)計出二分搜索算法：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; 算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn) 。第二十頁，共23頁。練習(xí)(linx