《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法二》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法二（8頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法二
課題：遞推法
目標(biāo)：
知識(shí)目標(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)。
分析：我們可以根據(jù)裴波那契數(shù)列的定義：從第2項(xiàng)開始，逐項(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è)問題可以看出，在計(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é)果（或初始值）。很多問題就是這樣逐步求解的。
對(duì)一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就可以遞推了，接下來便是
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和順推過程；
輸出倒推結(jié)果F1和倒推過程；
遞推分倒推法和順推法兩種形式。算法流程如下：
一、倒推法
所謂倒推法，就是在問題的解或目標(biāo)是由初始值遞推得到的問題中，已知解或目標(biāo)，根據(jù)遞推關(guān)系，采用倒推手段，一步步的倒推直至求得這個(gè)問題的初始陳述的方法。因?yàn)檫@類問題的運(yùn)算過程是一一映射的，故可分析其遞推公式。看看下面的例題。
例21：貯油點(diǎn)
一輛重型卡車欲穿過1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過不了沙漠的。因此司機(jī)必須設(shè)法在沿
5、途建立若干個(gè)貯油點(diǎn)，使卡車能順利穿過沙漠。試問司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲(chǔ)多少汽油，才能使卡車以消耗最少汽油的代價(jià)通過沙漠？
編程計(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倒推過程
我們可以用倒推法來解決這個(gè)問題。從終點(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間往返若干次?？ㄜ嚸看畏祷豂+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）。具體來說，第一個(gè)貯油點(diǎn)I=1應(yīng)距終點(diǎn)I=0處500km，且在該點(diǎn)貯藏500公升汽油，這樣才能保證卡車能由I=1處到達(dá)終點(diǎn)I=0處，這就是說
Way[I]=500；oil[I]=500；
圖20 倒推到第二步
為了在I=1處貯藏500公升汽油，卡車至少從I=2處開兩趟滿載油的車至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公升汽油，卡車至少從I=3處開三趟滿載油的車至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公升汽油，卡車至少從I=k+1處開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公升汽油，卡車至少從始點(diǎn)開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處開始向終點(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)開始，逐一打印至當(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ān)系式推出后項(xiàng)值，再由后項(xiàng)值按遞推關(guān)系式推出再后項(xiàng)值……，依次類推，直至從問題初始陳述向前推進(jìn)到這個(gè)問題的解為止。
看看下面的問題。
例22昆蟲繁殖
科學(xué)家在熱帶森林中發(fā)現(xiàn)了一種特殊的昆蟲，這種昆蟲的繁殖能力很強(qiáng)。每對(duì)成蟲過x個(gè)月產(chǎn)y對(duì)卵，每對(duì)卵要過兩個(gè)月長成成蟲。假設(shè)每個(gè)成蟲不死，第一個(gè)月只有一對(duì)成蟲，且卵長成成蟲后的第一個(gè)月不產(chǎn)卵(過X個(gè)月產(chǎn)卵)，問過Z個(gè)月以后，共有成蟲多少對(duì)？x>=1,y>=1,z>=x
輸入：x,y,z的數(shù)值
輸出：成蟲對(duì)數(shù)
事例：
輸入：x=1 y=2 z=8
輸出：37
分析：首
13、先我們來看樣例：每隔1個(gè)月產(chǎn)2對(duì)卵，求過8月（即第8+1=9月）的成蟲個(gè)數(shù)
月份
1
2
3
4
5
6
7
8
9
…
新增卵
0
2
2
2
6
10
14
26
46
…
成蟲
1
1
1
3
5
7
13
23
37
…
設(shè)數(shù)組A[i]表示第I月新增的成蟲個(gè)數(shù)。
由于新成蟲每過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)，即可用遞推求法。
則總共的成蟲個(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; {新生成蟲要過x 個(gè)月才開始產(chǎn)卵，即第I+2+x個(gè)月才出現(xiàn)第一群新成蟲}
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，我們來尋求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，問題解決。
但仔細(xì)分析，上述算法有一個(gè)明顯的缺陷：在求由于在求a2要運(yùn)用除法，因此會(huì)存在實(shí)數(shù)誤差，這個(gè)誤差在以后遞推求am的過程又不斷的擴(kuò)大。在實(shí)際中，當(dāng)m超過30時(shí)，求出的am就明顯偏離正確值。顯然，這種算法雖簡單但不可靠。
為了減少誤差，我們可設(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.
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞推法二
