【正文】 分治法的設(shè)計思想是，將一個難以直接解決的大問題， 分割成一些規(guī)模較小的相同問題，以便各個擊破， 分而治之。 遞歸的概念 例 1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為： 00)!1(1!???????nnnnn邊界條件 遞歸方程 邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。 ?n2222? 遞歸的概念 例 3 Ackerman函數(shù) ? 定義單變量的 Ackerman函數(shù) A(n)為， A(n)=A(n，n)。 集合 X中元素的全排列記為 perm(X)。 最大加數(shù) n1實際上不能大于 n。 在本例中，如果設(shè) p(n)為正整數(shù) n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)。各圓盤從小到大編號為 1,2,… ,n,現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 b上，并仍按同樣順序疊置。由此可以設(shè)計出解 Hanoi塔問題的遞歸算法如下。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 divideandconquer(P) { if ( | P | = n0) adhoc(P)。再設(shè)將原問題分解為 k個子問題以及用 merge將 k個子問題的解合并為原問題的解需用 f(n)個單位時間。 二分搜索技術(shù) 給定已按升序排好序的 n個元素 a[0:n1]，現(xiàn)要在這 n個元素中找出一特定元素 x。 else l = m+1。 ?最終的，這個思想導(dǎo)致了 快速傅利葉變換 (Fast Fourier Transform)的產(chǎn)生。 ?在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。 int t = tile++, // L型骨牌號 s = size/2。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。} // 覆蓋右下角子棋盤 if (dr = tr + s amp。 mergeSort(a, i+1, right)。 //對右半段排序 } } 快速排序 templateclass Type int Partition (Type a[], int p, int r) { int i = p, j = r + 1。 return j。 } 快速排序 快速排序算法的性能取決于劃分的對稱性。 線性時間選擇 如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這個基準(zhǔn)所劃分出的 2個子數(shù)組的長度都至少為原數(shù)組長度的 ε倍 (0ε1是某個正常數(shù) )，那么就可以 在最壞情況下 用 O(n)時間完成選擇任務(wù)。以這個元素作為劃分基準(zhǔn)。 for ( int i = 0。這 2點保證了 T(n)的遞歸式中 2個自變量之和n/5+3n/4=19n/20=εn， 0ε1。 ?遞歸地在 S1和 S2上找出其最接近點對 {p1,p2}和 {q1,q2}，并設(shè) d=min{|p1p2|,|q1q2|}， S中的最接近點對或者是 {p1,p2}，或者是 {q1,q2}，或者是某個 {p3,q3}，其中 p3∈ S1且 q3∈ S2。其中 m為 S中各點 x坐標(biāo)的中位數(shù)。設(shè) u， v是位于同一小矩形中的 2個點，則 distance(u,v)d。 if (n 2) return 。 按分治策略，將所有的選手分為兩半， n個選手的比賽日程表就可以通過為 n/2個選手設(shè)計的比賽日程表來決定。這時只要讓這 2個選手進(jìn)行比賽就可以了。 構(gòu)造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} d1=cpair2(S1)。 22222 3625)3/2()2/())()(())()(( dddvyuyvxux ???????為了 確切地知道要檢查哪 6個點 ，可以將 p和P2中所有 S2的點投影到垂直線 l上。 ?遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設(shè)d=min{d1,d2}， S中的最接近點對或者是 d，或者是某個 {p,q}，其中 p∈ P1且 q∈ P2。 ?由于在 S1中，每個長度為 d的半閉區(qū)間至多包含一個點（否則必有兩點距離小于 d），并且 m是 S1和 S2的分割點，因此(md,m]中至多包含 S中的一個點。當(dāng)然，除了 5和 75之外，還有其他選擇。 i++ ) 將 a[p+5*i]至 a[p+5*i+4]的第 3小元素 與 a[p+i]交換位置 。在這種情況下，找出的基準(zhǔn) x至少比 3(n5)/10個元素大，因為在每一組中有 2個元素小于本組的中位數(shù)，而 n/5個中位數(shù)中又有 (n5)/10個小于基準(zhǔn) x。所以，在最壞情況下，算法所需的計算時間 T(n)滿足遞歸式T(n)≤T(9n/10)+O(n) 。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可以在 a[p:r]中隨機選出一個元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機的，從而可以期望劃分是較對稱的。 ji{5, 7, 5, 2, 6, 8} i++。 // 將 x的元素交換到左邊區(qū)域 // 將 x的元素交換到右邊區(qū)域 while (true) { while (a[++i] x)。 //合并到數(shù)組 b copy(a, b, left, right)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s)。 // 覆蓋其余方格 chessBoard(tr, tc+s, tr+s1, tc+s, s)。amp。在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個 L型骨牌不得重疊覆蓋。 Strassen矩陣乘法 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來計算 A和 B的乘積矩陣 C，則每計算 C的一個元素 C[i][j]，需要做 n次乘法和 n1次加法。 } 算法復(fù)雜度分析： 每執(zhí)行一次算法的 while循環(huán)， 待搜索數(shù)組的大小減少一半。 ? 分解出的子問題的解可以合并為原問題的解； ? 分解出的各個子問題是相互獨立的。通常假定 T(n)是單調(diào)上升的，從而當(dāng) mi≤nmi+1時， T(mi)≤T(n)T(mi+1)。 //遞歸的解各子問題 return merge(y1,...,yk)。 通過 變換能 將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 move(a,b)。 在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。 ???????????????????11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq 遞歸的概念 例 5 整數(shù)劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 (1) q(n,1)=1,n?1。 R的全排列可歸納定義如下： 當(dāng) n=1時， perm(R)=(r)，其中 r是集合 R中唯一的元素； 當(dāng) n1時， perm(R)由 (r1)perm(R1)， (r2)perm(R2)， … ，(rn)perm(Rn)構(gòu)成。即 α(n) 是使 n≤A(k) 成立的最小的 k值。它可以遞歸地定義為： 邊界條