第3章遞推算法(C++版)

1、第三章第三章 遞推算法遞推算法 遞推法是一種重要的數(shù)學(xué)方法，在數(shù)學(xué)的各個(gè)領(lǐng)域中都遞推法是一種重要的數(shù)學(xué)方法，在數(shù)學(xué)的各個(gè)領(lǐng)域中都有廣泛的運(yùn)用，也是計(jì)算機(jī)用于數(shù)值計(jì)算的一個(gè)重要算法。有廣泛的運(yùn)用，也是計(jì)算機(jī)用于數(shù)值計(jì)算的一個(gè)重要算法。這種算法特點(diǎn)是：一個(gè)問題的求解需一系列的計(jì)算，在已知這種算法特點(diǎn)是：一個(gè)問題的求解需一系列的計(jì)算，在已知條件和所求問題之間總存在著某種相互聯(lián)系的關(guān)系，在計(jì)算條件和所求問題之間總存在著某種相互聯(lián)系的關(guān)系，在計(jì)算時(shí)，如果可以找到前后過程之間的數(shù)量關(guān)系（即遞推式），時(shí)，如果可以找到前后過程之間的數(shù)量關(guān)系（即遞推式），那么，從問題出發(fā)逐步推到已知條件，此種方法叫逆推。無那么

2、，從問題出發(fā)逐步推到已知條件，此種方法叫逆推。無論順推還是逆推，其關(guān)鍵是要找到遞推式。這種處理問題的論順推還是逆推，其關(guān)鍵是要找到遞推式。這種處理問題的方法能使復(fù)雜運(yùn)算化為若干步重復(fù)的簡(jiǎn)單運(yùn)算，充分發(fā)揮出方法能使復(fù)雜運(yùn)算化為若干步重復(fù)的簡(jiǎn)單運(yùn)算，充分發(fā)揮出計(jì)算機(jī)擅長(zhǎng)于重復(fù)處理的特點(diǎn)。計(jì)算機(jī)擅長(zhǎng)于重復(fù)處理的特點(diǎn)。 遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系（即遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系（即遞推關(guān)系）。遞推算法避開了求通項(xiàng)公式的麻煩，把一個(gè)復(fù)遞推關(guān)系）。遞推算法避開了求通項(xiàng)公式的麻煩，把一個(gè)復(fù)雜的問題的求解，分解成了連續(xù)的若干步簡(jiǎn)單運(yùn)算。一般說雜的問題的求解，分解成了連續(xù)的若干

3、步簡(jiǎn)單運(yùn)算。一般說來，可以將遞推算法看成是一種特殊的迭代算法。來，可以將遞推算法看成是一種特殊的迭代算法?！纠?】數(shù)字三角形。如下所示為一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)綌?shù)字三角形。如下所示為一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)降椎哪程幍囊粭l路徑，使該路徑所經(jīng)過的數(shù)字總和最大。只要求輸出總和。底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字總和最大。只要求輸出總和。 1、 一步可沿左斜線向下或右斜線向下走； 2、 三角形行數(shù)小于等于100； 3、 三角形中的數(shù)字為0，1，99； 測(cè)試數(shù)據(jù)通過鍵盤逐行輸入，如上例數(shù)據(jù)應(yīng)以如下所示格式輸入：573 88 1 02 7 4 44 5 2 6 5【算法

4、分析算法分析】此題解法有多種，從遞推的思想出發(fā)，設(shè)想，當(dāng)從頂層沿某條路徑走到第i層向第i+1層前進(jìn)時(shí)，我們的選擇一定是沿其下兩條可行路徑中最大數(shù)字的方向前進(jìn)，為此，我們可以采用倒推的手法，設(shè)aij存放從i,j 出發(fā)到達(dá)n層的最大值，則aij=maxaij+ai+1j，aij+ai+1j+1，a11 即為所求的數(shù)字總和的最大值?！緟⒖汲绦騾⒖汲绦颉?includeusing namespace std;int main() int n,i,j,a101101; cinn; for (i=1;i=n;i+) for (j=1;jaij; /輸入數(shù)字三角形的值 for (i=n-1;i=1;i-)

5、for (j=1;j=ai+1j+1) aij+=ai+1j; /路徑選擇 else aij+=ai+1j+1; couta110), 輸出鋪法總數(shù)。輸出鋪法總數(shù)?！舅惴ǚ治鏊惴ǚ治觥浚?）面對(duì)上述問題，如果思考方法不恰當(dāng)，要想獲得問題的解）面對(duì)上述問題，如果思考方法不恰當(dāng)，要想獲得問題的解答是相當(dāng)困難的?？梢杂眠f推方法歸納出問題解的一般規(guī)律。答是相當(dāng)困難的?？梢杂眠f推方法歸納出問題解的一般規(guī)律。 （2）當(dāng)）當(dāng)n=1時(shí)，只能是一種鋪法，鋪法總數(shù)有示為時(shí)，只能是一種鋪法，鋪法總數(shù)有示為x1=1。（3）當(dāng)）當(dāng)n=2時(shí)：骨牌可以兩個(gè)并列豎排，也可以并列橫排，再時(shí)：骨牌可以兩個(gè)并列豎排，也可以并列橫排

6、，再無其他方法，如下左圖所示，因此，鋪法總數(shù)表示為無其他方法，如下左圖所示，因此，鋪法總數(shù)表示為x2=2； （4）當(dāng)n=3時(shí)：骨牌可以全部豎排，也可以認(rèn)為在方格中已經(jīng)有一個(gè)豎排骨牌，則需要在方格中排列兩個(gè)橫排骨牌（無重復(fù)方法），若已經(jīng)在方格中排列兩個(gè)橫排骨牌，則必須在方格中排列一個(gè)豎排骨牌。如上右圖，再無其他排列方法，因此鋪法總數(shù)表示為x3=3。由此可以看出，當(dāng)n=3時(shí)的排列骨牌的方法數(shù)是n=1和n=2排列方法數(shù)的和。 （5）推出一般規(guī)律：對(duì)一般的n，要求xn可以這樣來考慮，若第一個(gè)骨牌是豎排列放置，剩下有n-1個(gè)骨牌需要排列，這時(shí)排列方法數(shù)為xn-1；若第一個(gè)骨牌是橫排列，整個(gè)方格至少有2個(gè)

7、骨牌是橫排列（1*2骨牌），因此剩下n-2個(gè)骨牌需要排列，這是骨牌排列方法數(shù)為xn-2。從第一骨牌排列方法考慮，只有這兩種可能，所以有： xn=xn-1+xn-2 （n2） x1=1 x2=2 xn=xn-1+xn-2就是問題求解的遞推公式。任給n都可以從中獲得解答。例如n=5， x3=x2+x1=3 x4=x3+x2=5 x5=x4+x3=8 下面是輸入下面是輸入n，輸出，輸出x1xn的的c+程序：程序：#includeusing namespace std;int main() int n,i,j,a101; coutn; a1=1;a2=2; coutx1=a1endl; coutx2=

8、a2endl; for (i=3;i=n;i+) /遞推過程遞推過程 ai=ai-1+ai-2; coutxi=aiendl; 下面是運(yùn)行程序輸入下面是運(yùn)行程序輸入 n=30，輸出的結(jié)果：，輸出的結(jié)果： input n: 30 x1=1 x2=2 x3=3 . x29=832040 x30=1346269問題的結(jié)果就是有名的斐波那契數(shù)。問題的結(jié)果就是有名的斐波那契數(shù)?！纠纠?】棋盤格數(shù)】棋盤格數(shù)設(shè)有一個(gè)N*M方格的棋盤（ l N100，1M100）。求出該棋盤中包含有多少個(gè)正方形、多少個(gè)長(zhǎng)方形（不包括正方形）。 例如：當(dāng) N=2， M3時(shí)： 正方形的個(gè)數(shù)有8個(gè)：即邊長(zhǎng)為1的正方形有6個(gè)；邊長(zhǎng)

9、為2的正方形有2個(gè)。 長(zhǎng)方形的個(gè)數(shù)有10個(gè)：即2*1的長(zhǎng)方形有4個(gè)：1*2的長(zhǎng)方形有3個(gè)：3*1的長(zhǎng)方形有2個(gè)：3*2的長(zhǎng)方形有1個(gè)： 程序要求：輸入：N，M 輸出：正方形的個(gè)數(shù)與長(zhǎng)方形的個(gè)數(shù) 如上例：輸入：2 3 輸出：8 10【算法分析】【算法分析】1.計(jì)算正方形的個(gè)數(shù)s1 邊長(zhǎng)為1的正方形個(gè)數(shù)為n*m 邊長(zhǎng)為2的正方形個(gè)數(shù)為(n-1)*(m-1) 邊長(zhǎng)為3的正方形個(gè)數(shù)為(n-2)*(m-2)邊長(zhǎng)為minn，m的正方形個(gè)數(shù)為(m-minn，m+1)*(n-minn，m+1)根據(jù)加法原理得出 s1= 1,min0)(*)(nmiimin2.長(zhǎng)方形和正方形的個(gè)數(shù)之和s 寬為1的長(zhǎng)方形和正方形有

10、m個(gè)，寬為2的長(zhǎng)方形和正方形有m-1個(gè)，寬為m的長(zhǎng)方形和正方形有1個(gè)； 長(zhǎng)為1的長(zhǎng)方形和正方形有n個(gè)，長(zhǎng)為2的長(zhǎng)方形和正方形有n-1個(gè)，長(zhǎng)為n的長(zhǎng)方形和正方形有1個(gè)；根據(jù)乘法原理 s=(1+2+n)*( 1+2+m)= 4*)1 (*)1 (mnmn3.長(zhǎng)寬不等的長(zhǎng)方形個(gè)數(shù)s2顯然，s2=s-s1 = -4*)1 (*)1 (mnmn1,min0)(*)(nmiimin由此得出算法：#includeusing namespace std;int main() int n,m; cinmn; int m1=m,n1=n,s1=m*n; /計(jì)算正方形的個(gè)數(shù)s1 while (m1!=0&n

11、1!=0) m1-;n1-; s1+=m1*n1; int s2=(m+1)*(n+1)*m*n)/4-s1; / 計(jì)算長(zhǎng)方形的個(gè)數(shù)s2 couts1 s2endl; 【例例4】昆蟲繁殖【問題描述問題描述】 科學(xué)家在熱帶森林中發(fā)現(xiàn)了一種特殊的昆蟲，這種昆蟲的繁殖能力很強(qiáng)。每對(duì)成蟲過x個(gè)月產(chǎn)y對(duì)卵，每對(duì)卵要過兩個(gè)月長(zhǎng)成成蟲。假設(shè)每個(gè)成蟲不死，第一個(gè)月只有一對(duì)成蟲，且卵長(zhǎng)成成蟲后的第一個(gè)月不產(chǎn)卵(過X個(gè)月產(chǎn)卵)，問過Z個(gè)月以后，共有成蟲多少對(duì)？0=X=20,1=Y=20,X=Z=50【輸入格式輸入格式】 x,y,z的數(shù)值【輸出格式輸出格式】 過Z個(gè)月以后，共有成蟲對(duì)數(shù)【輸入樣例輸入樣例】 1 2

12、8【輸出樣例輸出樣例】 37【參考程序參考程序】#includeusing namespace std;int main() long long a101=0,b101=0,i,j,x,y,z; cinxyz; for(i=1;i=x;i+)ai=1;bi=0; for(i=x+1;i=z+1;i+) /因?yàn)橐y(tǒng)計(jì)到第z個(gè)月后，所以要for到z+1 bi=y*ai-x; ai=ai-1+bi-2; coutaz+1endl; return 0;【例例5】位數(shù)問題【問題描述問題描述】 在所有的N位數(shù)中，有多少個(gè)數(shù)中有偶數(shù)個(gè)數(shù)字3？由于結(jié)果可能很大，你只需要輸出這個(gè)答案對(duì)12345取余的值?！据斎?/p>

13、格式輸入格式】 讀入一個(gè)數(shù)N【輸出格式輸出格式】 輸出有多少個(gè)數(shù)中有偶數(shù)個(gè)數(shù)字3?！据斎霕永斎霕永?2【輸出樣例輸出樣例】 73【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模】 1=N=1000【樣例說明樣例說明】 在所有的2位數(shù)字，包含0個(gè)3的數(shù)有72個(gè)，包含2個(gè)3的數(shù)有1個(gè)，共73個(gè)【算法分析算法分析】方法一：排列組合(但需要運(yùn)用動(dòng)態(tài)規(guī)劃)。 可以列出公式,在n個(gè)格子中放x個(gè)3(其中x為偶數(shù),包括0).。 c(n,x)*9(n-x)-c(n-1,x)*9(n-x-1) 含義為在n個(gè)格子中取x個(gè)3,且不考慮第一位的特殊情況為c(n,x)*9(n-x)。 而第一位為0的情況,為c(n-1,x)*9(n-x-1),兩者

14、減下,就為答案。 方法二：遞推 考慮這種題目,一般來說都是從第i-1位推導(dǎo)第i位,且當(dāng)前位是取偶數(shù)還是取奇數(shù)的。 恍然大悟.可以用fi0表示前i位取偶數(shù)個(gè)3有幾種情況,fi1表示前i位取奇數(shù)個(gè)3有幾種情況。 則狀態(tài)轉(zhuǎn)移方程可以表示為:fi0=fi-10*9+fi-11;fi1=fi-10+fi-11*9; 邊界條件:f11=1;f10=9;【參考程序參考程序】#includeusing namespace std;int main() int f10012,n,i,x; cinn; f11=1;f10=9; for(i=2;i=n;i+) x=f10; if(i=n)x-; fi0=(fi-1

15、0*x+fi-11)%12345; fi1=(fi-11*x+fi-10)%12345; cout0且j0且gij= 0遞推邊界有4個(gè)：Fij = 0 /gij = 1Fi0 = Fi-10 /i 0且gi0 = 0F0j = F0j-1 /j 0且g0j = 0F00 = 1考慮到最大情況下：n=20,m=20，路徑條數(shù)可能會(huì)超過231-1,所以要用高精度?！纠?】郵票問題郵票問題【問題描述問題描述】設(shè)有已知面額的郵票m種，每種有n張，用總數(shù)不超過n張的郵票，能從面額1開始，最多連續(xù)組成多少面額。（1m100，1n100，1郵票面額255）【輸入格式輸入格式】第一行：m,n的值，中間用一空

16、格隔開。第二行：A1.m（面額），每個(gè)數(shù)中間用一空格隔開?！据敵龈袷捷敵龈袷健窟B續(xù)面額數(shù)的最大值【輸入樣例輸入樣例】stamp.in 3 4 1 2 4【輸出樣例輸出樣例】stamp.out14【算法分析算法分析】一看到這個(gè)題目，給人的第一感覺是用回溯算法，從面額1開始，每種面額都用回溯進(jìn)行判斷，算法復(fù)雜度并不高，但是當(dāng)m，n取到極限值100時(shí)，程序明顯超時(shí)，因此，回溯算法在這里并不可取。 能否用遞推完成呢?我們有一個(gè)思路:從面額1開始，建立遞推關(guān)系方程，就用范例來說吧，面額1，2，4只用1張郵票行了，面額3可以表示為面額1，2的郵票和1+1=2，面額5有兩種表示方式min(面額1+面額4，面

17、額2+面額3)，照此類推，遞推關(guān)系方程不難建立，就拿郵票問題來說，以下是遞推的一種方法: #includeusing namespace std;int n,m,i,j,k;int c256; /面額int a31001; /遞推數(shù)組bool b1;void readfile() /讀入數(shù)據(jù) cin m n; b1 = true; for (i = 1; i ci; if (ci = 1) b1 = false; void work() if (b1 = true) cout MAX=0; /不存在面額1時(shí)輸出無解 else i = 1; ai = 1; do i+; for (j = 1;

18、j = m; j+) if (i % cj = 0) & (i / cj) ai) | (ai = 0) ai = i / cj; /判斷它能否被題目給定面額整除 for (j = 1; j = i/2; j+) if (aj + ai-j ai) ai = aj + ai-j; /尋找(1=j=i),使aj+ai-j值最小 while (ai = n) & (ai != 0); cout i-1; /輸出 int main ( ) readfile() ; work(); return 0; 這種遞推方法雖然簡(jiǎn)單，由于1=郵票面額=255，1=n=100，因此MAX值最多可達(dá)

19、到25500，25500次循環(huán)里必定還有嵌套循環(huán)，因此算法不加優(yōu)化，很難在規(guī)定時(shí)間內(nèi)得出最優(yōu)值。這就需要遞推的算法優(yōu)化。 一味遞推不尋求算法優(yōu)化，速度較之搜索提高不少，但一旦數(shù)據(jù)規(guī)模過大，很難在規(guī)定時(shí)間內(nèi)得出最優(yōu)值。 這種遞推方法原理是:對(duì)于某種要求得到的面額，判斷它能否被題目給定面額整除，再尋找(1=j=i)，使Aj+Ai-j值最小，求出湊成某種面額最少郵票數(shù)，算法雖然簡(jiǎn)單，但還可以進(jìn)一步優(yōu)化。何不將用m種面額郵票作循環(huán)，建立遞推關(guān)系式:Ai=MAX(AI-Cj+1)，于是當(dāng)取到極限值時(shí)，程序減少了約1.6*108次循環(huán)，遞推優(yōu)化作用不言而喻。下面是改進(jìn)后的程序: #include#incl

20、udeusing namespace std;int x256;int pieces30001;int m,n,i,j;int main() cin m n; for (i = 1; i xi; memset(pieces,0,sizeof(pieces); int maxx = 0; do /遞推循環(huán) maxx+; for (i = 1; i = 0) /循環(huán),建立遞推關(guān)系式PIECESi=MAX(PIECESI-Xj+1) if (piecesmaxx = 0) piecesmaxx = piecesmaxx-xi + 1; if (piecesmaxxpiecesmaxx-xi+1) p

21、iecesmaxx = piecesmaxx-xi+1; if (piecesmaxx = 0) | (piecesmaxx n) cout 1,m1) 邊界條件可以由定義2推導(dǎo)出： S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。 第二類Stirling數(shù)在競(jìng)賽中較少出現(xiàn)，但在競(jìng)賽中也有一些題目與其類似，甚至更為復(fù)雜。讀者不妨自己來試著建立其中的遞推關(guān)系。 小結(jié)：通過上面對(duì)五種典型的遞推關(guān)系建立過程的探討，可知對(duì)待遞推類的題目，要具體情況具體分析，通過找到某狀態(tài)與其前面狀態(tài)的聯(lián)系，建立相應(yīng)的遞推關(guān)系。 【例【例7】(1998合肥市競(jìng)賽復(fù)試第二題合肥市競(jìng)

22、賽復(fù)試第二題)同一平面內(nèi)的同一平面內(nèi)的n(n500)條直線，已知有條直線，已知有p(p2)條直線相交于同一點(diǎn)，則這條直線相交于同一點(diǎn)，則這n條直線最多條直線最多能將平面分割成多少個(gè)不同的區(qū)域？能將平面分割成多少個(gè)不同的區(qū)域？ 解：這道題目與第一部分中的平面分割問題十分相似，不同之處就在于線條的曲直以及是否存在共點(diǎn)線條。由于共點(diǎn)直線的特殊性，我們決定先考慮p條相交于一點(diǎn)的直線，然后再考慮剩下的n-p條直線。首先可以直接求出p條相交于一點(diǎn)的直線將平面劃分成的區(qū)域數(shù)為2p個(gè)，然后在平面上已經(jīng)有k(kp)條直線的基礎(chǔ)上，加上一條直線，最多可以與k條直線相交，而每次相交都會(huì)增加一個(gè)區(qū)域，與最后一條直線相

23、交后，由于直線可以無限延伸，還會(huì)再增加一個(gè)區(qū)域。所以fm=fm-1+m (mp)，邊界條件在前面已經(jīng)計(jì)算過了，是fp=2p。雖然這題看上去有兩個(gè)參數(shù)，但是在實(shí)際做題中會(huì)發(fā)現(xiàn)，本題還是屬于帶一個(gè)參數(shù)的遞推關(guān)系?！旧蠙C(jī)練習(xí)上機(jī)練習(xí)】1、走樓梯、走樓梯樓梯有N級(jí)臺(tái)階，上樓可以一步上一階，也可以一步上二階。編一遞歸程序，計(jì)算共有多少種不同走法？【輸入樣例輸入樣例】Stairs.in3【輸出樣例輸出樣例】Stairs.out32、兔子繁殖、兔子繁殖有一種兔子，出生后一個(gè)月就可以長(zhǎng)大，然后再過一個(gè)月一對(duì)長(zhǎng)大的兔子就可以生育一對(duì)小兔子且以后每個(gè)月都能生育一對(duì)。現(xiàn)在，我們有一對(duì)剛出生的這種兔子，那么，n個(gè)月過

24、后，我們會(huì)有多少對(duì)兔子呢？假設(shè)所有的兔子都不會(huì)死亡。【輸入格式輸入格式】輸入文件僅一行，包含一個(gè)自然數(shù)n?！据敵龈袷捷敵龈袷健枯敵鑫募H一行，包含一個(gè)自然數(shù)，即n個(gè)月后兔子的對(duì)數(shù)?！据斎霕永斎霕永縍abbit.in5【輸出樣例輸出樣例】Rabbit.out53、平面分割、平面分割 同一平面內(nèi)有n（n500）條直線，已知其中p（p2）條直線相交于同一點(diǎn)，則這n條直線最多能將平面分割成多少個(gè)不同的區(qū)域？【輸入格式輸入格式】?jī)蓚€(gè)整數(shù)n（n500）和p（2pn）?！据敵龈袷捷敵龈袷健恳粋€(gè)正整數(shù)，代表最多分割成的區(qū)域數(shù)目?！据斎霕永斎霕永縎urface.in12 5【輸出樣例輸出樣例】Surface.out734、骨牌鋪法、骨牌鋪法 有1n的一個(gè)長(zhǎng)方形，用一個(gè)11、12和13的骨牌鋪滿方格。例如當(dāng)n=3時(shí)為13的方格。此時(shí)用11、12和13的骨牌鋪滿方格，共有四種鋪法。如下圖：【輸入樣例輸入樣例】Domino.in 3【輸出樣例輸出樣例】Domino.out 45、蜜蜂路線、蜜蜂路線【問題描述問題描述】 一只蜜蜂在下圖所示的數(shù)字蜂房上爬動(dòng),已知它只能從標(biāo)號(hào)小的蜂房爬到標(biāo)號(hào)大的相鄰蜂房,現(xiàn)在問你：蜜蜂從蜂房M開始爬到蜂房N，MN，有多少種爬行路線？【輸入格式輸入格式】