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