第1講 遞推與迭代.ppt

1、常用算法與程序設(shè)計,1,第 1 講,遞推與迭代,常用算法與程序設(shè)計,2,主要內(nèi)容,遞推概述 遞推數(shù)列 應(yīng)用遞推求解應(yīng)用題 遞推與遞歸比較 迭代及其應(yīng)用,常用算法與程序設(shè)計,3,1.1 遞推概述,1.1.1 遞推算法 遞推是一種高效的數(shù)學(xué)模型，是組合數(shù)學(xué)中的一個重要解題方法。 遞推是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法。 遞推算法的首要問題是得到相鄰的數(shù)據(jù)項之間的關(guān)系，即遞推關(guān)系。,常用算法與程序設(shè)計,4,1. 實施遞推的步驟 (1) 確定遞推變量 (2) 建立遞推關(guān)系 (3) 確定初始（邊界）條件 (4) 對遞推過程進行控制,1.1.2 遞推實施步驟與描述,常用算法與程序設(shè)計,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è)計,6,（2） 簡單逆推算法 逆推即從后往前推,從已得的規(guī)模為n，n-1， ，i+1的一系列解，推出問題規(guī)模為 i的解，直至得到規(guī)模為1的解。 簡單逆推算法框架描述： f(ni+1)=； /* 確定初始值 */ for(k=i;k=1;k-) f(k)

3、=；/* 實施遞推 */ printf(f(1)； /* 輸出解f(1) */,常用算法與程序設(shè)計,7,設(shè)遞推的二維數(shù)組為f(k,j)，1kn,1jm。 二維數(shù)組順推算法框架描述： f(1,1m)=； /* 賦初始值 */ for(k=2;k； /* 實施遞推 */ printf(f(n,m)； /* 輸出解f(n,m) */,（3） 二維數(shù)組順推算法,常用算法與程序設(shè)計,8,當遞推關(guān)系包含兩個或兩個以上關(guān)系式時，通常應(yīng)用多關(guān)系分級遞推算法求解。 （4） 多關(guān)系分級遞推算法 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è)計,9,1.2 遞推數(shù)列,(1) 遞推算法設(shè)計 設(shè)置k循環(huán)（k=1,2,，n，其中n為輸入整數(shù)），在k循環(huán)外賦初值：a=2;b=3;s=0;在k循環(huán)中比較賦值： 當ab時，由賦值fk=b確定為序列的第k項；然后b=b*3，即b按遞推規(guī)律乘3, 為后一輪比較作準備。,1.2.1 冪序列,常用算法與程序設(shè)計,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è)計,11,1.2.2 雙關(guān)系遞推數(shù)列,(1) 算法設(shè)計要點 設(shè)n個數(shù)在數(shù)組m中，2x+1與 3x+1均作為一個隊列，從兩隊列中選一排頭(數(shù)值較小者)送入數(shù)組m中。所謂“排頭”就是隊列中尚未選入m的最小的數(shù)（下標）。這里用p2表示2x+1這一列的排頭的下標，用p3表示3x+1這一列的排頭的下標。,常用算法與程序設(shè)計,12,if(2*m(p2)3*m(p3) m(i)=3*m(p3)+1;p3+; 特別注意：兩隊列若出現(xiàn)相

6、等時，給m數(shù)組賦值后，兩排頭都要增1。 if(2*m(p2)=3*m(p3) m(i)=2*m(p2)+1; p2+; p3+; /* 為避免重復(fù)項，P2，p3均須增1 */ ,常用算法與程序設(shè)計,13,1.3.1 猴子爬山問題 【例1.4】 一個頑猴在一座有30級臺階的小山上爬山跳躍，猴子上山一步可跳1級，或跳3級，試求上山的30級臺階有多少種不同的爬法。 1. 遞推算法設(shè)計 一般地有遞推關(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è)計,14,int k,n; long f1000; printf(請輸入臺階總數(shù)n:); scanf(%d,2. 算法描述:,常用算法與程序設(shè)計,15,3. 問題引申 把問題引申為爬山n級，一步有m 種跨法，一步跨多少級均從鍵盤輸入。 (1） 分級遞推算法設(shè)計 設(shè)爬山t臺階級的不同爬法為f(t),設(shè)從鍵盤輸入一步跨多少級的m個整數(shù)分別為x(1), x(2), , x(m) (約定x(1)x(2)x(m)n)。 這里的整數(shù)x(1), x(2), , x(m)為鍵盤輸入，事前并不知道，因此不能在設(shè)計時簡單地確定f(x(1),f(x(2),。 事實上，可以把初始條件放在分級遞推中求取，應(yīng)

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

9、(3),或t=x(m)時, 按上遞推求f(t)外,還要加上1。道理很簡單，因為此時t本身即為一個一步到位的爬法。因而 f(t)=f(t)+1（t= x(2), x(3),x(m)） 我們所求的目標為： f(n)=f(n-x(1)+f(n-x(2)+f(n-x(m) 在遞推設(shè)計中我們可把臺階數(shù)n記為數(shù)組元素x(m+1),這樣處理是巧妙的,可以按相同的遞推規(guī)律遞推計算，簡化算法設(shè)計。 最后一項f(x(m+1)即為所求f(n)。,常用算法與程序設(shè)計,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+) /* 按公式分級 */ ft=ft+ft-xj; if(t=xk+1) /* t=x(k+1)時增1 */ ft=ft+1; printf( %ld. n,fn-1);,(4) 算法描述,常用算法與程序設(shè)計,19,1.3.2 整數(shù)劃分問題,【例1.5】 正整數(shù)s（簡稱為和數(shù)）的劃分(又稱分劃或拆分)是把s分成為若干個正整數(shù)（簡稱為零數(shù)或部分）之和, 劃分式中允許零數(shù)重復(fù),且不記零數(shù)的次序。 試求s共有多個不同的劃分式？展示出s的所有這些劃分式。 1. 探索劃分的遞推關(guān)系 為了建立遞推關(guān)系，先對和數(shù)k較小時的劃分式作觀察： 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è)計,20,由以上各劃分看到，除和數(shù)本身k=k這一特殊劃分式外，其它每一個劃分式至少為兩項之和。約定在所有劃分式中零數(shù)作不減排列，探索和數(shù)k的劃分式與和數(shù)k-1的劃分式存在以下遞推關(guān)系: (1) 在所有和數(shù)k-1的劃分式前加零數(shù)1都是和數(shù)k的劃分式。 (2) 和數(shù)k-1的劃分式的前兩個零數(shù)作比較,如果第1個零數(shù)x1小于第2個零數(shù)x2，則把第1個零數(shù)加1后成為和數(shù)k的劃分式。,常用算法與程序設(shè)計,21,顯然遞

12、推的初始條件為： a(2,1,1)=1，a(2,1,2)=1; a(2,2,1)=2。 根據(jù)遞推關(guān)系，實施遞推： (1) 實施在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項變?yōu)閗的第t項 */ (2) 若k-1劃分式第1項小于第2項，第1項加1，變?yōu)閗的第i個劃分式 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è)計,22,3.

13、整數(shù)劃分遞推設(shè)計的優(yōu)化,考察以上應(yīng)用三維數(shù)組a(k,j,i)完成遞推過程，當由k-1的劃分式推出k的劃分式時，k-1以前的數(shù)組單元已完全閑置。為此可考慮把三維數(shù)組a(k,j,i)改進為二維數(shù)組a(j,i) 。二維數(shù)組a(j,i)表示和數(shù)是k-1的已有劃分式，根據(jù)遞推關(guān)系推出k的劃分式： (1）把a(j,i）依次存儲到a(j,i+1),加上第一項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è)計,23,(2) 對已轉(zhuǎn)化的u個劃分式逐個檢驗，若其第2個數(shù)小于第3個數(shù)

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