經典遞歸算法輔導講解課件-藍橋杯軟件大賽輔導-技能大賽

遞歸與分治(fēnzhì)策略共六十頁將要求解的較大規(guī)模的問題(wèntí)分割成k個更小規(guī)模的子問題(wèntí)。算法總體(zǒngtǐ)思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。共六十頁算法(suànfǎ)總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠(zúgòu)小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。共六十頁算法(suànfǎ)總體思想將求出的小規(guī)模的問題的解合并為一個(yīɡè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)共六十頁自頂向下、逐步(zhúbù)分解的策略將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步(zhúbù)求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。(1)子問題應與原問題做同樣的事情，且更為簡單；(2)解決遞歸問題的策略是把一個規(guī)模比較大的問題分解為一個或若干規(guī)模比較小的問題，分別對這些比較小的問題求解，再綜合它們的結果，從而得到原問題的解。—分而治之策略（分治法）(3)這些比較小的問題的求解方法與原來問題的求解方法一樣。

共六十頁遞歸的概念(gàiniàn)直接或間接地調用自身的算法稱為遞歸算法。用函數自身給出定義的函數稱為遞歸函數。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術(jìshù)提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。共六十頁遞歸的三個條件(tiáojiàn)1、邊界條件2、遞歸前進段3、遞歸返回(fǎnhuí)段當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。共六十頁簡單(jiǎndān)的遞歸(求和)求1+2+3+…+n:邊界條件遞歸方程(fāngchéng)共六十頁簡單(jiǎndān)的遞歸(求和)publicstaticintsum(intn){if(n>1){returnn+sum(n-1);//調用遞歸方法}else{return1;//當n=1時，循環(huán)(xúnhuán)結束}共六十頁簡單(jiǎndān)的遞歸（階乘）

例1階乘函數(hánshù)

階乘函數可遞歸地定義為：邊界條件遞歸方程共六十頁簡單(jiǎndān)的遞歸（階乘）publicstaticintf(intn){

if(1==n)

return1;

else

returnn*(n-1);

}

共六十頁簡單(jiǎndān)的遞歸（階乘）共六十頁簡單(jiǎndān)的遞歸（階乘）共六十頁主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：6(1)3top返回(3)1(2)2(1)3top(4)0結束(1)遞歸調用執(zhí)行(zhíxíng)情況共六十頁簡單(jiǎndān)的遞歸（十進制轉二進制）static

voidd2b(intn){if(n==0||n==1);//System.out.print(n);//遞歸出口(chūkǒu)elsed2b(n/2);System.out.print(n%2);}共六十頁遞歸的目的(mùdì)使用遞歸的目的在于解決一種常見問題(wèntí)，即子任務只不過是開始試圖解決的相同問題(wèntí)的一個較簡單版本。共六十頁簡單的遞歸（縱向(zònɡxiànɡ)顯示整數）例子：在屏幕上以十進制打印(dǎyìn)一個非負整數，要求所有位縱向顯示在屏幕上。舉例來說1234顯示如下1234可以劃分為2個問題：縱向打印出除最后一位之外的所有位；打印最后一位。把1234記為number。共六十頁簡單的遞歸（縱向顯示(xiǎnshì)整數）應該這樣打?。?23第二步輸出4第一步需要123，可以表示為number/10。第二步表示為number%10。按照遞歸的思想(sīxiǎng)，其中一步——縱向打印number/10的所有位，是同一個縱向打印數字問題的一個比較簡單的實例。因為number/10比number少了一位，所以比較簡單，就可調用方法自身來實現(xiàn)。共六十頁簡單的遞歸（縱向(zònɡxiànɡ)顯示整數）方法(fāngfǎ)writeVertical的實現(xiàn)public

static

voidwriteVertical(intnumber){if(number<10){System.out.println(number);}else{writeVertical(number/10);System.out.println(number%10);}}共六十頁簡單的遞歸（縱向(zònɡxiànɡ)顯示整數）停止條件如果問題足夠簡單，就可以不用遞歸調用解決。對于writeVertical，這發(fā)生在number只有一位時。這種沒有任何遞歸的情況叫做停止條件或基本(jīběn)條件。在writeVertical方法中，停止條件由三行代碼實現(xiàn)：if(number<10){System.out.println(number);}共六十頁簡單(jiǎndān)的遞歸（縱向顯示整數）遞歸調用else{writeVertical(number/10);System.out.println(number%10);}writeVertical方法調用它自己去解決比較簡單的問題，即打印(dǎyìn)最后一位數字之外的所有位。共六十頁遞歸的概念(gàiniàn)對writeVertical進行擴展(kuòzhǎn)，以處理所有整數，包括負數。當輸入負號時，新方法在輸出的第一行打印負號，然后再是其他的位。怎么處理負數？打印負號，然后用-1×number把number變?yōu)檎龜怠Ｕ垏L試寫出方法superWriteVertical(intnumber)共六十頁遞歸的概念(gàiniàn)public

static

voidsuperWriteVertical(intnumber){if(number<0){System.out.println("-");superWriteVertical(-number);}else

if(number<10){System.out.println(number);}else{writeVertical(number/10);System.out.println(number%10);}}共六十頁簡單(jiǎndān)的遞歸（斐波那契）例2Fibonacci數列無窮數列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數列。它可以(kěyǐ)遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數可遞歸地計算如下：intfibonacci(intn){

if(n<=2)return1;

return

fibonacci(n-1)+fibonacci(n-2);}共六十頁簡單(jiǎndān)的遞歸（斐波那契）共六十頁簡單(jiǎndān)的遞歸（斐波那契）staticintf(intn) { if(n==1||n==2)return1;//遞歸出口(chūkǒu) returnf(n-1)+f(n-2); }

共六十頁求兩個(liǎnɡɡè)正整數m,n(m<n)的最大公約數簡單(jiǎndān)的遞歸（最大公約數）遞規(guī)定義：gcd(m,n)=gcd(n%m,m)n%m!=0gcd(m,n)=mn%m==0共六十頁簡單(jiǎndān)的遞歸（最大公約數）static

intgcd(inta,intb){if(b==0)returna;elsereturn

gcd(b,a%b);}共六十頁簡單(jiǎndān)的遞歸（最大公約數）程序從main開始，再到你定義的方法gcd，進行(jìnxíng)調用，80%50不等于0，執(zhí)行else語句，到gcd在進行(jìnxíng)調用gcd方法，不過2個參數為50和80%50的值30，50%30不等于0，繼續(xù)調用gcd方法，直到if(a%b==0)的值為TRUE為止，結果返回給intt繼續(xù)執(zhí)行剩下的語句。借用回答者：緣心風絕

80%50=30

50%30=20

30%20=10

20%10=0出遞歸

10是最大公約數。這樣比較清楚共六十頁簡單(jiǎndān)的遞歸（最大公約數2）n利用計算最大公約數的三條性質(xìngzhì)，用遞歸方法計算兩個整數的最大公約數。

n性質(xìngzhì)1：如果x>y，則x和y的最大公約數與x-y和y的最大公約數相同，即gcd(x,y)=gcd(x-y,y)

x>y

n性質(xìngzhì)2：如果y>x，則x和y的最大公約數與x和y-x的最大公約數相同，即gcd(x,y)=gcd(x,y-x)

x<y

n性質(xìngzhì)3：如果x=y，則x和y的最大公約數與x值和y值相同，即gcd(x,y)=x=y共六十頁設a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起(yīqǐ)。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。簡單(jiǎndān)的遞歸（Hanoi塔問題）共六十頁在問題規(guī)模較大時，較難找到一般的方法，因此(yīncǐ)我們嘗試用遞歸技術來解決這個問題。當n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當n＞1時，需要利用塔座c作為輔助塔座。此時若能設法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法(fāngfǎ)來做。由此可以設計出解Hanoi塔問題的遞歸算法如下。

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}簡單的遞歸（Hanoi塔問題）共六十頁簡單(jiǎndān)的遞歸（Hanoi塔問題）

有些問題的求解方法(fāngfǎ)是遞歸的，典型有漢諾塔問題求解：共六十頁漢諾塔問題(wèntí)求解盤片移動時必須遵守(zūnshǒu)以下規(guī)則：每次只能移動一個盤片；盤片可以插在A、B、C中任一塔座；不能將一個較大盤片的放在較小的盤片上。共六十頁漢諾塔問題(wèntí)求解共六十頁3.遞歸算法的設計(shèjì)方法

遞歸算法既是一種(yīzhǒnɡ)有效的算法設計方法，也是一種(yīzhǒnɡ)有效的分析問題的方法。遞歸算法求解問題的基本思想是：對于一個較為復雜的問題，把原問題分解成若干個相對簡單且類同的子問題,這樣，原問題就可遞推得到解。適宜于用遞歸算法求解的問題的充分必要條件是：（1）問題具有某種可借用的類同自身的子問題描述的性質；（2）某一有限步的子問題（也稱作本原問題）有直接的解存在。當一個問題存在上述兩個基本要素時，該問題的遞歸算法的設計方法是：（1）把對原問題的求解設計成包含有對子問題求解的形式。（2）設計遞歸出口。共六十頁例如：設計(shèjì)模擬漢諾塔問題求解過程的算法。問題描述：設有3根標號為A，B，C的柱子，在A柱上放著n個盤子，每一個都比下面的略小一點，要求把A柱上的盤子全部移到C柱上，移動的規(guī)則是：（1）一次只能移動一個盤子；（2）移動過程中大盤子不能放在小盤子上面；（3）在移動過程中盤子可以放在A，B，C的任意一個柱子上。共六十頁問題分析：可以用遞歸方法求解n個盤子的漢諾塔問題。解決方法：當n=1時，直接把圓盤從A移到C；當n>1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉化為求解n-1個圓盤的Hanoi問題，依次(yīcì)類推，直至轉化成只有一個圓盤的Hanoi問題。4個盤子漢諾塔問題的遞歸求解示意圖如圖所示。

共六十頁漢諾塔問題(wèntí)的遞歸求解示意圖

共六十頁求N階漢諾塔的遞歸算法(suànfǎ)：voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(x,n,z);/*將1號盤從x座移到z座*/(4)else{(5)hanoi(n-1,x,z,y);/*將x座上n-1個圓盤(yuánpán)移到y(tǒng)座，z座作為輔助*/(6)move(x,n,z);/*將n號盤從x座移到z座*/(7)hanoi(n-1,y,x,z);/*將y座上n-1個圓盤移到z座，x座作為輔助*/(8)}(9)}共六十頁4．遞歸過程(guòchéng)的實現(xiàn)遞歸函數被調用(diàoyòng)時，系統(tǒng)需要一個運行工作棧.系統(tǒng)的運行工作棧要保存兩類信息：（1）調用函數的返回地址；（2）調用函數的局部變量值。每一層遞歸調用所需保存的信息構成運行工作棧的一個工作記錄，在每進入下一層遞歸調用時，系統(tǒng)就建立一個新的工作記錄，并把這個工作記錄進棧；每返回一層遞歸調用，就出棧一個工作記錄。因為棧頂的工作記錄必定是當前正在運行的遞歸函數的工作記錄，所以棧頂的工作記錄也稱為活動記錄。共六十頁執(zhí)行(zhíxíng)情況：遞歸工作棧保存內容：形參n,x,y,z和返回地址其中(qízhōng)，返回地址用行編號表示nxyz返回地址共六十頁main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}3ABC03ABC02ACB63ABC02ACB61ABC63ABC02ACB6ABC123ABC共六十頁main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC0共六十頁main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0共六十頁main(){intm;printf("Inputnumberofdisks”);scanf(“%d”,&m);printf("Stepsmdisks”);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0?？?ABC02BAC8共六十頁遞歸小結(xiǎojié)優(yōu)點：結構(jiégòu)清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。共六十頁解決方法：在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調用工作棧。該方法通用性強，但本質(běnzhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實現(xiàn)遞歸函數。3、通過變換能將一些遞歸轉化為尾遞歸，從而迭代求出結果。后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。遞歸小結(xiǎojié)共六十頁練習(liànxí)使用遞歸的方式把輸入的一行字符逆序打印(dǎyìn)出來。提示：遇到‘\n’表示一行結束。共六十頁練習(liànxí)給出一種(yīzhǒnɡ)解決方式private

intindex=0;private

char[]chars;public

chargetChar(){if(index<chars.length)returnchars[index++];elsereturn'\n';}public

voidsetChars(char[]c){this.chars=c;}共六十頁練習(liànxí)public

voidreverse(){charc=getChar();if(c!='\n'){reverse();System.out.println(c);}}public

static

voidmain(String[]args){Testt=newTest();Scannersc=newScanner(System.in);Stringinput=sc.nextLine();