遞歸與分治策略第一部分

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

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

3、- 3）次。 分治方法 （Divide and Conquer）: （1）將數(shù)據(jù)集 S 均分為 S1 和 S2； （2）求解 S1 和 S2 中的最大和最小值； （3）最終的最大和最小值可以計(jì)算得到：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) ,治,分,合并,算法描述（為方便起見(jiàn)，假定 n 是 2 的指數(shù)倍，n 1）：,第2章 遞歸與分治策略,復(fù)雜度公式 T( n ) = 3n/2 2 的推導(dǎo)過(guò)程（要會(huì)處理類似的問(wèn)題）：,第2章 遞歸與分治策略,第2章 遞歸與分治策略,教學(xué)內(nèi)容和要求（講授 6 學(xué)時(shí)，2 學(xué)時(shí)上機(jī)實(shí)驗(yàn)，共 8 學(xué)時(shí)） （1）遞歸、遞歸算法的設(shè)計(jì)（Ackerman 函數(shù)、排列問(wèn)題、整數(shù)劃分問(wèn)題）（重點(diǎn)） （2）分治法的基本思想、算法效率分析（掌握） （3）二分搜索技術(shù)（熟練掌握） （4）棋盤覆蓋（理解） （5）合并排序（

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

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

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

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

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

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 ); ,算法代碼,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,定義單變量的 Ackerman 函數(shù) A(n) 為：A( n ) = A( n，n )。 定義其擬逆函數(shù)(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 的層數(shù)為 65536） 可知： ( 1 ) = 0 ( 2 ) = 1 ( 3 ) = ( 4 ) = 2 ( 5 ) = = ( 16 ) = 3 ( n )的增長(zhǎng)速度非常緩慢。 ( n )在復(fù)雜度分析中常遇到。對(duì)于通常所見(jiàn)到的正整數(shù)n，有 ( n ) 4 。但在理論上( n )沒(méi)有上界，隨著 n 的增加，它以難以想象的慢速度趨向正無(wú)窮大。,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,【例 4】 排列問(wèn)題 設(shè)計(jì)一個(gè)遞

12、歸算法生成 n 個(gè)元素 r1, r2, , rn 的全排列。 全排列：從 n 個(gè)不同元素中任取m（m n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從 n 個(gè)不同元素中取出 m 個(gè)元素的一個(gè)排列。當(dāng) m = n 時(shí)所有的排列情況叫全排列。 如 1, 2, 3 三個(gè)元素的全排列為： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 共 3！= 3 * 2 * 1 = 6 種排列,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,全排列的遞歸算法設(shè)計(jì) 從實(shí)際例子中觀察可知： （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 個(gè)元素的全排列問(wèn)題可轉(zhuǎn)化為求 2 個(gè)元素的全排列問(wèn)題。 . 推廣結(jié)論：n 個(gè)元素的全排列問(wèn)題可轉(zhuǎn)化為求 n - 1 個(gè)元素的全排列問(wèn)題（遞歸設(shè)計(jì)）。,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,全排列的遞歸算法 設(shè) R = r1, r2, , rn 是要進(jìn)行排列的 n 個(gè)元素，Ri = R - ri 。 集合 X 中元素的全排列記為 perm( X )。 (

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

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

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

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

18、pszStr ) 1 ); int main() printf( 全排列的遞歸實(shí)現(xiàn)n); char szTextStr = 123; printf(%s的全排列如下:n, szTextStr); Foo( szTextStr ); return 0; ,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,運(yùn)行結(jié)果如下：,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,【例 5】整數(shù)劃分問(wèn)題 將正整數(shù) n 表示成一系列正整數(shù)之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。 正整數(shù) n 的這種表示稱為正整數(shù) n 的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 例如正整數(shù) 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,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,再如正整數(shù) 4 有如下 5 種不同的劃分： 4； 3 + 1； 2 + 2，2 + 1 + 1； 1 + 1 + 1 + 1 注意 4 = 1 + 3 和 4 = 3 + 1 被認(rèn)為是同一個(gè)劃分。 也可以采用如下方式表示 4 的 5 個(gè)劃分： 4 , 3, 1 , 2, 2 ,

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

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

22、可以分為兩種情況： （3-1）劃分中包含 n 的情況，只有一個(gè)即 n ； （3-2）劃分中不包含 n 的情況，這時(shí)劃分中最大的數(shù)字也一定比 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 的一個(gè) m 劃分，記為 q( n, m )。 當(dāng) n = m 時(shí)， max n1, n

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

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

25、分治策略,因此可以給出求出 q( n, m ) 的遞歸函數(shù)代碼如下： 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 ); ,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,【例 6】Hanoi 塔問(wèn)題 一位法國(guó)數(shù)學(xué)家曾編寫過(guò)一個(gè)印度的古老傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的 64 片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。,漢

27、諾塔益智玩具,西安郵電大學(xué)計(jì)算機(jī)學(xué)院,第2章 遞歸與分治策略,如果考慮一下把 64 片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動(dòng)呢? 這里需要遞歸的方法。假設(shè)有 n 片，移動(dòng)次數(shù)是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 時(shí)，假如每秒鐘一次，一年 365 天有 31536000 秒，閏年 366 天有 31622400 秒，平均每年 31556952 秒，計(jì)算一下， 18446744073709551

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

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

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

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

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