第2章遞歸算法ppt課件

1、算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法遞歸算法(Recursion)l 本章內(nèi)容本章內(nèi)容l 遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制l 遞歸化為非遞歸遞歸化為非遞歸(難點(diǎn)難點(diǎn))l 遞歸算法舉例遞歸算法舉例l 遞歸算法復(fù)雜性的計(jì)算遞歸算法復(fù)雜性的計(jì)算(重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn))遞歸算法遞歸算法算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法遞歸(Recursion)定義l直接或間接地調(diào)用本身的算法稱為遞歸算法直接或間接地調(diào)用本身的算法稱為遞歸算法l直接或間接調(diào)用本身的函數(shù)稱為遞歸函數(shù)直接或間接調(diào)用本身的函數(shù)稱為遞歸函數(shù)l尾遞歸是指遞歸調(diào)用的語(yǔ)句在遞歸函數(shù)的最后一尾遞歸是指遞歸調(diào)用的語(yǔ)句在遞歸函數(shù)的

2、最后一句句l遞歸算法的特點(diǎn)：遞歸算法的特點(diǎn)：l用于處理一類遞歸定義的問(wèn)題用于處理一類遞歸定義的問(wèn)題l算法易于實(shí)現(xiàn)，簡(jiǎn)單明了算法易于實(shí)現(xiàn)，簡(jiǎn)單明了遞歸算法遞歸算法算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法1.遞歸算法的實(shí)現(xiàn)機(jī)制l遞歸算法經(jīng)過(guò)子程序/函數(shù)來(lái)實(shí)現(xiàn)l子程序調(diào)用的方式l參數(shù)傳送和前往值的傳送l子程序調(diào)用的內(nèi)部操作遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法1.1 子程序的調(diào)用方式遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制1STACK1/2STACK算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制12STACK12STA

3、CK算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法子程序/函數(shù)調(diào)用方式l關(guān)鍵：關(guān)鍵： l用棧保管前往地址用棧保管前往地址l用存放器保管前往地址用存放器保管前往地址(某些嵌入式處置器某些嵌入式處置器)遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法1.2參數(shù)傳送和前往值的回傳l參數(shù)傳送參數(shù)傳送l按值的傳送按值的傳送(值調(diào)用值調(diào)用)l按地址的傳送按地址的傳送(援用調(diào)用援用調(diào)用)l兩次值的傳送兩次值的傳送l地址的傳送地址的傳送l函數(shù)的前往值函數(shù)的前往值l經(jīng)過(guò)存放器傳送經(jīng)過(guò)存放器傳送(AX/EAX)l經(jīng)過(guò)全局變量的傳送經(jīng)過(guò)全局變量的傳送l例如例如 C+中的援用類型，一

4、些腳本言語(yǔ)的援用中的援用類型，一些腳本言語(yǔ)的援用變量類型都是按地址傳送的例子變量類型都是按地址傳送的例子遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法參數(shù)的傳送l值參數(shù)值參數(shù) (value parameter) 用于輸入?yún)?shù)的用于輸入?yún)?shù)的傳送。一個(gè)值參數(shù)相當(dāng)于一個(gè)部分變量，傳送。一個(gè)值參數(shù)相當(dāng)于一個(gè)部分變量，只是它的初始值來(lái)自為該形參傳送的實(shí)參。只是它的初始值來(lái)自為該形參傳送的實(shí)參。對(duì)值參數(shù)的修正不影響為該形參傳送的實(shí)對(duì)值參數(shù)的修正不影響為該形參傳送的實(shí)參。參。l援用參數(shù)援用參數(shù) (reference parameter) 用于輸入用于輸入和輸出參數(shù)傳送。

5、援用參數(shù)與實(shí)參變量表和輸出參數(shù)傳送。援用參數(shù)與實(shí)參變量表示同一存儲(chǔ)位置，對(duì)值參數(shù)的修正直接影示同一存儲(chǔ)位置，對(duì)值參數(shù)的修正直接影響為該形參傳送的實(shí)參。響為該形參傳送的實(shí)參。 遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法1.3子程序調(diào)用的內(nèi)部操作l Caller: (主調(diào)函數(shù)主調(diào)函數(shù))l 在棧頂為方式參數(shù)開(kāi)辟空間在棧頂為方式參數(shù)開(kāi)辟空間l 計(jì)算實(shí)參值并賦給棧頂?shù)男螀⒂?jì)算實(shí)參值并賦給棧頂?shù)男螀 前往地址入棧前往地址入棧l 指令流轉(zhuǎn)向被調(diào)函數(shù)的入口指令流轉(zhuǎn)向被調(diào)函數(shù)的入口l Callee:(被調(diào)函數(shù)被調(diào)函數(shù))l 初始化：初始化：l 部分量保管在堆棧中部分量保管

6、在堆棧中l(wèi) 從堆棧中取出形參運(yùn)算從堆棧中取出形參運(yùn)算l 前往：前往：l 將前往值保管到回傳變量中將前往值保管到回傳變量中l(wèi) 從棧中取出前往地址從棧中取出前往地址l 指令流轉(zhuǎn)到前往地址處繼續(xù)執(zhí)行程序指令流轉(zhuǎn)到前往地址處繼續(xù)執(zhí)行程序遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法1.4遞歸程序的內(nèi)部實(shí)現(xiàn)l內(nèi)部實(shí)現(xiàn)和函數(shù)調(diào)用類似，代碼只需一份內(nèi)部實(shí)現(xiàn)和函數(shù)調(diào)用類似，代碼只需一份l優(yōu)點(diǎn)：簡(jiǎn)單明了優(yōu)點(diǎn)：簡(jiǎn)單明了l構(gòu)造明晰，可讀性強(qiáng)構(gòu)造明晰，可讀性強(qiáng)l容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性l缺陷：運(yùn)轉(zhuǎn)效率較低缺陷：運(yùn)轉(zhuǎn)效率較低l入入/出棧次數(shù)

7、多，影響計(jì)算時(shí)間出棧次數(shù)多，影響計(jì)算時(shí)間l對(duì)系統(tǒng)棧的空間占用大，遞歸層次多時(shí)，對(duì)系統(tǒng)棧的空間占用大，遞歸層次多時(shí)，容易導(dǎo)致棧溢出容易導(dǎo)致棧溢出l同一個(gè)函數(shù)多次的反復(fù)調(diào)用，開(kāi)銷大同一個(gè)函數(shù)多次的反復(fù)調(diào)用，開(kāi)銷大遞歸算法的實(shí)現(xiàn)機(jī)制遞歸算法的實(shí)現(xiàn)機(jī)制算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法2.遞歸化為非遞歸l 直接遞歸化為非遞歸直接遞歸化為非遞歸(迭代迭代)l 原那么：原那么：l 在過(guò)程的開(kāi)場(chǎng)部分，初始化用戶棧在過(guò)程的開(kāi)場(chǎng)部分，初始化用戶棧(替代系統(tǒng)棧替代系統(tǒng)棧)，添加，添加一個(gè)全局變量一個(gè)全局變量retvalue用于保管前往值用于保管前往值l 建立標(biāo)號(hào)：分別在過(guò)程的第一條可執(zhí)行語(yǔ)句處、每個(gè)遞

8、建立標(biāo)號(hào)：分別在過(guò)程的第一條可執(zhí)行語(yǔ)句處、每個(gè)遞歸調(diào)用途建立標(biāo)號(hào)，依次為：歸調(diào)用途建立標(biāo)號(hào)，依次為：L0,L1,L2,，做為入，做為入口地址和前往地址口地址和前往地址l 消去遞歸調(diào)用：部分變量、形參、前往地址入棧消去遞歸調(diào)用：部分變量、形參、前往地址入棧,方式方式參數(shù)賦值，參數(shù)賦值，goto語(yǔ)句到語(yǔ)句到L0l 修正函數(shù)的前往部分：修正函數(shù)的前往部分：l 用戶棧為空，前往用戶棧為空，前往l 前往值保管到全局變量中，同時(shí)將援用參數(shù)賦給棧頂?shù)那巴当９艿饺肿兞恐?，同時(shí)將援用參數(shù)賦給棧頂?shù)南鄳?yīng)變量相應(yīng)變量l 取出前往地址，恢復(fù)現(xiàn)場(chǎng)。取出前往地址，恢復(fù)現(xiàn)場(chǎng)。(即恢復(fù)主調(diào)函數(shù)的部分量、即恢復(fù)主調(diào)函數(shù)的部

9、分量、參數(shù)等參數(shù)等,留意棧的平衡留意棧的平衡)l 轉(zhuǎn)向前往地址處執(zhí)行轉(zhuǎn)向前往地址處執(zhí)行2.遞歸化為非遞歸遞歸化為非遞歸算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法int GCD(unsigned int a, unsigned int b)int res ;if( a b )res = GCD(b,a);else if( b = 0 )res = a;elseres = GCD(b,a%b);return res;2.遞歸化為非遞歸遞歸化為非遞歸a = b*r + q其中其中0=qb那么：那么：(a,b) = (b,q) = = = ( D, 0)D 為為a,b的最大公因數(shù)的最大公因數(shù)算法設(shè)

10、計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法int GCD(unsigned int a, unsigned int b) CStack stack; int retvalue,retaddr;int res ;L0:if( a b )res = GCD(b,a);L1: ;else if( b = 0 )res = a;elseres = GCD(b,a%b);L2: ;return res; 建立用戶棧建立用戶棧 設(shè)置暫時(shí)變量設(shè)置暫時(shí)變量-(前往前往值和前往地址值和前往地址) 建立標(biāo)號(hào)建立標(biāo)號(hào)(入口地址入口地址和前往地址列表和前往地址列表)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法int

11、GCD(unsigned int a, unsigned int b) CStack stack; int retvalue,retaddr;int res ; stack.push(a);stack.push(b);L0:b=stack.pop();a=stack.pop();/從堆棧取參數(shù)從堆棧取參數(shù)if( a b )res = GCD(b,a);L1: ;else if( b = 0 )res = a;elseres = GCD(b,a%b);L2: ;return res;從堆棧中取從堆棧中取參數(shù)參數(shù)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法if( a m,那么那么knap(m,n

12、) knap(m,n-1)否那么否那么mn m ) return knap(m,n-1);if( knap( m-mn,n-1 ) return true;return knap(m,n-1);3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法HanoiHanoi塔問(wèn)題塔問(wèn)題漢諾塔漢諾塔Tower of Hanoi游戲聽(tīng)說(shuō)來(lái)源于布拉瑪神廟。游戲的游戲聽(tīng)說(shuō)來(lái)源于布拉瑪神廟。游戲的安裝如下圖圖上以安裝如下圖圖上以3個(gè)金片例，底座上有三根金的針，第一個(gè)金片例，底座上有三根金的針，第一根針上放著從大到小根針上放著從大到小64個(gè)金片。游戲的目的是把一切金片從第個(gè)金片。游戲的目的是

13、把一切金片從第一根針移到第三根針上，第二根針作為中間過(guò)渡。每次只能挪一根針移到第三根針上，第二根針作為中間過(guò)渡。每次只能挪動(dòng)一個(gè)金片，并且大的金片不能壓在小的金片上面。該游戲的動(dòng)一個(gè)金片，并且大的金片不能壓在小的金片上面。該游戲的終了就標(biāo)志著終了就標(biāo)志著“世界末日的到來(lái)。世界末日的到來(lái)。3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)ABC三個(gè)金片的三個(gè)金片的HanoiHanoi游戲的安裝游戲的安裝算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法分析：分析：游戲中金片挪動(dòng)是一個(gè)很繁瑣的過(guò)程。經(jīng)過(guò)計(jì)算，對(duì)于游戲中金片挪動(dòng)是一個(gè)很繁瑣的過(guò)程。經(jīng)過(guò)計(jì)算，對(duì)于64個(gè)金個(gè)金片至少需求挪動(dòng)片至少需求挪動(dòng) 264 1 = 1.6

14、1019 次次 。 無(wú)妨用無(wú)妨用A表示被挪動(dòng)金片所在的針源，表示被挪動(dòng)金片所在的針源，C表示目的針，表示目的針，B表表示過(guò)渡針。對(duì)于把示過(guò)渡針。對(duì)于把nn1個(gè)金片從第一根針個(gè)金片從第一根針A上移到第三根針上移到第三根針C的問(wèn)題可以分解成如下步驟：的問(wèn)題可以分解成如下步驟：1將將n-1個(gè)金片從個(gè)金片從A經(jīng)過(guò)經(jīng)過(guò)C挪動(dòng)到挪動(dòng)到B。2將第將第n個(gè)金片挪動(dòng)到個(gè)金片挪動(dòng)到C。3再將再將n-1個(gè)金片從個(gè)金片從B經(jīng)過(guò)經(jīng)過(guò)A挪動(dòng)到挪動(dòng)到C。 這樣就把挪動(dòng)這樣就把挪動(dòng)n個(gè)金片的問(wèn)題轉(zhuǎn)化為挪動(dòng)個(gè)金片的問(wèn)題轉(zhuǎn)化為挪動(dòng)n-1個(gè)金片的問(wèn)題，個(gè)金片的問(wèn)題，即挪動(dòng)即挪動(dòng)n個(gè)金片的問(wèn)題可用挪動(dòng)個(gè)金片的問(wèn)題可用挪動(dòng)n-1個(gè)金片

15、的問(wèn)題遞歸描畫，以此個(gè)金片的問(wèn)題遞歸描畫，以此類推，可轉(zhuǎn)化為挪動(dòng)一個(gè)金片的問(wèn)題。顯然，一個(gè)金片就可以直類推，可轉(zhuǎn)化為挪動(dòng)一個(gè)金片的問(wèn)題。顯然，一個(gè)金片就可以直接挪動(dòng)。接挪動(dòng)。3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)ABC三個(gè)金片的三個(gè)金片的HanoiHanoi游戲的安裝游戲的安裝算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法void hanoi(int n, int a, int b, int c) if (n 1) hanoi(n-1, a, c, b); move(n,a,b); hanoi(n-1, b, a, c); else move(n,a,b); /終了條件 3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法

16、設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法棋子挪動(dòng)問(wèn)題描畫：有問(wèn)題描畫：有2n個(gè)棋子排成一行，白子用個(gè)棋子排成一行，白子用0代表，黑子代表，黑子用用1代表。代表。n=5的形狀為：的形狀為： 0000011111_ _ (右邊至少兩個(gè)空位右邊至少兩個(gè)空位)挪動(dòng)規(guī)那么：挪動(dòng)規(guī)那么：(1)每次必需挪動(dòng)相鄰的兩個(gè)棋子，這兩個(gè)棋子不能互換每次必需挪動(dòng)相鄰的兩個(gè)棋子，這兩個(gè)棋子不能互換位置位置(2)挪動(dòng)的顏色不限，挪動(dòng)的方向不限挪動(dòng)的顏色不限，挪動(dòng)的方向不限要求：要求：最后成為最后成為 _ _ 0101010101 的形狀的形狀(中間無(wú)空格中間無(wú)空格)。3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和

17、分析 遞歸算法遞歸算法 空格在任何地方都是可等價(jià)變換的空格在任何地方都是可等價(jià)變換的 問(wèn)題規(guī)模為問(wèn)題規(guī)模為n和為和為n-1有類似的地方嗎？有類似的地方嗎？ 000000111111_ _ (問(wèn)題的規(guī)模問(wèn)題的規(guī)模n) 0000011111_ _01 (問(wèn)題的規(guī)模問(wèn)題的規(guī)模 n-1,?) 結(jié)論：結(jié)論： (1)規(guī)模為規(guī)模為n的問(wèn)題可以經(jīng)過(guò)兩步的挪動(dòng)變成規(guī)模為的問(wèn)題可以經(jīng)過(guò)兩步的挪動(dòng)變成規(guī)模為n-1的問(wèn)題的問(wèn)題! (2)初值遞歸的終了條件初值遞歸的終了條件n=?可以解可以解3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法1.初值的判別：初值的判別：n=2, 0011_ _ 0

18、_ _ 101 010_ _ 1 , 無(wú)解無(wú)解n=3, 無(wú)解無(wú)解n=4: 0 0 0 0 1 1 1 1 _ _ 0 0 0 _ _ 1 1 1 0 1 0 0 0 1 0 1 1 _ _ 1 0 _ _ 1 0 1 1 0 0 1 0 1 0 1 0 1 _ _ 0 1 _ _ 0 1 0 1 0 1 0 13.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法2.遞推關(guān)系式遞推關(guān)系式:0 0 0 . . . 0 0 0 1 1 1 . . . 1 1 1 _ _ (n)0 0 0 . . . 0 0 _ _ 1 1 . . . 1 1 1 0 10 0 0 . . .

19、0 0 1 1 1 1 . . . 1 _ _ 0 1 (n-1)對(duì)對(duì)n-1個(gè)棋子進(jìn)展遞歸的挪動(dòng)直到個(gè)棋子進(jìn)展遞歸的挪動(dòng)直到n=4為止為止3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法3.算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：(對(duì)棋子的位置進(jìn)展編號(hào)，從對(duì)棋子的位置進(jìn)展編號(hào)，從1,2,2n,2n+1,2n+2)void chess(int n) /n為挪動(dòng)的棋子數(shù)，為挪動(dòng)的棋子數(shù)，n4 if( n = 4 ) /遞歸出口遞歸出口 else if( n4 ) /進(jìn)入遞歸進(jìn)入遞歸 move_to(n,n+1, 2n+1,2n+2); move_to(2n-1,2n,n,n+1); ches

20、s(n-1); 3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法4.思索：思索：假設(shè)棋子的挪動(dòng)規(guī)那么改為每次挪動(dòng)相鄰的假設(shè)棋子的挪動(dòng)規(guī)那么改為每次挪動(dòng)相鄰的3個(gè)個(gè)(4,5,)棋子，其他條件不變，那么如何處理此問(wèn)題？棋子，其他條件不變，那么如何處理此問(wèn)題？遞歸關(guān)系式的推導(dǎo)遞歸關(guān)系式的推導(dǎo)初值的判別初值的判別(n=?有解有解)算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法n個(gè)元素的全陳列N=1, 輸出輸出 1N=2, 輸出輸出 1,2 2,1N=3, 輸出輸出 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,

21、2,1處理：處理：遞推關(guān)系式遞推關(guān)系式初始值初始值(遞歸的出口遞歸的出口)算法實(shí)現(xiàn)算法實(shí)現(xiàn)3.遞歸算法設(shè)計(jì)遞歸算法設(shè)計(jì)算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法a = 1,2.3,4,n;/對(duì)對(duì)ak an 進(jìn)展全陳列進(jìn)展全陳列void Range(a,k,n) if( k = n ) Print(a); /輸出陳列輸出陳列 else for(i=k;i2時(shí)時(shí), H(n) = H(n-1) + H(n-2)下面分析時(shí)間復(fù)雜度：設(shè)為下面分析時(shí)間復(fù)雜度：設(shè)為T(n)C, n2時(shí)時(shí)T(n)=4.遞歸關(guān)系式計(jì)算遞歸關(guān)系式計(jì)算算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法T(n) 2T(n-1) 22

22、T(n-2) 2n-1T(1) = O(2n)4.遞歸關(guān)系式計(jì)算遞歸關(guān)系式計(jì)算算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法4.2時(shí)間復(fù)雜度的計(jì)算-迭代法0, n = 12T(n/2) + cn, n1T(n) = T(n) = 2T(n/2) +cn = 2(2T(n/4) +c*n/2) +cn = 22T(n/4) + cn + cn = 23T(n/23) + cn + cn +cn = = 2kT(n/2k) + cn + cn + + cn = 2k*0 + kcn = cnlog2n = O(nlogn)K個(gè)個(gè)設(shè)設(shè) n/2k = 1,那么那么 k = log2n4.遞歸關(guān)系式計(jì)算

23、遞歸關(guān)系式計(jì)算求求O(T(n)=?算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法lrecursion tree 遞推樹、迭代樹遞推樹、迭代樹4.遞歸關(guān)系式計(jì)算遞歸關(guān)系式計(jì)算算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法算法設(shè)計(jì)和分析算法設(shè)計(jì)和分析 遞歸算法遞歸算法漢諾塔漢諾塔Tower of Hanoi問(wèn)題：?jiǎn)栴}：假設(shè)假設(shè)move所需的時(shí)間為所需的時(shí)間為1，那么其時(shí)間復(fù)雜度：，那么其時(shí)間復(fù)雜度：1, n = 12T(n-1) + 1, n1T(n) = T(n) = 2T(n-1) + 1 = 2 2T(n-2)+1 + 1 = 22T(n-2) + 2 + 1 = 23T(n-3) + 22 + 2 + 1 = = 2n-1T(1) + 2n-2 + + 23 + 22 + 2 + 1 = 2n-1 + 2n-2