【正文】 而正整數(shù) n的劃分?jǐn)?shù) p(n)=q(n,n)。（其中： Ri=R－ { ri } ) 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 13 遞歸的概念 ?例 5 整數(shù)劃分問題 ?將一個(gè)正整數(shù) n表示成形如下式的一系列正整數(shù)的和，稱為 n的一個(gè)劃分。 222( , 3 ) 2nAn ?22265536( 3 , 4 ) 2A ?2 1 , 01 0 , 0( , )2 2 , 0( ( 1 , ) , 1 ) , 1nmnmA n mn n mA A n m m n m???????? ?? ? ??? ? ? ??算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 12 遞歸的概念 ?例 4 數(shù)列的全排列問題 ? 求 n個(gè)元素 R={r1,r2,…,r n}的全排列 perm(R) 。 Ackerman函數(shù) A(n,m)定義如下 ： 2 1 , 01 0 , 0( , )2 2 , 0( ( 1 , ), 1 ) , 1nmnmA n mn n mA A n m m n m???????? ?? ? ??? ? ? ?? 遞歸的概念 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 11 遞歸的概念 ?Ackerman函數(shù) ? A(n,0)＝ n+2 ? A(n,1) ＝ 2n ? A(n,2) ＝ 2n 。 (2)非遞歸定義： nnn ??????? )1(321! ?算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 4 遞歸的概念 ?例 2: Fibonacci數(shù)列 ? 問題引入 ?裴波那契（ Fibonacci leonardo，約 11701250）是意大利著名數(shù)學(xué)家． ?在他的著作 《 算盤書 》 中許多有趣的問題，最富成功的問題是著名的“ 兔子繁殖問題 ”： 如果每對(duì)兔子每月繁殖一對(duì)子兔，而子兔在出生后第二個(gè)月就有生殖能力，試問一對(duì)兔子一年能繁殖多少對(duì)兔子？ ?問題分析 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 5 遞歸的概念 月份 初生 成熟 總數(shù) 0 1 0 1 1 0 1 1 2 1 1 2 3 1 2 3 4 2 3 5 5 3 5 8 6 5 8 13 …… …… …… …… 0 1 2 3 4 10( ) 1 1( 1 ) ( 2) 1nF n nF n F n n??????? ? ? ? ??算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 6 遞歸的概念 ?數(shù)列的特點(diǎn) ? 數(shù)列的增長(zhǎng)速度 ? 自然科學(xué)中的若干實(shí)例 ? 構(gòu)造一個(gè)新數(shù)列 ( ) 5 1 0 . 6 1 8 . . . (( 1 ) 2l imnfnfn?????? 黃 金 分 割 數(shù) ）算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 7 ?定義及解法 00( ) 1 1( 1 ) ( 2) 1nF n nF n F n n??????? ? ? ? ?? 遞歸的概念 111 1 5 1 5()225nnFn????? ? ? ???????? ? ? ?? ? ? ?? ? ? ???111110nnnnnFFFF???→ O() → O(n) → O(logn) 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 8 遞歸的概念 ?三種解法的比較 ?解法 1： O() ?解法 2： O(n) ?解法 3： O(logn) fib(110)： O() ? 1022 次運(yùn)算 O(n) ? 111 次運(yùn)算 O(logn) ? 7 次運(yùn)算 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 9 遞歸的概念 ?思考： ?樓梯問題 ?有一樓梯共有 n階，上樓可以一步上一階，也可以一步上兩階。211。 2022 第 2章 遞歸與分治策略 ? 遞歸的概念 ? 分治法的基本思想 ? 分治法的應(yīng)用 ?本章小結(jié) 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 2 遞歸的概念 ?嵌套與遞歸 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 3 遞歸的概念 例 1: 階乘函數(shù) 階乘函數(shù)可遞歸地定義為： 00)!1(1!???????nnnnn邊界條件 遞歸方程 注意： (1)邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。 ?編一個(gè)程序，計(jì)算共有多少種不同的走法？ 11( ) 2 2( 1 ) ( 2) 2nS n nS n S n n??????? ? ? ? ??算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 10 例 3 Ackerman函數(shù) 當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是 雙遞歸函數(shù) 。 ? ? A(n,4)的增長(zhǎng)速度非常快，以致于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。 ? 分析： ? 當(dāng) n=1時(shí)， perm(R)=(r) ? 當(dāng) n1時(shí)， perm(R) 由 (r1)perm(R1) (r2)perm(R2) ……… (rn)perm(Rn) ? 構(gòu)成。 ?形如： n＝ n1＋ n2＋ …… ＋ nk 其中： (ni≥1， i＝ 1,2,…, k， k≥1)且 n≥n1≥n2≥……≥ nk ≥1 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 14 遞歸的概念 ?例如：整數(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。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 16 遞歸的概念 ?幾個(gè)概念 ? n的 r劃分 ? n的 r劃分?jǐn)?shù) ? n的不可重復(fù)劃分 ?問題擴(kuò)展 1 ? 將正整數(shù)劃分成連續(xù)的正整數(shù)之和。 else { hanoi(n1, a, c, b)。 hanoi(n1, c, b, a)。 ? 所以， n個(gè)盤子的移動(dòng)次數(shù)為： 11()2 ( 1 ) 1 1( ) 2 1nnTnT n nTn??? ?? ? ??? ? ? 遞歸的概念 若 n=64，則移動(dòng)次數(shù)為 264－ 1 264－ 1＝ 18,446,744,073,709,551,615 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 23 遞歸的概念 ?264－ 1＝ 18,446,744,073,709,551,615是個(gè)什么概念？ ?實(shí)例 1： ?假設(shè)每秒鐘移動(dòng)一次，一年約 31556926秒， ?計(jì)算表明：移動(dòng) 64個(gè)盤子需要 5800多億年。 ? 缺點(diǎn)： ? 遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 ? 通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 27 分治法的設(shè)計(jì)思想是 : 將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。 孫子兵法 分治法的基本思想 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 28 分治法的基本思想 ?分治法（ Divide and Conquer）的基本思想 : ? 分解 (Divide)： ? 將一個(gè)規(guī)模為 n的問題， 分解 為 k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同。 ? 合并 (Merge)： ? 將各個(gè)子問題的解 合并 得到原問題的解。 //解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,...,Pk； //分解問題 for (i=1。i++) //遞歸地解各子問題 yi=divideandconquer(Pi)。 //將各子問題的解合并 //為原問題的解 } 算法設(shè)計(jì)與分析 遞歸與分治策略 ? 四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 劉芳 30 分治法的基本思想 ?啟發(fā)式規(guī)則： ?平衡 子問題： ?在用分治法設(shè)計(jì)算法時(shí)，最好使