【正文】 。 ⑾ ⑿ ⒀ ⒁ ⑹ ⑺ ⑻ ⑼ ⑽ ⑴ ⑵ ⑶ ⑷ ⑸ 5, 3, A, B, C 5, 2, A, C, B 5, 3, A, B, C 5, 1, A, B, C 5, 2, A, C, B 5, 3, A, B, C 5, 2, A, C, B 5, 3, A, B, C 7, 1, C, A, B 5, 2, A, C, B 5, 3, A, B, C 5, 2, A, C, B 5, 3, A, B, C 5, 3, A, B, C 7, 2, B, A, C 5, 3, A, B, C 5, 1, B, C, A 7, 2, B, A, C 5, 3, A, B, C 7, 2, B, A, C 5, 3, A, B, C 7, 1, A, B, C 7, 2, B, A, C 5, 3, A, B, C 7, 2, B, A, C 5, 3, A, B, C 5, 3, A, B, C 2021年 11月 12日 28 思考題： 如果塔的個數(shù)變?yōu)?a,b,c,d四個，現(xiàn)要將n個圓盤從 a全部移動到 d，移動規(guī)則不變，求移動步數(shù)最小的方案。 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ù) 。 ⑥ hanoi(n1, b, a, c)。 （ 2）把塔 A上剩下的一個碟子移到塔 C上。開始時，在塔座 a上有一疊共 n個圓盤，這些圓盤自下而上，由大到小地疊在一起。 if(n m) return q (n, n)。 最大加數(shù) n1實際上不能大于 n。 (3) q(n,n)=1+q(n,n1)。 例如：正整數(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。再循環(huán)中需要把交換過去的，再換回來一邊下一次進(jìn)行循環(huán)時候使用。 i++) ? { ? swap(list[k],list[i])。 i++) cout list[i]。 (ri)perm(X)表示在全排列 perm(X)的每一個排列前加上前綴 ri得到的排列。 2021年 11月 12日 12 一、遞歸的概念 ? 例 3 Ackerman函數(shù) 當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是 雙遞歸函數(shù)。 2021年 11月 12日 10 一、遞歸的概念 ? 例 2 Fibonacci數(shù)列 無窮數(shù)列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， …… ，稱為Fibonacci數(shù)列。 2021年 11月 12日 9 一、遞歸的概念 例 1 階乘函數(shù) 00)!1(1!??????? nnnnn邊界條件 遞歸方程 int factorial(int n) { if (n==0) return 1。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。 凡治眾如治寡，分?jǐn)?shù)是也。 算法總體思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = ? 對這 k個子問題分別求解。 ? 掌握設(shè)計有效算法的分治策略。 ? 通過下面的范例學(xué)習(xí)分治策略設(shè)計技巧。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 孫子兵法 2021年 11月 12日 6 提綱 一、遞歸的概念 二、分治法的基本思想 三、分治法的應(yīng)用 2021年 11月 12日 7 提綱 一、遞歸的概念 二、分治法的基本思想 三、分治法的應(yīng)用 2021年 11月 12日 8 遞歸的概念 ?直接或間接地調(diào)用自身的算法稱為 遞歸算法 。這自然導(dǎo)致遞歸過程的產(chǎn)生。 return n*factorial(n1)。遞歸定義為： int fibonacci(int n) { if (n = 1) return 1。 ? 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}的全排列。 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)成。 ? cout endl。 ? perm(list,k+1,m)。 2021年 11月 12日 15 一、遞歸的概念 ?例 5 整數(shù)劃分問題 將正整數(shù) n表示成一系列正整數(shù)之和： n=n1+n2+… +nk， 其中 n1≥n2≥… ≥nk≥1， k≥1。 2021年 11月 12日 16 一、遞歸的概念 ?例 5 整數(shù)劃分問題 將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)。 正整數(shù) n的劃分由 n1=n的劃分和 n1≤n 1的劃分組成。 2021年 11月 12日 17 一、遞歸的概念 ?例 5 整數(shù)劃分問題 ?正整數(shù) n的劃分?jǐn)?shù) p(n)=q(n,n)。 if(n == m) return (q (n, m 1) + 1)。各圓盤從小到大編號為 1,2,… ,n,現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 c上，并仍按同樣順序疊臵。 （ 3）將 n1個碟子從塔 B借助塔 A移到塔 C上。 ⑦ } ⑧ } ⑨ 2021年 11月 12日 23 2021年 11月 12日 24 遞歸函數(shù)的運行軌跡 在遞歸函數(shù)中 ， 調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù) ， 需要注意的是遞歸函數(shù)的調(diào)用層次 ， 如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第 0層 ， 進(jìn)入函數(shù)后 ，首次遞歸調(diào)用自身稱為第 1層調(diào)用；從第 i層遞歸調(diào)用自身稱為第 i+1層 。 為了保證遞歸函數(shù)的正確執(zhí)行 ， 系統(tǒng)需設(shè)立一個工作棧 。 2021年 11月 12日 29 一、遞歸的概念 遞歸小結(jié)： ?優(yōu)點： 結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 遞歸小結(jié) 2021年 11月 12日 31 遞歸算法求解問題的要素 遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。 2021年 11月 12日 32 設(shè)計遞歸算法的方法是： ⑴尋找方法，將問題化為原問題的子問題求解（ 例 n!=n*(n1)! ）。如果子問題的規(guī)模仍然不夠小，則再劃分為 k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 2021年 11月 12日 42 分治法的設(shè)計 ?設(shè)計過程分為三個階段 ?Divide： 整個問題劃分為多個子問題 ?Conquer： 求解各子問題 (遞歸調(diào)用正設(shè)計的算法 ) ?Merge： 合并子問題的解 , 形成原始問題的解 2021年 11月 12日 43 分治法的設(shè)計 divideandconquer(P) { if ( | P | = n0) adhoc(P)。 //遞歸的解各子問題 。即將一個問題分成大小相等的 k個子問題的處理方法是行之有效的。 ?劃分時間可直接得到 =D(n) ? Conquer階段的時間復(fù)雜性 ?遞歸調(diào)用 ?Conquer時間 = kT(n/m) ? Combine階段的時間復(fù)雜性 ?時間可以直接得到 =C(n) 2021年 11月 12日 46 分治法的復(fù)雜性分析 ? T(n)表示該分治法解規(guī)模為 |P|=n的問題所需的計算時間，則有： ? n/m可能不是整數(shù)。()(l o g)3()。 2021年 11月 12日 50 分析： 如果 n=1即只有一個元素，則只要比較這個元素和 x就可以確定 x是否在表中。 分析： 很顯然此問題分解出的子問題相互獨立，即在 a[i]的前面或后面查找 x是獨立的子問題，因此滿足分治法的第四個適用條件。 二分搜索技術(shù) 2021年 11月 12日 51