2019-2020年高中信息技術(shù)全國青少年奧林匹克聯(lián)賽教案遞推法

1、2019-2020年高中信息技術(shù)全國青少年奧林匹克聯(lián)賽教案遞推法所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系， 逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡后確可用遞推算法求解的題目一般有以下二個(gè)特點(diǎn)：(1)問題可以劃分成多個(gè)狀態(tài)；(2)除初始狀態(tài)外，其它各個(gè)狀態(tài)都可以用固定的遞推關(guān)系式來表示。在我們實(shí)際解題中， 題目不會直接給出遞推關(guān)系式，而是需要通過分析各種狀態(tài)，找出遞推關(guān)系式。遞推法應(yīng)用任務(wù)1:當(dāng)N,M輸入之后，找出一條從左下角到右上角的路徑。 例如：輸入N=4,M=4I,。輸出：路徑的格式：(1,1)-(2,3)-(4,4)

2、若不存在路徑，則輸出no任務(wù)2:當(dāng)N,M給出之后，同時(shí)給出馬起始的位置和終點(diǎn)的位置，試找出從起點(diǎn)到終點(diǎn)的所有 路徑的數(shù)目。輸出:2(即由(1,5)到(3,5)共有2條路徑)輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起點(diǎn)坐標(biāo)，終點(diǎn)坐標(biāo))輸出格式：路徑數(shù)目(若不存在從起點(diǎn)到終點(diǎn)的路徑，輸出0)算法分析：為了研究的方便，我們先將棋盤的橫坐標(biāo)規(guī)定為i，縱坐標(biāo)規(guī)定為j，對于一個(gè)起點(diǎn)),(3,5)(終點(diǎn))nXm的棋盤，i的值從1到n,j的值從1到m。棋盤上的任意點(diǎn)都可以用坐標(biāo)（i,j）表示。對于馬的移動方法，我們用K來表示四種移動方向（1,2,3,4）;而每種移動方法用偏移值來表示，并將這

3、些偏移值分別保存在數(shù)組dx和dy中，如下表KDxkDyk12122-131241-2根據(jù)馬走的規(guī)則，馬可以由（i-dxk,j-dyk）走到（i,j）。只要馬能從（1,1）走到 （i-dxk,j-dyk），就一定能走到（i,j）,馬走的坐標(biāo)必須保證在棋盤上。我們以（n,m）為起點(diǎn)向左遞推，當(dāng)遞推到（i-dxk,j-dyk）的位置是（1,1）時(shí)，就找到了一條從（1,1）至U（ n,m）的路徑。我們用一個(gè)二維數(shù)組a表示棋盤，對于任務(wù)一，使用倒推法，從終點(diǎn)（n,m）往左遞推，設(shè)初始值an,m為（-1,-1）,如果從（i,j）一步能走到（n,m），就將（n,m）存放在ai,j中。如下表，a3,2和a2,

4、3的值是（4,4）,表示從這兩個(gè)點(diǎn)都可以到達(dá)坐標(biāo)（4,4）。從（1,1）可到達(dá)（2,3）、 （3,2）兩個(gè)點(diǎn)，所以a1,1存放兩個(gè)點(diǎn)中的任意一個(gè)即可。遞推結(jié)束以 后，如果a1,1值為（0,0）說明不存在路徑，否則a1,1值就是馬走下一步的坐標(biāo)，以此遞推輸出路徑。-1,-14,44,42,3任務(wù)一的源程序:con stdx:array1.4of in teger=(2,2,1,1);dy:array1.4of in teger=(1,-1,2,-2);typemap=recordx,y:i nteger;en d;vari,j, n,m,k:i nteger;a:array0.50,0.50of

5、 map;beginread( n, m);fillchar(a,sizeof(a),0);an,m.x:=-1;an,m.y:=-1;標(biāo)記為終點(diǎn)for i:=n dow nto 2 do 倒推for j:=1 to m doif ai,j.x0 thenfor k:=1 to 4 dobeginai-dxk,j-dyk.x:=i;ai-dxk,j-dyk.y:=j;end;if a1,1.x=0 then writeln(no)else begin存在路徑i:=1;j:=1;write(,i,j,);while ai,j.x-1 dobegink:=i;i:=ai,j.x;j:=ak,j.y

6、;write(-(,i,j,);end;end;end.對于任務(wù)二，也可以使用遞推法，用數(shù)組Ai,j存放從起點(diǎn)(x1,y1)到(i,j)的路徑 總數(shù)，按同樣的方法從左向右遞推，一直遞推到(x2,y2)，ax2,y2即為所求的解。源程 序(略)在上面的例題中， 遞推過程中的某個(gè)狀態(tài)只與前面的一個(gè)狀態(tài)有關(guān)， 遞推關(guān)系并不復(fù)雜， 如果在遞推中的某個(gè)狀態(tài)與前面的所有狀態(tài)都有關(guān)， 就不容易找出遞推關(guān)系式， 這就需要我 們對實(shí)際問題進(jìn)行分析與歸納， 從中找到突破口， 總結(jié)出遞推關(guān)系式。 我們可以按以下四個(gè) 步驟去分析：(1)細(xì)心的觀察；(2)豐富的聯(lián)想；(3)不斷地嘗試；(4)總結(jié)出遞推關(guān)系式。下面我們再

7、看一個(gè)復(fù)雜點(diǎn)的例子。例2、棧(noipxxpj)題目大意：求n個(gè)數(shù)通過棧后的排列總數(shù)。(K nW18)如輸入3輸出5算法分析：先模擬入棧、出棧操作，看看能否找出規(guī)律，我們用f(n)表示n個(gè)數(shù)通過棧操作后的排列總數(shù)，當(dāng)n很小時(shí)，很容易模擬出f(1)=1;f(2)=2;f(3)=5,通過觀察，看不出它們之間的遞推關(guān)系，我們再分析N=4的情況，假設(shè)入棧前的排列為“4321”，按第一個(gè)數(shù)“4”在出棧后的位置進(jìn)行分情況討論：(1)若“4”最先輸出，剛好與N=3相同，總數(shù)為f(3);(2)若“4”第二個(gè)輸出，則在“4”的前只能是“1”，“23”在“4”的后面，這時(shí)可以分別看作是N=1和N=2時(shí)的二種情況，

8、排列數(shù)分別為f(1)和f(2),所以此時(shí)的總數(shù)為f(1)*f(2);(3)若“4”第三個(gè)輸出，則“4”的前面二個(gè)數(shù)為“12”,后面一個(gè)數(shù)為“3”，組成 的排列總數(shù)為f(2)*f(1);(4)若“4”第四個(gè)輸出，與情況(1)相同，總數(shù)為f(3);所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);若設(shè)0個(gè)數(shù)通過棧后的排列總數(shù)為：f(0)=1;上式可變?yōu)椋篺(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0);再進(jìn)一步推導(dǎo)，不難推出遞推式：f(n )=f(O)*f( n-1)+f(1)*f( n-2)+f(n-1)*f(0);即f(n)=

9、(n=1)初始值：f(0)=1;有了以上遞推式，就很容易用遞推法寫出程序。vara:array0.18of longint;n ,i,j:i nteger;beginreadl n(n);fillchar(a,sizeof(a),0);a0:=1;for i:=1 to n dofor j:=0 to i-1 do ai:=ai+aj*ai-j-1;writel n(a n);en d.遞推算法最主要的優(yōu)點(diǎn)是算法結(jié)構(gòu)簡單，程序易于實(shí)現(xiàn)，難點(diǎn)是從問題的分析中找出解決問題的遞推關(guān)系式。對于以上兩個(gè)例子，如果在比賽中找不出遞推關(guān)系式，也可以用回溯法求解。2019-2020年高中信息技術(shù) 全國青少年奧

10、林匹克聯(lián)賽教案遞推法二課題：遞推法目標(biāo):知識目標(biāo)： 遞推概念與利用遞推解決實(shí)際問題能力目標(biāo):遞推方程重點(diǎn)：遞推方程 難點(diǎn)：遞推方程寫出板書示意:1)遞推的理解(例20)2)倒推法(例21)3)順推法(例22、例23)授課過程:遞推就是逐步推導(dǎo)的過程。我們先看一個(gè)簡單的問題。例20： 一個(gè)數(shù)列的第0項(xiàng)為0,第1項(xiàng)為1，以后每一項(xiàng)都是前兩項(xiàng)的和，這個(gè)數(shù)列就 是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第N項(xiàng)。I=0)f n = *2(n =1)JnjL + fn/(n A2 )分析：我們可以根據(jù)裴波那契數(shù)列的定義：從第2項(xiàng)開始，逐項(xiàng)推算，直到第N項(xiàng)。因此可以設(shè)計(jì)出如下算法：F0 := 1; F1 :=

11、2;FOR I := 2 TO N DOFI：= FI-1 + FI-2;從這個(gè)問題可以看出，在計(jì)算裴波那契數(shù)列的每一項(xiàng)目時(shí)，都可以由前兩項(xiàng)推出。這樣，相鄰兩項(xiàng)之間的變化有一定的規(guī)律性，我們可以將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式：Fn=g(Fn-1),這就在數(shù)的序列中， 建立起后項(xiàng)和前項(xiàng)之間的關(guān)系。然后從初始條件(或是最終結(jié)果)入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果(或初始值)。很多問題就是這樣逐步求解的。對一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件(或最終結(jié)果)，問題就可以遞推了， 接下來便是讓計(jì)算機(jī)一步步了。 讓高速的計(jì)算機(jī)從事這種重復(fù)運(yùn)算， 真 正起到“物盡其用”的

12、效果。遞推分倒推法和順推法兩種形式。算法流程如下：滿足求解初始條件F1-一丫順推_ _一N倒推由題意(或遞推關(guān)系)定初始值F1(邊 界條件)求出順推關(guān)系式Fi=g(Fi-1);由題意(或遞推關(guān)系)確定最終結(jié)果Fn；求出倒推關(guān)系式Fi-1=gFi);I=1;由邊界條件F1出發(fā)進(jìn)行順推l=n ; 從最終結(jié)果Fn出發(fā)進(jìn)行倒推While當(dāng)前結(jié)果Fi非最終結(jié)果FndoWhile當(dāng)前結(jié)果Fi非初始值F1do由Fi=g(Fi-1)順推后項(xiàng)；由Fi-1=g(Fi)倒推前項(xiàng)；輸出順推結(jié)果Fn和順推過程；輸出倒推結(jié)果F1和倒推過程；一、倒推法所謂倒推法，就是在問題的解或目標(biāo)是由初始值遞推得到的問題中，已知解或目標(biāo)

13、，根 據(jù)遞推關(guān)系，采用倒推手段，一步步的倒推直至求得這個(gè)問題的初始陳述的方法。因?yàn)檫@類問題的運(yùn)算過程是一一映射的，故可分析其遞推公式?？纯聪旅娴睦}。例21:貯油點(diǎn)一輛重型卡車欲穿過1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過不了沙漠的。 因此司機(jī)必須設(shè)法在沿途建立若干個(gè)貯油點(diǎn)， 使 卡車能順利穿過沙漠。 試問司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲多少汽油，才能使卡車以消耗最少汽油的代價(jià)通過沙漠？編程計(jì)算及打印建立的貯油點(diǎn)序號，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。格式 如下：Dista nce(k.m.)Oil(litre)X XX X分

14、析：設(shè)Wayl第I個(gè)貯油點(diǎn)到終點(diǎn)(1=0)的距離；oill第I個(gè)貯油點(diǎn)的貯油量；我們可以用倒推法來解決這個(gè)問題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置及 存油量。圖19表示倒推時(shí)的返回點(diǎn)。終點(diǎn)起點(diǎn)111=0 1-1 1=2圖 19 倒推過程從貯油點(diǎn)I向貯油點(diǎn)I+1倒推的方法是：卡車在貯油點(diǎn)I和貯油點(diǎn)I+1間往返若干次?？ㄜ嚸看畏祷?+1點(diǎn)時(shí)應(yīng)該正好耗盡500公升汽油，而每次從1+1點(diǎn)出發(fā)時(shí)又必須裝足500公升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下，使I點(diǎn)貯足1*500公升汽油的要求(0WIwn-1)。具體來說，第一個(gè)貯油點(diǎn)1=1應(yīng)距終點(diǎn)I=0處500km,且在該點(diǎn)貯藏500公升汽油

15、，這樣才能保證卡車能由1=1處到達(dá)終點(diǎn)I=0處，這就是說WayI=500;oilI=500;為了在I=1處貯藏500公升汽油， 卡車至少從1=2處開兩趟滿載油的車至1=1處， 所以1=2處至少貯有2*500公升汽油，即oil2=500*2=1000;另外，再加上從I=1返回至1=2處的一趟空載，合計(jì)往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d12=500/3km,Way2=Way1+d12=Wayl+500/3此時(shí)的狀況如圖20所示。No.12終點(diǎn)冬一5001=0起1-1圖 20 倒推到第二步一500圖 21 倒推到第三步為了在1=2處貯藏1000公升汽油，卡車至少從1=3處

16、開三趟滿載油的車至1=2處。所 以1=3處至少貯有3*500公升汽油，即oil3=500*3=1500。加上1=2至1=3處的二趟返程 空車，合計(jì)5次。路途耗油亦應(yīng)500公升，即d23=500/5，Way3=Way2+d23=Way2+500/5；此時(shí)的狀況如圖21所示。依次類推，為了在I=k處貯藏k*500公升汽油，卡車至少從I=k+1處開k趟滿載車至l=k處，即oilk+1=(k+1)*500=oilk+500，加上從l=k返回I=k+1的k-1趟返程空間，合計(jì)2k-1次。這2k-1次總耗油量按最省要求為500公升，即dk,k+1=500/(2k-1)，Wayk+1=Wayk+dk,k+1

17、=Wayk+500/(2k-1)；此時(shí)的狀況如圖22所示。II縮占 a 八譏*-Wayn最后，l=n至始點(diǎn)的距離為1000-Wayn,oiln=500*n。為了在l=n處取得n*500公升汽油，卡車至少從始點(diǎn)開n+1次滿載車至l=n，加上從l=n返回始點(diǎn)的n趟返程空車，合計(jì)2n+1次，2n+1趟的總耗油量應(yīng)正好為(1000-Wayn)*(2n+1)，即始點(diǎn)藏油為oil n+(1000-Way n)*(2 n+1)程序設(shè)計(jì)如下：program Oilib;貯油點(diǎn)位置序號累計(jì)終點(diǎn)至當(dāng)前貯油點(diǎn)的距離varK: In teger;D,D1: Real; l=n1=01=11=21=3圖 22 倒推到第

18、 n 步至終點(diǎn)的距離Oil, Way: array 1 . 10 of Real;i: In teger;beginWriteln(No.,Distanee:30,Oil:80);K := 1;D := 500;從I=1處開始向終點(diǎn)倒推Way1 := 500;Oil1 := 500;repeatK := K + 1;D := D + 500 / (2 * K-1);WayK := D;OilK := OilK-1 + 500;un til D = 1000;WayK := 1000;置始點(diǎn)到終點(diǎn)的距離值D1 := 1000-WayK-1;求l=n處至至點(diǎn)的距離OilK := D1 * (2 *

19、 k + 1) + OilK-1; 求始點(diǎn)貯油量由始點(diǎn)開始，逐一打印至當(dāng)前貯油點(diǎn)的距離和貯油量for i := 0 to K doWriteln(i, 1000-WayK-i:30, OilK-i:80);en d.二、順推法順推法是從邊界條件出發(fā)，通過遞推關(guān)系式推出后項(xiàng)值，再由后項(xiàng)值按遞推關(guān)系式推出再后項(xiàng)值.，依次類推，直至從問題初始陳述向前推進(jìn)到這個(gè)問題的解為止?？纯聪旅娴膯栴}。例22昆蟲繁殖科學(xué)家在熱帶森林中發(fā)現(xiàn)了一種特殊的昆蟲，這種昆蟲的繁殖能力很強(qiáng)。每對成蟲過x個(gè)月產(chǎn)y對卵，每對卵要過兩個(gè)月長成成蟲。假設(shè)每個(gè)成蟲不死，第一個(gè)月只有一對成蟲， 且卵長成成蟲后的第一個(gè)月不產(chǎn)卵（過X個(gè)月產(chǎn)

20、卵），問過Z個(gè)月以后，共有成蟲多少對？x=1,y=1,z=x輸入：x,y,z的數(shù)值輸出：成蟲對數(shù)事例：月份123456789新增卵0222610142646成蟲111357132337數(shù)由于新成蟲每過x個(gè)月產(chǎn)y對卵，則可對每個(gè)AI作如下操作Ai+k*x+2:=Ai+k*x+2+Ai*y(1=k,I+k*x+2z+i end;beginreadln(x,y,z); ai:=i;for i:=i to z do add(i);ans:=0;遞推初始化對每個(gè)AI進(jìn)行遞推for i:=1 to z+1 do ans:=ans+ai; 累加總和 writeln(ans);end.例23：實(shí)數(shù)數(shù)列(NOI

21、94第3題) 一個(gè)實(shí)數(shù)數(shù)列共有N項(xiàng)，已知ai=(ai-1-ai+1)/2+d，(1IN) (N60)鍵盤輸入N, d,ai,an,m輸出a。 輸入數(shù)據(jù)均不需判錯(cuò)。分析：根據(jù)公式ai=(ai-1-ai+1)/2+d變形得,ai+1=ai-1-2ai+2d,因此該數(shù)列的通項(xiàng)公式為：a =a-2-2ai-i+2d，已知ai，如果能求出a2,這樣就可以根據(jù)公式遞推求出amai=a-2-2ai-i+2d.=ai-2-2(ai-3-2ai-2+2d)+2d=-2ai-3+5(ai-4-2ai-3+2d)-2d=5ai-4-i2ai-3+8d輸入：x=1 y=2 z=8輸出：37分析：首先我們來看樣例：每隔

22、1個(gè)月產(chǎn)2對卵，求過8月（即第8+1=9月）的成蟲個(gè)設(shè)數(shù)組Ai表示第I月新增的成蟲個(gè)數(shù)。一直迭代下去，直到最后，可以建立ai和ai與a2的關(guān)系式。設(shè)ai=Ra2+Qd+Rai，我們來尋求R,Qi,Ri的變化規(guī)律。ai=ai-2-2ai-i+2dai=R-2a2+Q2d+R-2ai-2(R-ia2+Qid+R-iai)+2d=(Pi-2-2Pi-i)a2+(Qi-2-2Qi-i+2)d+(Ri-2-2Ri-i)ai Pi=R-2-2Pi-iQ=Q-2-2Qi-i+2Ri=Ri-2-2Ri-i顯然，Pi=0 Qi=0 Ri=i(i=i)P2=i Q2=0 R2=0(i=2)將初值Pi、Q、Ri和P2、Q、R代入可以求出Pn、Q、Ran=Pna2+Qd+Raia2=(an-Qnd+Rnai)/Pn然后根據(jù)公式遞推求出am,問題解決。但仔細(xì)分析，上述算法有一個(gè)明顯的缺陷：在求由于在求a2要運(yùn)用除法，因此會存在實(shí)數(shù)誤差，這個(gè)誤差在以后遞推求am的過程又不斷的擴(kuò)大。在實(shí)際中，當(dāng)m超過30時(shí)，求出的am就明顯偏離正確值。顯然，這種算法雖簡單但不可靠。為了減少誤差，我們可設(shè)計(jì)如下算法：ai=P a2+Qd+Rai=Pi-ia3+Qi-id+Ri-ia2=Pi-2a4+Qi-2d+Ri-2a3=Pi-2+kak+Qi-2+kd+Ri-2+kak-ian= Pn-k+2ak+ Qn-k+2d +