第1講-遞推與迭代課件

1、1遞推概述遞推概述遞推數(shù)列遞推數(shù)列應(yīng)用遞推求解應(yīng)用題應(yīng)用遞推求解應(yīng)用題遞推與遞歸比較遞推與遞歸比較迭代及其應(yīng)用迭代及其應(yīng)用 2 2. 遞推算法框架描述遞推算法框架描述f(1i-1)=； /* 確定初始值確定初始值 */for(k=i;k=n;k+) f(k)=； /* 施遞推施遞推 */printf(f(n)； /* 輸出輸出n規(guī)模的解規(guī)模的解f(n) */3（2） 簡單逆推算法簡單逆推算法 逆推即從后往前推逆推即從后往前推,從已得的規(guī)模為從已得的規(guī)模為n，n-1，i+1的一系列解，推出問題規(guī)模為的一系列解，推出問題規(guī)模為 i的解，直至的解，直至得到規(guī)模為得到規(guī)模為1的解。的解。 簡單逆推算法

2、框架描述：簡單逆推算法框架描述：f(ni+1)=f(ni+1)= ； / /* * 確定初始值確定初始值 * */ /for(k=i;k=1;k-)for(k=i;k=1;k-) f(k)= f(k)= ；/ /* * 實(shí)施遞推實(shí)施遞推 * */ /printf(f(1)printf(f(1)； / /* * 輸出解輸出解f(1) f(1) * */ /4設(shè)遞推的二維數(shù)組為設(shè)遞推的二維數(shù)組為f(k,j)f(k,j)，1kn,1jm1kn,1jm。二維數(shù)組順推算法框架描述：二維數(shù)組順推算法框架描述：f(1,1m)=f(1,1m)= ； / /* * 賦初始值賦初始值 * */ /for(k=2;

3、k=n;k+)for(k=2;k=n;k+)for(j=1;j=m;j+)for(j=1;j=m;j+) f(k,j)= f(k,j)= ； / /* * 實(shí)施遞推實(shí)施遞推 * */ /printf(f(n,m)printf(f(n,m)； / /* * 輸出解輸出解f(n,m) f(n,m) * */ /5 當(dāng)遞推關(guān)系包含兩個或兩個以上關(guān)系式時，通常應(yīng)用多關(guān)系當(dāng)遞推關(guān)系包含兩個或兩個以上關(guān)系式時，通常應(yīng)用多關(guān)系分級遞推算法求解。分級遞推算法求解。（4 4） 多關(guān)系分級遞推算法多關(guān)系分級遞推算法f(1i-1)=f(1i-1)= ； / /* * 賦初始值賦初始值 * */ /for(k=i;k

4、=n;k+)for(k=i;k=n;k+) if( if()1) f(k)= f(k)=1； / /* * 據(jù)遞推關(guān)系據(jù)遞推關(guān)系1 1遞推遞推 * */ / if( if()2) f(k)= f(k)=2； / /* * 據(jù)遞推關(guān)系據(jù)遞推關(guān)系2 2遞推遞推 * */ / if( if()m) f(k)= f(k)=m； / /* * 據(jù)遞推關(guān)系據(jù)遞推關(guān)系m m遞推遞推 * */ /printf(f(n)printf(f(n)； / /* * 輸出解輸出解f(n) f(n) * */ /61.2 遞推數(shù)列(1) (1) 遞推算法設(shè)計(jì)遞推算法設(shè)計(jì)設(shè)置設(shè)置k k循環(huán)（循環(huán)（k=1,2,k=1,2,，

5、n n，其中，其中n n為輸入整數(shù)），在為輸入整數(shù)），在k k循環(huán)外賦初值：循環(huán)外賦初值：a=2;b=3;s=0;a=2;b=3;s=0;在在k k循環(huán)中比較賦值：循環(huán)中比較賦值：當(dāng)當(dāng)ababab時，由賦值時，由賦值fk=bfk=b確定為序列的第確定為序列的第k k項(xiàng)；然后項(xiàng)；然后b=bb=b* *3 3，即，即b b按遞按遞推規(guī)律乘推規(guī)律乘3, 3, 為后一輪比較作準(zhǔn)備。為后一輪比較作準(zhǔn)備。1.2.1 冪序列冪序列7遞推過程描述：遞推過程描述：a=2;b=3; a=2;b=3; * * 為遞推變量為遞推變量a,ba,b賦初值賦初值 * */ /for(k=1;k=n;k+)for(k=1;k

6、=n;k+) if(ab) if(ab) fk=a;a=a fk=a;a=a* *2;/2;/* * 用用a a給給fkfk賦值賦值 * */ / else else fk=b;b=b fk=b;b=b* *3;/3;/* * 用用b b給給fkfk賦值賦值 * */ / 在這一算法中，變量在這一算法中，變量a,ba,b是變化的，分別代表是變化的，分別代表2 2的冪與的冪與3 3的冪。的冪。nn81.2.2 雙關(guān)系遞推數(shù)列(1) (1) 算法設(shè)計(jì)要點(diǎn)算法設(shè)計(jì)要點(diǎn)設(shè)設(shè)n n個數(shù)在數(shù)組個數(shù)在數(shù)組m m中，中，2x+12x+1與與 3x+13x+1均作為一個隊(duì)列，從均作為一個隊(duì)列，從兩隊(duì)列中選一排頭

7、兩隊(duì)列中選一排頭( (數(shù)值較小者數(shù)值較小者) )送入數(shù)組送入數(shù)組m m中。所謂中。所謂“排頭排頭”就是隊(duì)列中尚未選入就是隊(duì)列中尚未選入m m的最小的數(shù)（下標(biāo)）。的最小的數(shù)（下標(biāo)）。這里用這里用p2p2表示表示2x+12x+1這一列的排頭的下標(biāo)，用這一列的排頭的下標(biāo)，用p3p3表示表示3x+13x+1這一列的排頭的下標(biāo)。這一列的排頭的下標(biāo)。9if(2if(2* *m(p2)3m(p2)3m(p2)3* *m(p3)m(p3) m(i)=3 m(i)=3* *m(p3)+1;p3+;m(p3)+1;p3+;特別注意：兩隊(duì)列若出現(xiàn)相等時，給特別注意：兩隊(duì)列若出現(xiàn)相等時，給m m數(shù)組賦值數(shù)組賦值后，兩

8、排頭都要增后，兩排頭都要增1 1。if(2if(2* *m(p2)=3m(p2)=3* *m(p3)m(p3) m(i)=2 m(i)=2* *m(p2)+1;m(p2)+1; p2+; p3+; p2+; p3+; / /* * 為避免重復(fù)項(xiàng)，為避免重復(fù)項(xiàng)，P2P2，p3p3均須增均須增1 1 * */ / 101.3.1 1.3.1 猴子爬山問題猴子爬山問題【例例1.41.4】 一個頑猴在一座有一個頑猴在一座有3030級臺階的小山上級臺階的小山上爬山跳躍，猴子上山一步可跳爬山跳躍，猴子上山一步可跳1 1級，或跳級，或跳3 3級，試級，試求上山的求上山的3030級臺階有多少種不同的爬法。級臺

9、階有多少種不同的爬法。1. 1. 遞推算法設(shè)計(jì)遞推算法設(shè)計(jì)一般地有遞推關(guān)系：一般地有遞推關(guān)系： f(k)=f(k-1)+f(k-3) f(k)=f(k-1)+f(k-3) （k3k3）初始條件有初始條件有: : f(1)=1 f(1)=1； 即即1=11=1。 f(2)=1f(2)=1； 即即2=1+12=1+1。 f(3)=2f(3)=2； 即即3=1+1+13=1+1+1；3=33=3。1.3 應(yīng)用遞推求解應(yīng)用題11 int k,n; long f1000;int k,n; long f1000; printf( printf(請輸入臺階總數(shù)請輸入臺階總數(shù)n:);n:); scanf(%d

10、,&n); scanf(%d,&n); f1=1;f2=1;f3=2; f1=1;f2=1;f3=2; / /* * 數(shù)組元素賦初值數(shù)組元素賦初值 * */ / for(k=4;k=n;k+) for(k=4;k=n;k+) fk=fk-1+fk-3; fk=fk-1+fk-3; / /* * 按遞推關(guān)系實(shí)施遞推按遞推關(guān)系實(shí)施遞推 * */ / printf(s=%ld,fn); printf(s=%ld,fn);2. 算法描述算法描述: 123. 3. 問題引申問題引申把問題引申為爬山把問題引申為爬山n n級，一步有級，一步有m m 種跨法，一步跨多少級均種跨法，一步跨多少級

11、均從鍵盤輸入。從鍵盤輸入。(1(1） 分級遞推算法設(shè)計(jì)分級遞推算法設(shè)計(jì)設(shè)爬山設(shè)爬山t t臺階級的不同爬法為臺階級的不同爬法為f(t),f(t),設(shè)從鍵盤輸入一步跨多少設(shè)從鍵盤輸入一步跨多少級的級的m m個整數(shù)分別為個整數(shù)分別為x(1), x(2), , x(m)x(1), x(2), , x(m) ( (約定約定x(1)x(2)x(m)n)x(1)x(2)x(m)n)。這里的整數(shù)這里的整數(shù)x(1), x(2), , x(m)x(1), x(2), , x(m)為鍵盤輸入，事前并不知為鍵盤輸入，事前并不知道，因此不能在設(shè)計(jì)時簡單地確定道，因此不能在設(shè)計(jì)時簡單地確定f(x(1),f(x(2),f(

12、x(1),f(x(2),。事實(shí)上，可以把初始條件放在分級遞推中求取，應(yīng)用多關(guān)系事實(shí)上，可以把初始條件放在分級遞推中求取，應(yīng)用多關(guān)系分級遞推算法（分級遞推算法（6 6）完成遞推。）完成遞推。13 (2) 探討探討f(t)的遞推關(guān)系的遞推關(guān)系當(dāng)當(dāng)tx(1)tx(1)時，時，f(t)=0f(t)=0；f(x(1)=1f(x(1)=1。（初始條件）。（初始條件）當(dāng)當(dāng)x(1)tx(2)x(1)tx(2)時，第時，第1 1級遞推：級遞推：f(t)=f(t-x(1)f(t)=f(t-x(1)；當(dāng)當(dāng)x(2)tx(3)x(2)tx(3)時，第時，第2 2級遞推：級遞推：f(t)=f(t-x(1)+f(t-f(t

13、)=f(t-x(1)+f(t-x(2)x(2)；一般地，當(dāng)x(k)tx(k+1),k=1,2,m-1,有第k級遞推： f(t)=f(t-x(1)+f(t-x(2)+f(t-x(k)f(t)=f(t-x(1)+f(t-x(2)+f(t-x(k)當(dāng)x(m)t時，第m級遞推： f(t)=f(t-x(1)+f(t-x(2)+f(t-x(m)f(t)=f(t-x(1)+f(t-x(2)+f(t-x(m)14(3) (3) 注意注意當(dāng)當(dāng)t=x(2),t=x(2),或或t=x(3),t=x(3),或或t=x(m)t=x(m)時時, , 按上遞推按上遞推求求f(t)f(t)外外, ,還要加上還要加上1 1。道

14、理很簡單，因?yàn)榇藭r。道理很簡單，因?yàn)榇藭rt t本身即為一個一步到位的爬法。因而本身即為一個一步到位的爬法。因而 f(t)=f(t)+1f(t)=f(t)+1（t= x(2), x(3),x(m)t= x(2), x(3),x(m)）我們所求的目標(biāo)為：我們所求的目標(biāo)為： f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) 在遞推設(shè)計(jì)中我們可把臺階數(shù)在遞推設(shè)計(jì)中我們可把臺階數(shù)n n記為數(shù)組元素記為數(shù)組元素x(m+1),x(m+1),這樣處理是巧妙的這樣處理是巧妙的,可以按相同的遞推可以按相同的遞推規(guī)律遞推計(jì)算，簡化算法設(shè)計(jì)

15、。規(guī)律遞推計(jì)算，簡化算法設(shè)計(jì)。 最后一項(xiàng)最后一項(xiàng)f(x(m+1)f(x(m+1)即為所求即為所求f(n)f(n)。 15for(i=1;i=x1-1;i+) fi=0; for(i=1;i=x1-1;i+) fi=0; xm+1=n;fx1=1;xm+1=n;fx1=1;for(k=1;k=m;k+)for(k=1;k=m;k+)for(t=xk+1;t=xk+1;t+)for(t=xk+1;t=xk+1;t+) ft=0; ft=0; for(j=1;j=k;j+) / for(j=1;j=k;j+) /* * 按公式分級按公式分級 * */ / ft=ft+ft-xj; ft=ft+ft-

16、xj; if(t=xk+1) / if(t=xk+1) /* * t=x(k+1) t=x(k+1)時增時增1 1 * */ / ft=ft+1; ft=ft+1; printf( %ld. n,fn-1);printf( %ld. n,fn-1);(4) 算法描述算法描述161.3.2 整數(shù)劃分問題【例例1.51.5】 正整數(shù)正整數(shù)s s（簡稱為和數(shù)）的劃分（簡稱為和數(shù)）的劃分( (又稱分劃或拆又稱分劃或拆分分) )是把是把s s分成為若干個正整數(shù)（簡稱為零數(shù)或部分）之和分成為若干個正整數(shù)（簡稱為零數(shù)或部分）之和, , 劃分式中允許零數(shù)重復(fù)劃分式中允許零數(shù)重復(fù), ,且不記零數(shù)的次序。且不記零

17、數(shù)的次序。試求試求s s共有多個不同的劃分式？展示出共有多個不同的劃分式？展示出s s的所有這些劃分式。的所有這些劃分式。1. 1. 探索劃分的遞推關(guān)系探索劃分的遞推關(guān)系為了建立遞推關(guān)系，先對和數(shù)為了建立遞推關(guān)系，先對和數(shù)k k較小時的劃分式作觀察：較小時的劃分式作觀察：17由以上各劃分看到，除和數(shù)本身由以上各劃分看到，除和數(shù)本身k=kk=k這一特殊劃分這一特殊劃分式外，其它每一個劃分式至少為兩項(xiàng)之和。約定式外，其它每一個劃分式至少為兩項(xiàng)之和。約定在所有劃分式中零數(shù)作不減排列，探索和數(shù)在所有劃分式中零數(shù)作不減排列，探索和數(shù)k k的劃的劃分式與和數(shù)分式與和數(shù)k-1k-1的劃分式存在以下遞推關(guān)系的

18、劃分式存在以下遞推關(guān)系: :(1) (1) 在所有和數(shù)在所有和數(shù)k-1k-1的劃分式前加零數(shù)的劃分式前加零數(shù)1 1都是和數(shù)都是和數(shù)k k的劃分式。的劃分式。(2) (2) 和數(shù)和數(shù)k-1k-1的劃分式的前兩個零數(shù)作比較的劃分式的前兩個零數(shù)作比較, ,如果如果第第1 1個零數(shù)個零數(shù)x1x1小于第小于第2 2個零數(shù)個零數(shù)x2x2，則把第，則把第1 1個零數(shù)加個零數(shù)加1 1后成為和數(shù)后成為和數(shù)k k的劃分式。的劃分式。18顯然遞推的初始條件為：顯然遞推的初始條件為： a(2,1,1)=1a(2,1,1)=1，a(2,1,2)=1; a(2,2,1)=2a(2,1,2)=1; a(2,2,1)=2。根

19、據(jù)遞推關(guān)系，實(shí)施遞推：根據(jù)遞推關(guān)系，實(shí)施遞推：(1) (1) 實(shí)施在實(shí)施在k-1k-1所有劃分式前加所有劃分式前加1 1操作操作 a(k,j,1)=1; a(k,j,1)=1; for(t=2;t=k;t+) for(t=2;t=k;t+) a(k,j,t)=a(k-1,j,t-1); a(k,j,t)=a(k-1,j,t-1); / /* * k-1 k-1的第的第t-1t-1項(xiàng)變?yōu)轫?xiàng)變?yōu)閗 k的第的第t t項(xiàng)項(xiàng) * */ / (2) (2) 若若k-1k-1劃分式第劃分式第1 1項(xiàng)小于第項(xiàng)小于第2 2項(xiàng)，第項(xiàng)，第1 1項(xiàng)加項(xiàng)加1 1，變?yōu)?，變?yōu)閗 k的的第第i i個劃分式個劃分式 if(a

20、(k-1,j,1)a(k-1,j,2)if(a(k-1,j,1)a(k-1,j,2) a(k,i,1)=a(k-1,j,1)+1; a(k,i,1)=a(k-1,j,1)+1; for(t=2;t=k-1;t+) for(t=2;t=1;t-) for(t=i;t=1;t-) a(j,t+1)=a(j,t); a(j,t+1)=a(j,t);a(j,1)=1; a(j,1)=1; 20 211.4 遞推與遞歸比較遞歸其實(shí)就是利用系統(tǒng)堆棧遞歸其實(shí)就是利用系統(tǒng)堆棧, ,實(shí)現(xiàn)函數(shù)自身調(diào)用實(shí)現(xiàn)函數(shù)自身調(diào)用, ,或者是相或者是相互調(diào)用的過程。在通往邊界的過程中互調(diào)用的過程。在通往邊界的過程中, ,都會把

21、單步地址保都會把單步地址保存下來，再按照先進(jìn)后出進(jìn)行運(yùn)算。遞歸的數(shù)據(jù)傳送也類存下來，再按照先進(jìn)后出進(jìn)行運(yùn)算。遞歸的數(shù)據(jù)傳送也類似。似。遞歸的運(yùn)算方法遞歸的運(yùn)算方法, ,決定了它的效率較低，因?yàn)閿?shù)據(jù)要不斷決定了它的效率較低，因?yàn)閿?shù)據(jù)要不斷的進(jìn)棧出棧。在應(yīng)用遞歸時，只要輸入的的進(jìn)棧出棧。在應(yīng)用遞歸時，只要輸入的n n值稍大，程序值稍大，程序求解就比較困難。因而從計(jì)算效率來說，遞推往往要高于求解就比較困難。因而從計(jì)算效率來說，遞推往往要高于遞歸。遞歸。遞推免除了數(shù)據(jù)進(jìn)出棧的過程，也就是說遞推免除了數(shù)據(jù)進(jìn)出棧的過程，也就是說, ,不需要函數(shù)不不需要函數(shù)不斷的向邊界值靠攏斷的向邊界值靠攏, ,而直接從邊

22、界出發(fā)，逐步推出函數(shù)值而直接從邊界出發(fā)，逐步推出函數(shù)值, , 直觀明了。直觀明了。在有些情況下，遞歸可以轉(zhuǎn)化為效率較高的遞推。但是遞在有些情況下，遞歸可以轉(zhuǎn)化為效率較高的遞推。但是遞歸作為重要的基礎(chǔ)算法歸作為重要的基礎(chǔ)算法, ,它的作用不可替代，在把握這兩它的作用不可替代，在把握這兩種算法的時候應(yīng)該特別注意。種算法的時候應(yīng)該特別注意。22【例例1.61.6】 求整數(shù)求整數(shù)s s的劃分?jǐn)?shù)的劃分?jǐn)?shù)解：設(shè)解：設(shè)n n的的“最大零數(shù)不超過最大零數(shù)不超過m”m”的劃分式個數(shù)為的劃分式個數(shù)為q(n,m)q(n,m)。 建立遞推關(guān)系建立遞推關(guān)系所有所有q(n,m)q(n,m)個劃分式分為兩類：零數(shù)中不包含個劃分式分為兩類：零數(shù)中不包含m m的劃分式的劃分式有有q(n,m-1)q(n,m-1)個；零數(shù)中包含個；零數(shù)中包含m m 的劃分式有的劃分式有q(n-m,m)q(n-m,m)個。有個。有 q(n,m)=q(n,m-1)+q(n-m,m) (1mns)q(n,m)=q(n,m-1)+q(n-m,m) (1mns)其中其中 q(n-m,m)=q(n-m,n-m) q