第1講 遞推與迭代.ppt

1、常用算法與程序設(shè)計(jì),1,第 1 講,遞推與迭代,常用算法與程序設(shè)計(jì),2,主要內(nèi)容,遞推概述 遞推數(shù)列 應(yīng)用遞推求解應(yīng)用題 遞推與遞歸比較 迭代及其應(yīng)用,常用算法與程序設(shè)計(jì),3,1.1 遞推概述,1.1.1 遞推算法 遞推是一種高效的數(shù)學(xué)模型，是組合數(shù)學(xué)中的一個(gè)重要解題方法。 遞推是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法。 遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)之間的關(guān)系，即遞推關(guān)系。,常用算法與程序設(shè)計(jì),4,1. 實(shí)施遞推的步驟 (1) 確定遞推變量 (2) 建立遞推關(guān)系 (3) 確定初始（邊界）條件 (4) 對(duì)遞推過程進(jìn)行控制,1.1.2 遞推實(shí)施步驟與描述,常用算法與程序設(shè)計(jì),5

2、,2. 遞推算法框架描述,（1） 簡單順推算法 順推即從前往后推,從已求得的規(guī)模為1，2， ，i-1的一系列解，推出問題規(guī)模為 i的解，直至得到規(guī)模為n的解。 簡單順推算法框架描述： f(1i-1)=； /* 確定初始值 */ for(k=i;k； /* 施遞推 */ printf(f(n)； /* 輸出n規(guī)模的解f(n) */,常用算法與程序設(shè)計(jì),6,（2） 簡單逆推算法 逆推即從后往前推,從已得的規(guī)模為n，n-1， ，i+1的一系列解，推出問題規(guī)模為 i的解，直至得到規(guī)模為1的解。 簡單逆推算法框架描述： f(ni+1)=； /* 確定初始值 */ for(k=i;k=1;k-) f(k)

3、=；/* 實(shí)施遞推 */ printf(f(1)； /* 輸出解f(1) */,常用算法與程序設(shè)計(jì),7,設(shè)遞推的二維數(shù)組為f(k,j)，1kn,1jm。 二維數(shù)組順推算法框架描述： f(1,1m)=； /* 賦初始值 */ for(k=2;k； /* 實(shí)施遞推 */ printf(f(n,m)； /* 輸出解f(n,m) */,（3） 二維數(shù)組順推算法,常用算法與程序設(shè)計(jì),8,當(dāng)遞推關(guān)系包含兩個(gè)或兩個(gè)以上關(guān)系式時(shí)，通常應(yīng)用多關(guān)系分級(jí)遞推算法求解。 （4） 多關(guān)系分級(jí)遞推算法 f(1i-1)=； /* 賦初始值 */ for(k=i;k) f(k)=； /* 據(jù)遞推關(guān)系1遞推 */ if() f

4、(k)=； /* 據(jù)遞推關(guān)系2遞推 */ if() f(k)=； /* 據(jù)遞推關(guān)系m遞推 */ printf(f(n)； /* 輸出解f(n) */,常用算法與程序設(shè)計(jì),9,1.2 遞推數(shù)列,(1) 遞推算法設(shè)計(jì) 設(shè)置k循環(huán)（k=1,2,，n，其中n為輸入整數(shù)），在k循環(huán)外賦初值：a=2;b=3;s=0;在k循環(huán)中比較賦值： 當(dāng)ab時(shí)，由賦值fk=b確定為序列的第k項(xiàng)；然后b=b*3，即b按遞推規(guī)律乘3, 為后一輪比較作準(zhǔn)備。,1.2.1 冪序列,常用算法與程序設(shè)計(jì),10,遞推過程描述： a=2;b=3; * 為遞推變量a,b賦初值 */ for(k=1;k=n;k+) if(ab) fk=a

5、;a=a*2;/* 用a給fk賦值 */ else fk=b;b=b*3;/* 用b給fk賦值 */ 在這一算法中，變量a,b是變化的，分別代表2的冪與3的冪。,常用算法與程序設(shè)計(jì),11,1.2.2 雙關(guān)系遞推數(shù)列,(1) 算法設(shè)計(jì)要點(diǎn) 設(shè)n個(gè)數(shù)在數(shù)組m中，2x+1與 3x+1均作為一個(gè)隊(duì)列，從兩隊(duì)列中選一排頭(數(shù)值較小者)送入數(shù)組m中。所謂“排頭”就是隊(duì)列中尚未選入m的最小的數(shù)（下標(biāo)）。這里用p2表示2x+1這一列的排頭的下標(biāo)，用p3表示3x+1這一列的排頭的下標(biāo)。,常用算法與程序設(shè)計(jì),12,if(2*m(p2)3*m(p3) m(i)=3*m(p3)+1;p3+; 特別注意：兩隊(duì)列若出現(xiàn)相

6、等時(shí)，給m數(shù)組賦值后，兩排頭都要增1。 if(2*m(p2)=3*m(p3) m(i)=2*m(p2)+1; p2+; p3+; /* 為避免重復(fù)項(xiàng)，P2，p3均須增1 */ ,常用算法與程序設(shè)計(jì),13,1.3.1 猴子爬山問題 【例1.4】 一個(gè)頑猴在一座有30級(jí)臺(tái)階的小山上爬山跳躍，猴子上山一步可跳1級(jí)，或跳3級(jí)，試求上山的30級(jí)臺(tái)階有多少種不同的爬法。 1. 遞推算法設(shè)計(jì) 一般地有遞推關(guān)系： f(k)=f(k-1)+f(k-3) （k3） 初始條件有: f(1)=1； 即1=1。 f(2)=1； 即2=1+1。 f(3)=2； 即3=1+1+1；3=3。,1.3 應(yīng)用遞推求解應(yīng)用題,常用

7、算法與程序設(shè)計(jì),14,int k,n; long f1000; printf(請(qǐng)輸入臺(tái)階總數(shù)n:); scanf(%d,2. 算法描述:,常用算法與程序設(shè)計(jì),15,3. 問題引申 把問題引申為爬山n級(jí)，一步有m 種跨法，一步跨多少級(jí)均從鍵盤輸入。 (1） 分級(jí)遞推算法設(shè)計(jì) 設(shè)爬山t臺(tái)階級(jí)的不同爬法為f(t),設(shè)從鍵盤輸入一步跨多少級(jí)的m個(gè)整數(shù)分別為x(1), x(2), , x(m) (約定x(1)x(2)x(m)n)。 這里的整數(shù)x(1), x(2), , x(m)為鍵盤輸入，事前并不知道，因此不能在設(shè)計(jì)時(shí)簡單地確定f(x(1),f(x(2),。 事實(shí)上，可以把初始條件放在分級(jí)遞推中求取，應(yīng)

8、用多關(guān)系分級(jí)遞推算法（6）完成遞推。,常用算法與程序設(shè)計(jì),16,(2) 探討f(t)的遞推關(guān)系 當(dāng)tx(1)時(shí)，f(t)=0；f(x(1)=1。（初始條件） 當(dāng)x(1)tx(2)時(shí)，第1級(jí)遞推：f(t)=f(t-x(1)； 當(dāng)x(2)tx(3)時(shí)，第2級(jí)遞推：f(t)=f(t-x(1)+f(t-x(2)； 一般地，當(dāng)x(k)tx(k+1),k=1,2,m-1,有第k級(jí)遞推： f(t)=f(t-x(1)+f(t-x(2)+f(t-x(k) 當(dāng)x(m)t時(shí)，第m級(jí)遞推： f(t)=f(t-x(1)+f(t-x(2)+f(t-x(m),常用算法與程序設(shè)計(jì),17,(3) 注意 當(dāng)t=x(2),或t=x

9、(3),或t=x(m)時(shí), 按上遞推求f(t)外,還要加上1。道理很簡單，因?yàn)榇藭r(shí)t本身即為一個(gè)一步到位的爬法。因而 f(t)=f(t)+1（t= x(2), x(3),x(m)） 我們所求的目標(biāo)為： f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) 在遞推設(shè)計(jì)中我們可把臺(tái)階數(shù)n記為數(shù)組元素x(m+1),這樣處理是巧妙的,可以按相同的遞推規(guī)律遞推計(jì)算，簡化算法設(shè)計(jì)。 最后一項(xiàng)f(x(m+1)即為所求f(n)。,常用算法與程序設(shè)計(jì),18,for(i=1;i=x1-1;i+) fi=0; xm+1=n;fx1=1; for(k=1;k=m;k+) for(t=xk+1;t=xk+1;

10、t+) ft=0; for(j=1;j=k;j+) /* 按公式分級(jí) */ ft=ft+ft-xj; if(t=xk+1) /* t=x(k+1)時(shí)增1 */ ft=ft+1; printf( %ld. n,fn-1);,(4) 算法描述,常用算法與程序設(shè)計(jì),19,1.3.2 整數(shù)劃分問題,【例1.5】 正整數(shù)s（簡稱為和數(shù)）的劃分(又稱分劃或拆分)是把s分成為若干個(gè)正整數(shù)（簡稱為零數(shù)或部分）之和, 劃分式中允許零數(shù)重復(fù),且不記零數(shù)的次序。 試求s共有多個(gè)不同的劃分式？展示出s的所有這些劃分式。 1. 探索劃分的遞推關(guān)系 為了建立遞推關(guān)系，先對(duì)和數(shù)k較小時(shí)的劃分式作觀察： k=2：1+1；2

11、k=3：1+1+1；1+2；3 k=4：1+1+1+1；1+1+2；1+3；2+2；4 k=5：1+1+1+1+1；1+1+1+2；1+1+3；1+2+2；1+4；2+3；5,常用算法與程序設(shè)計(jì),20,由以上各劃分看到，除和數(shù)本身k=k這一特殊劃分式外，其它每一個(gè)劃分式至少為兩項(xiàng)之和。約定在所有劃分式中零數(shù)作不減排列，探索和數(shù)k的劃分式與和數(shù)k-1的劃分式存在以下遞推關(guān)系: (1) 在所有和數(shù)k-1的劃分式前加零數(shù)1都是和數(shù)k的劃分式。 (2) 和數(shù)k-1的劃分式的前兩個(gè)零數(shù)作比較,如果第1個(gè)零數(shù)x1小于第2個(gè)零數(shù)x2，則把第1個(gè)零數(shù)加1后成為和數(shù)k的劃分式。,常用算法與程序設(shè)計(jì),21,顯然遞

12、推的初始條件為： a(2,1,1)=1，a(2,1,2)=1; a(2,2,1)=2。 根據(jù)遞推關(guān)系，實(shí)施遞推： (1) 實(shí)施在k-1所有劃分式前加1操作 a(k,j,1)=1; for(t=2;t=k;t+) a(k,j,t)=a(k-1,j,t-1); /* k-1的第t-1項(xiàng)變?yōu)閗的第t項(xiàng) */ (2) 若k-1劃分式第1項(xiàng)小于第2項(xiàng)，第1項(xiàng)加1，變?yōu)閗的第i個(gè)劃分式 if(a(k-1,j,1)a(k-1,j,2) a(k,i,1)=a(k-1,j,1)+1; for(t=2;t=k-1;t+) a(k,i,t)=a(k-1,j,t); ,2. 算法描述,常用算法與程序設(shè)計(jì),22,3.

13、整數(shù)劃分遞推設(shè)計(jì)的優(yōu)化,考察以上應(yīng)用三維數(shù)組a(k,j,i)完成遞推過程，當(dāng)由k-1的劃分式推出k的劃分式時(shí)，k-1以前的數(shù)組單元已完全閑置。為此可考慮把三維數(shù)組a(k,j,i)改進(jìn)為二維數(shù)組a(j,i) 。二維數(shù)組a(j,i)表示和數(shù)是k-1的已有劃分式，根據(jù)遞推關(guān)系推出k的劃分式： (1）把a(bǔ)(j,i）依次存儲(chǔ)到a(j,i+1),加上第一項(xiàng)a(j,1)=1；這樣完成在k-1的所有劃分式前加1的操作，轉(zhuǎn)化為k的劃分式。 for(t=i;t=1;t-) a(j,t+1)=a(j,t); a(j,1)=1;,常用算法與程序設(shè)計(jì),23,(2) 對(duì)已轉(zhuǎn)化的u個(gè)劃分式逐個(gè)檢驗(yàn)，若其第2個(gè)數(shù)小于第3個(gè)數(shù)

14、（相當(dāng)于k-1時(shí)的第1個(gè)數(shù)小于第2個(gè)數(shù)），則把第2個(gè)數(shù)加1，去除第一個(gè)數(shù)后，作為k時(shí)增加的一個(gè)劃分式，為第t(t從u開始，每增加一個(gè)劃分式，t增1)劃分式。 for(t=u,j=1;j0) a(t,i-1)=a(j,i);i+; ,常用算法與程序設(shè)計(jì),24,1.4 遞推與遞歸比較,遞歸其實(shí)就是利用系統(tǒng)堆棧,實(shí)現(xiàn)函數(shù)自身調(diào)用,或者是相互調(diào)用的過程。在通往邊界的過程中,都會(huì)把單步地址保存下來，再按照先進(jìn)后出進(jìn)行運(yùn)算。遞歸的數(shù)據(jù)傳送也類似。 遞歸的運(yùn)算方法,決定了它的效率較低，因?yàn)閿?shù)據(jù)要不斷的進(jìn)棧出棧。在應(yīng)用遞歸時(shí)，只要輸入的n值稍大，程序求解就比較困難。因而從計(jì)算效率來說，遞推往往要高于遞歸。 遞推免除了數(shù)據(jù)進(jìn)出棧的過程，也就是說,不需要函數(shù)不斷的向邊界值靠攏,而直接從邊界出發(fā)，逐步推出函數(shù)值, 直觀明了。 在有些情況下，遞歸可以轉(zhuǎn)化為效率較高的遞推。但是遞歸作為重要的基礎(chǔ)算法,它的作用不可替代，在把握這兩種算法的時(shí)候應(yīng)該特別注意。,常用算法與程序設(shè)計(jì),25,【例1.6】 求整數(shù)s的劃分?jǐn)?shù) 解：設(shè)n的“最大零數(shù)不超過m”的劃分式個(gè)數(shù)為q(n,m)。 建立遞推關(guān)系 所有q(n,m)個(gè)劃分式分為兩類：零數(shù)中不包含m的劃分式有q(n,m-1)個(gè)；零數(shù)中包含m 的劃分式有q(n-m,m)個(gè)。有 q(n,m)=q(n,m-1)+q(n-m,m) (1mns) 其中 q