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