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

《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二（8頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法二 課題：遞推法 目標(biāo)： 知識(shí)目標(biāo)：遞推概念與利用遞推解決實(shí)際問(wèn)題 能力目標(biāo)：遞推方程 重點(diǎn)：遞推方程 難點(diǎn)：遞推方程寫出 板書示意： 1） 遞推的理解（例20） 2） 倒推法（例21） 3） 順推法（例22、例23） 授課過(guò)程： 遞推就是逐步推導(dǎo)的過(guò)程。我們先看一個(gè)簡(jiǎn)單的問(wèn)題。 例20：一個(gè)數(shù)列的第0項(xiàng)為0，第1項(xiàng)為1，以后每一項(xiàng)都是前兩項(xiàng)的和，這個(gè)數(shù)列就是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第N項(xiàng)。 分析：我們可以根據(jù)裴波那契數(shù)列的定義：從第2項(xiàng)開(kāi)始，逐項(xiàng)推算，直到第N項(xiàng)。因此可以設(shè)計(jì)出如下算法：

2、 F[0] := 1; F[1] := 2; FOR I := 2 TO N DO F[I] := F[I – 1] + F[I – 2]; 從這個(gè)問(wèn)題可以看出，在計(jì)算裴波那契數(shù)列的每一項(xiàng)目時(shí)，都可以由前兩項(xiàng)推出。這樣，相鄰兩項(xiàng)之間的變化有一定的規(guī)律性，我們可以將這種規(guī)律歸納成如下簡(jiǎn)捷的遞推關(guān)系式：Fn=g(Fn-1)，這就在數(shù)的序列中，建立起后項(xiàng)和前項(xiàng)之間的關(guān)系。然后從初始條件（或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值）。很多問(wèn)題就是這樣逐步求解的。 對(duì)一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件（或最終結(jié)果），問(wèn)題就可以遞推了，接下來(lái)便是

3、讓計(jì)算機(jī)一步步了。讓高速的計(jì)算機(jī)從事這種重復(fù)運(yùn)算，真正起到“物盡其用”的效果。 滿足求解 Y{順推} 初始條件F1 N{倒推} 由題意（或遞推關(guān)系）定初始值F1（邊界條件）求出順推關(guān)系式Fi=g(Fi-1)； 由題意（或遞推關(guān)系）確定最終結(jié)果Fn；求出倒推關(guān)系式Fi-1=g’(Fi)； I=1；{由邊界條件F1出發(fā)進(jìn)行順推} I=n；{從最終結(jié)果Fn出發(fā)進(jìn)行倒推} While 當(dāng)前結(jié)果Fi非最終結(jié)果Fn do While 當(dāng)前結(jié)果Fi非初始值F1 do

4、 由Fi=g(Fi-1)順推后項(xiàng)； 由Fi-1=g(Fi)倒推前項(xiàng)； 輸出順推結(jié)果Fn和順推過(guò)程； 輸出倒推結(jié)果F1和倒推過(guò)程； 遞推分倒推法和順推法兩種形式。算法流程如下： 一、倒推法 所謂倒推法，就是在問(wèn)題的解或目標(biāo)是由初始值遞推得到的問(wèn)題中，已知解或目標(biāo)，根據(jù)遞推關(guān)系，采用倒推手段，一步步的倒推直至求得這個(gè)問(wèn)題的初始陳述的方法。因?yàn)檫@類問(wèn)題的運(yùn)算過(guò)程是一一映射的，故可分析其遞推公式。看看下面的例題。 例21：貯油點(diǎn) 一輛重型卡車欲穿過(guò)1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過(guò)不了沙漠的。因此司機(jī)必須設(shè)法在沿

5、途建立若干個(gè)貯油點(diǎn)，使卡車能順利穿過(guò)沙漠。試問(wèn)司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲(chǔ)多少汽油，才能使卡車以消耗最少汽油的代價(jià)通過(guò)沙漠？ 編程計(jì)算及打印建立的貯油點(diǎn)序號(hào)，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。格式如下： No. Distance(k.m.) Oil(litre) 1 × × × × 2 × × × × … … … … … 分析： 設(shè)Way[I]——第I個(gè)貯油點(diǎn)到終點(diǎn)（I=0）的距離； oil[I]——第I個(gè)貯油點(diǎn)的貯油量； 圖19倒推過(guò)程 我們可以用倒推法來(lái)解決這個(gè)問(wèn)題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置及存油量。圖19表示倒

6、推時(shí)的返回點(diǎn)。 從貯油點(diǎn)I向貯油點(diǎn)I+1倒推的方法是：卡車在貯油點(diǎn)I和貯油點(diǎn)I+1間往返若干次。卡車每次返回I+1點(diǎn)時(shí)應(yīng)該正好耗盡500公升汽油，而每次從I+1點(diǎn)出發(fā)時(shí)又必須裝足500公升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下，使I點(diǎn)貯足I*500公升汽油的要求（0≦I≦n-1）。具體來(lái)說(shuō)，第一個(gè)貯油點(diǎn)I=1應(yīng)距終點(diǎn)I=0處500km，且在該點(diǎn)貯藏500公升汽油，這樣才能保證卡車能由I=1處到達(dá)終點(diǎn)I=0處，這就是說(shuō) Way[I]=500；oil[I]=500； 圖20 倒推到第二步 為了在I=1處貯藏500公升汽油，卡車至少?gòu)腎=2處開(kāi)兩趟滿載油的車至I=1處，所以I=2處至

7、少貯有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上從I=1返回至I=2處的一趟空載，合計(jì)往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d12=500/3km，Way[2]=Way[1]+d12=Way[I]+500/3 此時(shí)的狀況如圖20所示。 圖21 倒推到第三步 為了在I=2處貯藏1000公升汽油，卡車至少?gòu)腎=3處開(kāi)三趟滿載油的車至I=2處。所以I=3處至少貯有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3處的二趟返程空車，合計(jì)5次。路途耗油亦應(yīng)500公升，即d23=500/5， Way[3]=Way[2]+d

8、23=Way[2]+500/5； 此時(shí)的狀況如圖21所示。 依次類推，為了在I=k處貯藏k*500公升汽油，卡車至少?gòu)腎=k+1處開(kāi)k趟滿載車至I=k處，即oil[k+1]=(k+1)*500=oil[k]+500，加上從I=k返回I=k+1的k-1趟返程空間，合計(jì)2k-1次。這2k-1次總耗油量按最省要求為500公升，即dk,k+1=500/(2k-1)， 圖22倒推到第n步 Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)； 此時(shí)的狀況如圖22所示。 最后，I=n至始點(diǎn)的距離為1000-Way[n],oil[n]=500*n。為了在I=n處取得n

9、*500公升汽油，卡車至少?gòu)氖键c(diǎn)開(kāi)n+1次滿載車至I=n，加上從I=n返回始點(diǎn)的n趟返程空車，合計(jì)2n+1次，2n+1趟的總耗油量應(yīng)正好為（1000-Way[n]）*(2n+1)，即始點(diǎn)藏油為oil[n]+(1000-Way[n])*(2n+1)。 程序設(shè)計(jì)如下： program Oil_lib; var K: Integer; {貯油點(diǎn)位置序號(hào)} D, {累計(jì)終點(diǎn)至當(dāng)前貯油點(diǎn)的距離} D1: Real; {I=n至終點(diǎn)的距離} Oil, Way: array [1 .. 10] of

10、 Real; i: Integer; begin Writeln(‘No.’, ‘Distance’:30, ‘Oil’:80); K := 1; D := 500; {從I=1處開(kāi)始向終點(diǎn)倒推} Way[1] := 500; Oil[1] := 500; repeat K := K + 1; D := D + 500 / (2 * K – 1); Way[K] := D; Oil[K] := Oil[K – 1]

11、 + 500; until D >= 1000; Way[K] := 1000; {置始點(diǎn)到終點(diǎn)的距離值} D1 := 1000 – Way[K – 1]; {求I=n處至至點(diǎn)的距離} Oil[K] := D1 * (2 * k + 1) + Oil[K – 1]; {求始點(diǎn)貯油量} {由始點(diǎn)開(kāi)始，逐一打印至當(dāng)前貯油點(diǎn)的距離和貯油量} for i := 0 to K do Writeln(i, 1000 – Way[K – i]:30, Oil[K – i]:80); end.

12、 二、順推法 順推法是從邊界條件出發(fā)，通過(guò)遞推關(guān)系式推出后項(xiàng)值，再由后項(xiàng)值按遞推關(guān)系式推出再后項(xiàng)值……，依次類推，直至從問(wèn)題初始陳述向前推進(jìn)到這個(gè)問(wèn)題的解為止。 看看下面的問(wèn)題。 例22昆蟲(chóng)繁殖 科學(xué)家在熱帶森林中發(fā)現(xiàn)了一種特殊的昆蟲(chóng)，這種昆蟲(chóng)的繁殖能力很強(qiáng)。每對(duì)成蟲(chóng)過(guò)x個(gè)月產(chǎn)y對(duì)卵，每對(duì)卵要過(guò)兩個(gè)月長(zhǎng)成成蟲(chóng)。假設(shè)每個(gè)成蟲(chóng)不死，第一個(gè)月只有一對(duì)成蟲(chóng)，且卵長(zhǎng)成成蟲(chóng)后的第一個(gè)月不產(chǎn)卵(過(guò)X個(gè)月產(chǎn)卵)，問(wèn)過(guò)Z個(gè)月以后，共有成蟲(chóng)多少對(duì)？x>=1,y>=1,z>=x 輸入：x,y,z的數(shù)值 輸出：成蟲(chóng)對(duì)數(shù) 事例： 輸入：x=1 y=2 z=8 輸出：37 分析：首

13、先我們來(lái)看樣例：每隔1個(gè)月產(chǎn)2對(duì)卵，求過(guò)8月（即第8+1=9月）的成蟲(chóng)個(gè)數(shù) 月份 1 2 3 4 5 6 7 8 9 … 新增卵 0 2 2 2 6 10 14 26 46 … 成蟲(chóng) 1 1 1 3 5 7 13 23 37 … 設(shè)數(shù)組A[i]表示第I月新增的成蟲(chóng)個(gè)數(shù)。 由于新成蟲(chóng)每過(guò)x個(gè)月產(chǎn)y對(duì)卵，則可對(duì)每個(gè)A[I]作如下操作: A[i+k*x+2]:=A[i+k*x+2]+A[i]*y （1<=k, I+k*x+2<=z+1） 因?yàn)锳 [i]的求得只與A[1]~A[i-1]有關(guān)，即可用遞推求法。 則總共的成蟲(chóng)個(gè)數(shù)

14、為： 程序如下： program exam22; var x,y,z,i :integer; ans :longint; a :array[1..60]of longint; procedure add(i:integer); var j :integer; begin j:=i+2+x; {新生成蟲(chóng)要過(guò)x 個(gè)月才開(kāi)始產(chǎn)卵，即第I+2+x個(gè)月才出現(xiàn)第一群新成蟲(chóng)} repeat a[j]:=a[j]+a[i]*y; {遞推} j:=j+x until j>z+1

15、 end; begin readln(x,y,z); a[1]:=1; {初始化} for i:=1 to z do add(i); {對(duì)每個(gè)A[I]進(jìn)行遞推} ans:=0; for i:=1 to z+1 do ans:=ans+a[i]; {累加總和} writeln(ans); end. 例23：實(shí)數(shù)數(shù)列（NOI94第3題） 一個(gè)實(shí)數(shù)數(shù)列共有N項(xiàng)，已知 ai=(ai-1-ai+1)/2+d，(1

16、=(ai-1-ai+1)/2+d 變形得，ai+1=ai-1-2ai+2d，因此該數(shù)列的通項(xiàng)公式為：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，這樣就可以根據(jù)公式遞推求出am ∵ ai=ai-2-2ai-1+2d ……① =ai-2-2（ai-3-2ai-2+2d）+2d =-2ai-3+5（ai-4-2ai-3+2d）-2d =5ai-4-12ai-3+8d …… 一直迭代下去，直到最后，可以建立ai和a1與a2的關(guān)系式。 設(shè)ai=Pia2+Qid+Ria1，我們來(lái)尋求Pi,Qi,Ri的變化規(guī)律。 ∵ ai=ai-2-2ai

17、-1+2d ∴ ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 ∴ Pi=Pi-2-2Pi-1 ……② Qi=Qi-2-2Qi-1+2 ……③ Ri=Ri-2-2Ri-1 ……④ 顯然，P1=0 Q1=0 R1=1 （i=1） P2=1 Q2=0 R2=0 （i=2） 將初值P1、Q1、R1和P2、Q2、R2代入②③④可以求出Pn、Qn、Rn ∵ an=Pna2+

18、Qnd+Rna1 ∴ a2=(an-Qnd+Rna1)/Pn 然后根據(jù)公式①遞推求出am，問(wèn)題解決。 但仔細(xì)分析，上述算法有一個(gè)明顯的缺陷：在求由于在求a2要運(yùn)用除法，因此會(huì)存在實(shí)數(shù)誤差，這個(gè)誤差在以后遞推求am的過(guò)程又不斷的擴(kuò)大。在實(shí)際中，當(dāng)m超過(guò)30時(shí)，求出的am就明顯偏離正確值。顯然，這種算法雖簡(jiǎn)單但不可靠。 為了減少誤差，我們可設(shè)計(jì)如下算法： ∵ ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3 …… =Pi-2+kak+Qi-2+kd+Ri-2+kak-1 ∴

19、an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1 ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 ……⑤ 根據(jù)公式⑤，可以順推a2、a3、…、aM。雖然仍然存在實(shí)數(shù)誤差，但由于Pn-k+2遞減，因此最后得出的am要比直接利用公式①精確得多。 程序如下： program NOI94_3; const MaxN = 60; var N, M, i: Integer; D: Real; A: array [1 .. MaxN] of Real; F: array [1 .. MaxN,

20、1 .. 3] of Real; {F[i,1]：對(duì)應(yīng)Pi；F[i,2]：對(duì)應(yīng)Qi；F[i,3]：對(duì)應(yīng)Ri} procedure Init; begin Write(‘N, M, D =’); Readln(N, M, D); {輸入項(xiàng)數(shù)、輸出項(xiàng)序號(hào)和常數(shù)} Write(‘A1, A’, N, ‘ =’); Readln(A[1], A[N]); {輸入a1和an} end; procedure Solve; {根據(jù)公式Pi?Pi-2-2*Pi-1,Qi?Qi-2-2*Qi-1,Ri?Ri

21、-2-2*Ri-1求Pi、Qi、Ri } begin F[1, 1] := 0; F[1, 2] := 0; F[1, 3]:= 1; F[2, 1] := 1; F[2, 2] := 0; F[2, 3] := 0; for i := 3 to N do begin F[i, 1] := F[i – 2, 1] – 2 * F[i – 1, 1]; F[i, 2] := F[i – 2, 2] – 2 * F[i – 1, 2] + 2; F[i, 3] := F[i – 2, 3] – 2 * F[i – 1, 3]; end; end; procedure Main; begin Solve; {遞推A2…Am} for i := 2 to M do A[i]:=(A[N]–F[N–i+2,2]*D–F[N–i+2,3]*A[i–1])/F[N–i+2,1]; Writeln(‘a(chǎn)’, m, ‘ =’, A[M]:20 :10); end; begin Init; Main; end.