全國軟件設(shè)計(jì)大賽培訓(xùn)

第二講：遞推與遞歸內(nèi)容提要遞推法遞歸法遞推法遞推法是指由遞推公式逐步推演得出問題解的方法。遞推法是一種簡單的思想。遞推法適合求解可以用遞推公式描述出來的問題，一般來講，遞推法求解問題是線性的負(fù)責(zé)性的。遞推法求解斐波那契數(shù)列：f(0)=1,f(1)=1f(n+2)=f(n+1)+f(n)(n>=0)程序代碼

f[0]=1;f[1]=1;for(inti=0;i<n-1;i++) f[i+2]=f[i+1]+f[i];習(xí)題1有一只經(jīng)過訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。請編程計(jì)算蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。其中，蜂房的結(jié)構(gòu)如下所示。習(xí)題2：樓梯的走法：有一樓梯共M級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？內(nèi)容提要遞推法遞歸法遞歸法直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。遞歸法例1階乘函數(shù)

階乘函數(shù)可遞歸地定義為：遞歸基始遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計(jì)算后得出結(jié)果。遞歸法階乘函數(shù)的程序：longfac(intn){if(n==0)return1;elsereturnn*fac(n-1);}遞歸法例2Ackerman函數(shù)當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：遞歸法例3Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。遞歸法漢諾塔問題的程序：voidhanoi(intn,chara,charb,charc){

if(n>0){

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

move(a,b);

hanoi(n-1,c,b,a);}}voidmove（a,b）{ println(“%c%c”,a,b);}遞歸法優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時間還是占用的存儲空間都比非遞歸算法要多。遞歸法在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實(shí)現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限習(xí)題3：寫一個進(jìn)制轉(zhuǎn)換的函數(shù):convert(intn)：輸入一個十進(jìn)制數(shù)n，將它轉(zhuǎn)換成R