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