【正文】 正整數(shù) n的不 同劃分個數(shù)。 2021年 11月 12日 15 一、遞歸的概念 ?例 5 整數(shù)劃分問題 將正整數(shù) n表示成一系列正整數(shù)之和： n=n1+n2+… +nk， 其中 n1≥n2≥… ≥nk≥1， k≥1。 ? } ? } 思想： 當(dāng)首項和最后一項相等，說明排列結(jié)束就需要輸出了 當(dāng)首項和最后一項不同，首先利用循環(huán)把首項和循環(huán)中的每一項對調(diào)作為首字符（或數(shù)字），之后進(jìn)行從后一位開始的全排列。 ? perm(list,k+1,m)。 i=m。 ? cout endl。 i=m。 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)成。 集合 X中元素的全排列記為 perm(X)。 ? Ackerman函數(shù) A(n， m)定義如下： ?????????????????1,20)1),1((),(2)0,(1),0(2)0,1(mnnmmmnAAmnAnnAmAA2021年 11月 12日 13 一、遞歸的概念 ?例 4 排列問題 設(shè)計一個遞歸算法生成 n個元素 {r1,r2,… ,rn}的全排列。 } 邊界條件 遞歸方程 210)2()1(11)(?????????????nnnnFnFnF2021年 11月 12日 11 一、 遞歸的概念 例 3 Ackerman函數(shù) 前 2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義： nnn ??????? )1(321! ????????????????? ?????????? ???? 1125125151)(nnnF本例中的 Ackerman函數(shù)卻無法找到非遞歸的定義。遞歸定義為： int fibonacci(int n) { if (n = 1) return 1。遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。 return n*factorial(n1)。 下面來看幾個實例。這自然導(dǎo)致遞歸過程的產(chǎn)生。 ?由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。 孫子兵法 2021年 11月 12日 6 提綱 一、遞歸的概念 二、分治法的基本思想 三、分治法的應(yīng)用 2021年 11月 12日 7 提綱 一、遞歸的概念 二、分治法的基本思想 三、分治法的應(yīng)用 2021年 11月 12日 8 遞歸的概念 ?直接或間接地調(diào)用自身的算法稱為 遞歸算法 。 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) 2021年 11月 12日 5 分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 學(xué)習(xí)要點 : 2021年 11月 12日 3 ? 將要求解的較大規(guī)模的問題分割成 k個更小規(guī)模的子問題。 ? 通過下面的范例學(xué)習(xí)分治策略設(shè)計技巧。計算機算法設(shè)計與分析 Design and Analysis of Computer Algorithms 第二章 遞歸與分治策略 2021年 11月 12日 2 ? 理解遞歸的概念。 ? 掌握設(shè)計有效算法的分治策略。 ? （ 1）二分搜索技術(shù)； ? （ 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個子問題分別求解。 2021年 11月 12日 4 算法總體思想 ?將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 凡治眾如治寡，分?jǐn)?shù)是也。用函數(shù)自身給出定義的函數(shù)稱為 遞歸函數(shù) 。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。 ?分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。 2021年 11月 12日 9 一、遞歸的概念 例 1 階乘函數(shù) 00)!1(1!??????? nnnnn邊界條件 遞歸方程 int factorial(int n) { if (n==0) return 1。 } ?邊界條件與遞歸方程是 遞歸函數(shù)的二個要素。 2021年 11月 12日 10 一、遞歸的概念 ? 例 2 Fibonacci數(shù)列 無窮數(shù)列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， …… ，稱為Fibonacci數(shù)列。 return fibonacci(n1)+fibonacci(n2)。 2021年 11月 12日 12 一、遞歸的概念 ? 例 3 Ackerman函數(shù) 當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是 雙遞歸函數(shù)。 設(shè) R={r1,r2,… ,rn}是要進(jìn)行排列的 n個元素， Ri=R{ri}。 (ri)perm(X)表示在全排列 perm(X)的每一個排列前加上前綴 ri得到的排列。 2021年 11月 12日 14 ? template class T ? void perm(T list[], int k, int m) ? {//產(chǎn)生 list[k:m]的所有排列 ? if (k==m) ? {//單元素排列 ? for (int i=0。 i++) cout list[i]。 ? } ? else ? {//多元素序列，遞歸產(chǎn)生排列 ? for (int i=k。 i++) ? { ? swap(list[k],list[i])。 ? swap(list[k],list[i])。再循環(huán)中需要把交換過去的，再換回來一邊下一次進(jìn)行循環(huán)時候使用。 正整數(shù) n的這種表示稱為正整數(shù) n的劃分。 例如：正整數(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。 (4) q(n,m)=q(n,m1)+q(nm,m),nm1。 (3) q(n,n)=1+q(n,n1)。 (1) q(n,1)=1,n?1。 最大加數(shù) n1實際上不能大于 n。 ???????????????????11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq2021年 11月 12日 18 ?int q(int n, int m) { if ((n 1) || (m 1)) return 0。 if(n m) return q (n, n)。 return (q (n, m1)+ q( (n m), m))。開始時，在塔座 a上有一疊共 n個圓盤，這些圓盤自下而上，由大到小地疊在一起。在移動圓盤時應(yīng)遵守以下移動規(guī)則： 規(guī)則 1：每次只能移動 1個圓盤； 規(guī)則 2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則 3：在滿足規(guī)則 1和 2的前提下，可將圓盤移至 a,b,c中任一塔座上。 （ 2）把塔 A上剩下的一個碟子移到塔 C上。 顯然，這是一個遞歸求解的過程 2021年 11月 12日 21 2021年 11月 12日 22 Hanoi塔算法： void hanoi(int n, int a, int b, int c) ① { ② if (n 0) ③ { ④ hanoi(n1, a, c, b)。 ⑥ hanoi(n1, b, a, c)。 反之 ， 退出第 i+1層調(diào)用應(yīng)該返回第 i層 。 2021年 11月 12日 25 Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,A,B,C) Hanio(2,A,C,B) Move (C,B) Hanio(1,C,A,B) Move (A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C) Hanio(1,B,C,A) Move (A,C) Hanio(2,B,A,C) Move (B,A) Hanio(1,A,B,C) 結(jié)束 2021年 11月 12日 26 遞歸函數(shù)的內(nèi)部執(zhí)行過程 一個遞歸函數(shù)的調(diào)用過程類似于多個函數(shù)的嵌套調(diào)用 ，只不過調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù) 。 具體地說 ，遞歸調(diào)用的內(nèi)部執(zhí)行過程如下： （ 1） 運行開始時 ， 首先為遞歸調(diào)用建立一個工作棧 ， 其結(jié)構(gòu)包括值參 、 局部變量和返回地址； （ 2） 每次執(zhí)行遞歸調(diào)用之前 ， 把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧； （ 3） 每次遞歸調(diào)用結(jié)束后 ， 將棧頂元素出棧 ， 使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值 ， 然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行 。 ⑾ ⑿