遞歸與分治策略第一部分

1、算法設計與分析,第2章 遞歸與分治策略,分治（Divide and Conquer）,凡治眾如治寡，分數是也。 孫子兵法,治理大軍團就象治理小部隊一樣有效，是依靠合理的組織、結構、編制。,將一個難以直接解決的大問題，合理分割成一些規(guī)模較小的相同問題，以便各個擊破，這個策略就叫分而治之（分治法）。,第2章 遞歸與分治策略,分治法是最為重要的算法設計方法之一。 主要思想是：將一個問題不斷分割成若干個小問題，然后通過對小問題的求解再生成大問題的解。 因此分治法可以分為兩個重要步驟： （1）自頂向下：將問題不斷分割成小的問題。 （2）自底而上：將小問題解決來構建大問題的解。 分治和遞歸經常同時應用在算

2、法設計中。,第2章 遞歸與分治策略,將要求解的較大規(guī)模的問題分割為 k 個較小規(guī)模的子問題。對這 k 個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為 k 個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。,第2章 遞歸與分治策略,將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。,第2章 遞歸與分治策略,【例】找一組數的最大最小數。 直接求解：需要 n - 1 次比較來求最小數（n 個數兩兩比較共需要 n 1 次），然后另外 n - 2 次比較來求最大數（除去最小值的剩下 n 1 個數兩兩比較共需要 n 2 次）?？傆嫗椋?2n

3、- 3）次。 分治方法 （Divide and Conquer）: （1）將數據集 S 均分為 S1 和 S2； （2）求解 S1 和 S2 中的最大和最小值； （3）最終的最大和最小值可以計算得到：min( S1, S2 ), max( S1, S2 )； （4）采用同樣的處理方法遞歸處理 S1 和 S2。,第2章 遞歸與分治策略,min_max(S, min, max) if |S| = 2 then min min(S) max max(S) else split S evenly into S1 and S2 min_max(S1, min1, max1) min_max(S2, mi

4、n2, max2) min min(min1, min2) max max(max1, max2) ,治,分,合并,算法描述（為方便起見，假定 n 是 2 的指數倍，n 1）：,第2章 遞歸與分治策略,復雜度公式 T( n ) = 3n/2 2 的推導過程（要會處理類似的問題）：,第2章 遞歸與分治策略,第2章 遞歸與分治策略,教學內容和要求（講授 6 學時，2 學時上機實驗，共 8 學時） （1）遞歸、遞歸算法的設計（Ackerman 函數、排列問題、整數劃分問題）（重點） （2）分治法的基本思想、算法效率分析（掌握） （3）二分搜索技術（熟練掌握） （4）棋盤覆蓋（理解） （5）合并排序（

5、理解） （6）快速排序（熟練掌握）,第2章 遞歸與分治策略,2.1 遞歸的概念 （1）直接或間接地調用自身的算法稱為遞歸算法。用函數自身給出定義的函數稱為遞歸函數。 （2）由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。 （3）分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。,第2章 遞歸與分治策略,遞歸實例 （1）數據結構本身固有遞歸特性，特別適于用遞歸描述：樹（二叉樹） 樹是由 n（n 0）個

6、結點組成的有限集合。若 n = 0，稱為空樹；若 n 0，則： （A）有一個特定的稱為根（root）的結點。它只有直接后繼，但沒有直接前驅； （B）除根結點以外的其它結點可以劃分為m（ m 0）個互不相交的有限集合T0，T1，Tm-1，每個集合Ti（i = 0, 1, , m - 1）又是一棵樹，稱為根的子樹，每棵子樹的根結點有且僅有一個直接前驅，但可以有 0 個或多個直接后繼。 由此可知，樹的定義是一個遞歸的定義，即樹的定義中又用到了樹的概念。,第2章 遞歸與分治策略,樹的實例 1 - 紅樓夢人物關系表,樹的實例 2 圖像處理類譜系,第2章 遞歸與分治策略,二叉樹是 n（n 0）個結點的有限

7、集，它或者是空集（n = 0），或者由一個根結點及兩棵不相交的左子樹和右子樹組成。,二叉樹的前序遍歷 遞歸算法,第2章 遞歸與分治策略,（2）一些問題本身沒有明顯的遞歸結構，但用遞歸技術來求解，可使設計出的算法簡捷易懂。 【例 1】階乘函數 階乘函數可遞歸地定義為：,邊界條件（一般是非遞歸定義的初始值）與遞歸方程是遞歸函數的二個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果。,西安郵電大學計算機學院,第2章 遞歸與分治策略,int factorial( int n ) if ( n = 0 ) return 1; return n * factorial( n 1 ); ,算法

8、代碼,第2章 遞歸與分治策略,【例 2】 Fibonacci 數列 無窮數列1，1，2，3，5，8，13，21，34，55，稱為 Fibonacci數列。它可以遞歸地定義為：,第2章 遞歸與分治策略,第 n 個 Fibonacci 數可遞歸地計算如下： int fibonacci( int n ) if (n = 1) return 1; return fibonacci( n 1 ) + fibonacci( n 2 ); ,算法代碼,西安郵電大學計算機學院,第2章 遞歸與分治策略,【例 3】 Ackerman 函數 當一個函數及它的一個變量是由函數自身定義時，稱這個函數是雙遞歸函數。 Ac

9、kerman 函數 A(n，m) 有 2 個獨立的整型變量 m = 0 和 n = 0，定義如下：,西安郵電大學計算機學院,第2章 遞歸與分治策略,Ackerman 函數的特點：“階乘函數”和“Fibonacci 數列”都可以找到相應的非遞歸方式定義，如下：,Ackerman 函數卻無法找到非遞歸的定義。,西安郵電大學計算機學院,第2章 遞歸與分治策略,Ackerman 函數 A ( n，m ) 的自變量 m 的每一個值都定義了一個單變量函數：,西安郵電大學計算機學院,第2章 遞歸與分治策略,西安郵電大學計算機學院,第2章 遞歸與分治策略,Ackerman 函數總結如下：,西安郵電大學計算機學

10、院,第2章 遞歸與分治策略,int Ackerman( int n, int m ) if ( m = 0) if ( n = 1 ) return 1; else return ( n + 2 ); else if( n = 0 ) return 1; else return Ackerman( Ackerman( n - 1, m ), m - 1 ); ,算法代碼,西安郵電大學計算機學院,第2章 遞歸與分治策略,定義單變量的 Ackerman 函數 A(n) 為：A( n ) = A( n，n )。 定義其擬逆函數(n)為：( n ) = min kA( k ) n 。即 ( n ) 是

11、使 n A( k )成立的最小的 k 值。 A( 0 ) = 1 A( 1 ) = 2 A( 2 ) = 4 A( 3 ) = 16 A( 4 ) = 2 多重冪（其中 2 的層數為 65536） 可知： ( 1 ) = 0 ( 2 ) = 1 ( 3 ) = ( 4 ) = 2 ( 5 ) = = ( 16 ) = 3 ( n )的增長速度非常緩慢。 ( n )在復雜度分析中常遇到。對于通常所見到的正整數n，有 ( n ) 4 。但在理論上( n )沒有上界，隨著 n 的增加，它以難以想象的慢速度趨向正無窮大。,西安郵電大學計算機學院,第2章 遞歸與分治策略,【例 4】 排列問題 設計一個遞

12、歸算法生成 n 個元素 r1, r2, , rn 的全排列。 全排列：從 n 個不同元素中任取m（m n）個元素，按照一定的順序排列起來，叫做從 n 個不同元素中取出 m 個元素的一個排列。當 m = n 時所有的排列情況叫全排列。 如 1, 2, 3 三個元素的全排列為： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 共 3！= 3 * 2 * 1 = 6 種排列,西安郵電大學計算機學院,第2章 遞歸與分治策略,全排列的遞歸算法設計 從實際例子中觀察可知： （1） 1 的全排列為：1 （2） 1, 2 的全排列為：1, 2 2, 1 （3）

13、1, 2, 3 的全排列為： 1, 2, 3 1, 3, 2 2, 3 的全排列加上 1 所得 2, 1, 3 2, 3, 1 1, 3 的全排列加上 2 所得 3, 1, 2 3, 2, 1 1, 2 的全排列加上 3 所得 即：3 個元素的全排列問題可轉化為求 2 個元素的全排列問題。 . 推廣結論：n 個元素的全排列問題可轉化為求 n - 1 個元素的全排列問題（遞歸設計）。,西安郵電大學計算機學院,第2章 遞歸與分治策略,全排列的遞歸算法 設 R = r1, r2, , rn 是要進行排列的 n 個元素，Ri = R - ri 。 集合 X 中元素的全排列記為 perm( X )。 (

14、 ri )perm( X ) 表示在全排列 perm( X ) 的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：,當 n = 1 時，perm( R ) = ( r )，其中 r 是集合 R 中唯一的元素； 當 n 1 時，perm( R ) 由 ( r1 )perm(R1)，( r2 )perm(R2)，( rn )perm(Rn)構成。,西安郵電大學計算機學院,第2章 遞歸與分治策略,全排列的遞歸算法說明示例 設 R = 1, 2, 3 ，則 n = 3，根據上述算法，產生的全排列為： 1 2, 3 2 3 3 2 （即對集合 2, 3 繼續(xù)執(zhí)行遞歸算法，下同） 2 1, 3

15、1 3 3 1 3 1, 2 1 2 2 1 即 R = 1, 2, 3 產生的全排列為： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1,西安郵電大學計算機學院,第2章 遞歸與分治策略,全排列在 IT 公司的筆試面試中比較熱門，百度、迅雷等大公司的校園招聘以及程序員和軟件設計師的考試中都考過此題。 如下面的百度、迅雷校招筆試題中的“全排列”： 【題目】用 C+ 寫一個函數, 如 Foo( const char *str ), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba。 【分析】

16、根據上述描述的算法，可知全排列的遞歸實現算法的規(guī)律是“全排列是從第一個數字起每個數分別與它后面的數字交換”。這樣根據上述算法可以 寫出示例代碼如下：,西安郵電大學計算機學院,第2章 遞歸與分治策略,/ 全排列的遞歸實現（假定集合中的各個元素互不相同） #include #include void Swap( char *a, char *b ) char t = *a; *a = *b; *b = t; ,西安郵電大學計算機學院,第2章 遞歸與分治策略,/ k 表示當前選取到第幾個數, m表示共有多少數. void AllRange(char *pszStr, int k, int m) if

17、 ( k = m ) static int s_i = 1; printf( 第%3d個排列t%sn, s_i+, pszStr); else for (int i = k; i = m; i+) / 第 i 個數分別與它后面的數字交換就能得到新的排列 Swap( pszStr + k, pszStr + i ); AllRange( pszStr, k + 1, m ); Swap( pszStr + k, pszStr + i ); ,西安郵電大學計算機學院,第2章 遞歸與分治策略,void Foo( char *pszStr ) AllRange( pszStr, 0, strlen(

18、pszStr ) 1 ); int main() printf( 全排列的遞歸實現n); char szTextStr = 123; printf(%s的全排列如下:n, szTextStr); Foo( szTextStr ); return 0; ,西安郵電大學計算機學院,第2章 遞歸與分治策略,運行結果如下：,西安郵電大學計算機學院,第2章 遞歸與分治策略,【例 5】整數劃分問題 將正整數 n 表示成一系列正整數之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。 正整數 n 的這種表示稱為正整數 n 的劃分。求正整數n的不同劃分個數。 例如正整數 6 有如

19、下 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,西安郵電大學計算機學院,第2章 遞歸與分治策略,再如正整數 4 有如下 5 種不同的劃分： 4； 3 + 1； 2 + 2，2 + 1 + 1； 1 + 1 + 1 + 1 注意 4 = 1 + 3 和 4 = 3 + 1 被認為是同一個劃分。 也可以采用如下方式表示 4 的 5 個劃分： 4 , 3, 1 , 2, 2 ,

20、2, 1, 1 , 1, 1, 1, 1 ;,第2章 遞歸與分治策略,將正整數 n 的不同劃分個數稱為正整數 n 的劃分數，記作 p( n )。如上述 p( 6 ) = 11。 將正整數 n 表示成一系列正整數之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。正整數 n 的這種表示稱為正整數 n 的劃分。 如果 max n1, n2, , nk = m，則稱劃分 n = n1 + n2 + + nk 屬于 n 的一個 m 劃分，記為 q( n, m )。顯然對于正整數劃分問題而言，m = n，即計算 q( n, n ) 的值。 前面的幾個例子中，問題本身都具有比

21、較明顯的遞歸關系，因而容易用遞歸函數直接求解。在本例中，如果設 p( n ) 為正整數n的劃分數，則難以找到遞歸關系。需要借助 q( n, m ) 建立遞歸關系。,西安郵電大學計算機學院,第2章 遞歸與分治策略,在這里考慮一般的 q( n, m ) 的計算，根據 n 和 m 的關系，考慮以下幾種情況： （1）當 n = 1 時，不論 m 的值為多少( m 0 )，只有一種劃分即 1 ; （2）當 m = 1 時，不論 n 的值為多少，只有一種劃分即 n 個 1， 1, 1, 1, ., 1 ;,西安郵電大學計算機學院,第2章 遞歸與分治策略,（3） 當 n = m 時，根據劃分中是否包含 n，

22、可以分為兩種情況： （3-1）劃分中包含 n 的情況，只有一個即 n ； （3-2）劃分中不包含 n 的情況，這時劃分中最大的數字也一定比 n 小，即 n 的 所有 ( n 1 ) 劃分。（ m = n 1，即包含所有max n1, n2, , nk = n 1 的情況） 因此 q( n, m ) = q( n, n ) = 1 + q( n, n 1 ); 注意：q( n, m ) 中 m 的定義為： 如果 max n1, n2, , nk = m，則稱劃分 n = n1 + n2 + + nk 屬于 n 的一個 m 劃分，記為 q( n, m )。 當 n = m 時， max n1, n

23、2, , nk = m = n，也即 n1, n2, , nk 中的最大值小于或者等于 n 都是可以的，所以上述（3-2）是成立的。,第2章 遞歸與分治策略,（4）當 n m 時，根據劃分中是否包含最大值 m，可以分為兩種情況： （5-1）劃分中包含 m 的情況，即 m, n1, n2, ., ni , 其中 n1, n2, ., ni 的和 為 n - m，可能再次出現 m（ max n1, n2, , ni = m 是可以成立的）， 因此是（ n - m）的 m 劃分，因此這種劃分個數為 q( n - m, m ); （5-2）劃分中不包含 m 的情況，則劃分中所有值都比 m ?。?m），

24、即 n 的 ( m 1 ) 劃分（一定滿足max n1, n2, , nk = m - 1），個數為 q( n, m 1 ); 因此 q( n, m ) = q( n - m, m ) + q( n, m 1 );,西安郵電大學計算機學院,第2章 遞歸與分治策略,綜上可知：上面的結論具有遞歸定義特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，將會轉換為情況（5）。而情況（5）為通用情況，屬于遞推的方法，其本質主要是通過減小 m 以達到回歸條件，從而解決問題。 遞推表達式如下：,正整數 n 的劃分數 p( n ) = q( n, n )。,西安郵電大學計算機學院,第2章 遞歸與

25、分治策略,因此可以給出求出 q( n, m ) 的遞歸函數代碼如下： unsigned long GetIntegerPartitionCount( int n, int m ) if ( n = 1 | m = 1 ) return 1; else if ( n m ) return GetIntegerPartitionCount( n, n ); else if ( n = m ) return 1 + GetIntegerPartitionCount( n, m 1 ); else return GetIntegerPartitionCount( n, m 1 ) + GetInteg

26、erPartitionCount( n - m, m ); ,西安郵電大學計算機學院,第2章 遞歸與分治策略,【例 6】Hanoi 塔問題 一位法國數學家曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的 64 片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。,漢

27、諾塔益智玩具,西安郵電大學計算機學院,第2章 遞歸與分治策略,如果考慮一下把 64 片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動呢? 這里需要遞歸的方法。假設有 n 片，移動次數是f( n ).顯然 f( 1 )=1, f( 2 ) = 3, f( 3 ) = 7，且 f( k+1 ) = 2 * f( k ) + 1。此后不難證明 f( n ) = 2 n - 1。n = 64 時，假如每秒鐘一次，一年 365 天有 31536000 秒，閏年 366 天有 31622400 秒，平均每年 31556952 秒，計算一下， 18446744073709551

28、615 / 31556952 = 584554049253.855年 這表明移完這些金片需要5845億年以上，而地球存在至今不過 45 億年，太陽系的預期壽命據說也就是數百億年。真的過了5845億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。,西安郵電大學計算機學院,第2章 遞歸與分治策略,Hanoi 塔問題的標準描述： 設 a, b, c 是 3 個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則： 規(guī)

29、則 1：每次只能移動 1 個圓盤； 規(guī)則 2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則 3：在滿足移動規(guī)則 1 和 2 的前提下，可將圓盤移至 a,b,c 中任一塔座上。,Hanoi 塔的動態(tài)演示,西安郵電大學計算機學院,第2章 遞歸與分治策略,算法設計： （1）當 n = 1 時，只要將編號為 1 的圓盤從塔座 a 直接移到塔座 b 上即可； （2）當 n 1 時，需要利用塔座 c 作為輔助塔座。此時要設法將 n - 1 個較小的圓盤依照規(guī)則從 a 移至 c 上，然后將剩下的最大塔座從 a 移至 b 上。最后設法將 n - 1 個較小的圓盤依照規(guī)則從 c 移至 b 上。 由此可

30、見，n 個圓盤的移動問題可分解為兩次 n - 1 個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設計出算法如下：,西安郵電大學計算機學院,第2章 遞歸與分治策略,void hanoi( int n, int a, int b, int c ) / 將塔座 a 上的 n 個圓盤依規(guī)則移至塔座 b 上， / 以塔座 c 作為輔助塔座 if ( n 0 ) hanoi( n - 1, a, c, b ); move( a, b ); / 將塔座 a 上編號為 n 的圓盤移至塔座 b 上 hanoi( n - 1, c, b, a ); ,西安郵電大學計算機學院,第2章 遞歸與分治策略,遞歸

31、小結 優(yōu)點：結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。 缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。 解決方法：在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。 （1）采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調用工作棧。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 （2）用遞推來實現遞歸函數。這種方法在時空復雜度上均有較大改善，但其適用范圍有限。,西安郵電大學計算機學院,第2章 遞歸與分治策略,2.2 分治法的基本思想 分治法的基本思想是將一個規(guī)模為 n

32、的問題分解為 k 個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。 分治法所能解決的問題一般具有以下幾個特征： （1）該問題規(guī)模縮小到一定的程度就可以容易地解決； 因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。,西安郵電大學計算機學院,第2章 遞歸與分治策略,（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有“最優(yōu)子結構性質”。 這條特征是應用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用。 （3）利用該問題分解出的子問題的解可以合并為該問題的解。 能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。,西安郵電大學計算機學院,第2章 遞歸與分治策略,（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。,西安郵電大學計算機學院,第2章