【正文】 第 2章 遞歸與分治策略 學習要點 : ? 理解遞歸的概念。 ? 掌握設計有效算法的分治策略。 ? 通過下面的范例學習分治策略設計技巧。 ? （ 1）二分搜索技術； ? （ 2）大整數(shù)乘法； ? （ 3） Strassen矩陣乘法； ? （ 4）棋盤覆蓋； ? （ 5）合并排序和快速排序； ? （ 6）線性時間選擇； ? （ 7）最接近點對問題； ? （ 8）循環(huán)賽日程表。 ? 將要求解的較大規(guī)模的問題分割成 k個更小規(guī)模的子問題。 算法總體思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ? 對這 k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 算法總體思想 ? 對這 k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 算法總體思想 ? 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 算法總體思想 ? 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 分治法的設計思想是，將一個難以直接解決的大問題， 分割成一些規(guī)模較小的相同問題，以便各個擊破， 分而治之。 遞歸的概念 ? 直接或間接地調用自身的算法稱為 遞歸算法 。用函數(shù)自身給出定義的函數(shù)稱為 遞歸函數(shù) 。 ? 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產(chǎn)生。 ? 分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設計之中，并由此產(chǎn)生許多高效算法。 下面來看幾個實例。 遞歸的概念 例 1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為： 00)!1(1!???????nnnnn邊界條件 遞歸方程 邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結果。 遞歸的概念 例 2 Fibonacci數(shù)列 無窮數(shù)列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， …… ，稱為Fibonacci數(shù)列。它可以遞歸地定義為： 邊界條件 遞歸方程 110)2()1(11)(????????????nnnnFnFnF第 n個 Fibonacci數(shù)可遞歸地計算如下： int fibonacci(int n) { if (n = 1) return 1。 return fibonacci(n1)+fibonacci(n2)。 } 遞歸的概念 例 3 Ackerman函數(shù) 當一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是 雙遞歸函數(shù) 。 Ackerman函數(shù) A(n， m)定義如下： ?????????????????1,20)1),1((),(2)0,(1),0(2)0,1(mnnmmmnAAmnAnnAmAA 遞歸的概念 例 3 Ackerman函數(shù) 前 2例中的函數(shù)都可以找到相應的非遞歸方式定義： nnn ??????? )1(321! ????????????????? ?????????? ???? 1125125151)(nnnF本例中的 Ackerman函數(shù)卻無法找到非遞歸的定義。 遞歸的概念 例 3 Ackerman函數(shù) ? A(n， m)的自變量 m的每一個值都定義了一個單變量函數(shù)： ? M=0時， A(n,0)=n+2 ? M=1時， A(n,1)=A(A(n1,1),0)=A(n1,1)+2，和 A(1,1)=2故A(n,1)=2*n ? M=2時， A(n,2)=A(A(n1,2),1)=2A(n1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故 A(n,2)= 2^n 。 ? M=3時，類似的可以推出 ? M=4時， A(n,4)的增長速度非常快，以至于沒有適當?shù)臄?shù)學式子來表示這一函數(shù)。 ?n2222? 遞歸的概念 例 3 Ackerman函數(shù) ? 定義單變量的 Ackerman函數(shù) A(n)為， A(n)=A(n，n)。 ? 定義其擬逆函數(shù) α(n) 為： α(n)=min{k ｜A(k)≥n} 。即 α(n) 是使 n≤A(k) 成立的最小的 k值。 ? α(n) 在復雜度分析中常遇到。對于通常所見到的正整數(shù) n，有 α(n)≤4 。但在理論上 α(n) 沒有上界，隨著 n的增加，它以難以想象的慢速度趨向正無窮大。 遞歸的概念 例 4 排列問題 設計一個遞歸算法生成 n個元素 {r1,r2,… ,rn}的全排列。 設 R={r1,r2,… ,rn}是要進行排列的 n個元素， Ri=R{ri}。 集合 X中元素的全排列記為 perm(X)。 (ri)perm(X)表示在全排列 perm(X)的每一個排列前加上前綴得到的排列。 R的全排列可歸納定義如下： 當 n=1時， perm(R)=(r)，其中 r是集合 R中唯一的元素； 當 n1時， perm(R)由 (r1)perm(R1)， (r2)perm(R2)， … ，(rn)perm(Rn)構成。 遞歸的概念 例 5 整數(shù)劃分問題 將正整數(shù) n表示成一系列正整數(shù)之和： n=n1+n2+… +nk， 其中 n1≥n 2≥ … ≥n k≥1 ， k≥1 。 正整數(shù) n的這種表示稱為正整數(shù) n的劃分。求正整數(shù) n的不 同劃分個數(shù)。 例如正整數(shù) 6有如下 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。 (2) q(n,m)=q(n,n),m?n。