《2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞推法二》由會員分享，可在線閱讀，更多相關《2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞推法二（8頁珍藏版）》請在裝配圖網上搜索。
1、2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞推法二
課題：遞推法
目標：
知識目標：遞推概念與利用遞推解決實際問題
能力目標：遞推方程
重點：遞推方程
難點：遞推方程寫出
板書示意：
1） 遞推的理解（例20）
2） 倒推法（例21）
3） 順推法（例22、例23）
授課過程：
遞推就是逐步推導的過程。我們先看一個簡單的問題。
例20：一個數列的第0項為0，第1項為1，以后每一項都是前兩項的和，這個數列就是著名的裴波那契數列，求裴波那契數列的第N項。
分析：我們可以根據裴波那契數列的定義：從第2項開始，逐項推算，直到第N項。因此可以設計出如下算法：
2、
F[0] := 1; F[1] := 2;
FOR I := 2 TO N DO
F[I] := F[I – 1] + F[I – 2];
從這個問題可以看出，在計算裴波那契數列的每一項目時，都可以由前兩項推出。這樣，相鄰兩項之間的變化有一定的規(guī)律性，我們可以將這種規(guī)律歸納成如下簡捷的遞推關系式：Fn=g(Fn-1)，這就在數的序列中，建立起后項和前項之間的關系。然后從初始條件（或是最終結果）入手，按遞推關系式遞推，直至求出最終結果（或初始值）。很多問題就是這樣逐步求解的。
對一個試題，我們要是能找到后一項與前一項的關系并清楚其起始條件（或最終結果），問題就可以遞推了，接下來便是
3、讓計算機一步步了。讓高速的計算機從事這種重復運算，真正起到“物盡其用”的效果。
滿足求解
Y{順推}
初始條件F1
N{倒推}
由題意（或遞推關系）定初始值F1（邊界條件）求出順推關系式Fi=g(Fi-1)；
由題意（或遞推關系）確定最終結果Fn；求出倒推關系式Fi-1=g’(Fi)；
I=1；{由邊界條件F1出發(fā)進行順推}
I=n；{從最終結果Fn出發(fā)進行倒推}
While 當前結果Fi非最終結果Fn do
While 當前結果Fi非初始值F1 do
4、
由Fi=g(Fi-1)順推后項；
由Fi-1=g(Fi)倒推前項；
輸出順推結果Fn和順推過程；
輸出倒推結果F1和倒推過程；
遞推分倒推法和順推法兩種形式。算法流程如下：
一、倒推法
所謂倒推法，就是在問題的解或目標是由初始值遞推得到的問題中，已知解或目標，根據遞推關系，采用倒推手段，一步步的倒推直至求得這個問題的初始陳述的方法。因為這類問題的運算過程是一一映射的，故可分析其遞推公式。看看下面的例題。
例21：貯油點
一輛重型卡車欲穿過1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過不了沙漠的。因此司機必須設法在沿
5、途建立若干個貯油點，使卡車能順利穿過沙漠。試問司機如怎樣建立這些貯油點？每一貯油點應存儲多少汽油，才能使卡車以消耗最少汽油的代價通過沙漠？
編程計算及打印建立的貯油點序號，各貯油點距沙漠邊沿出發(fā)的距離以及存油量。格式如下：
No.
Distance(k.m.)
Oil(litre)
1
× ×
× ×
2
× ×
× ×
…
… …
… …
分析：
設Way[I]——第I個貯油點到終點（I=0）的距離；
oil[I]——第I個貯油點的貯油量；
圖19倒推過程
我們可以用倒推法來解決這個問題。從終點向始點倒推，逐一求出每個貯油點的位置及存油量。圖19表示倒
6、推時的返回點。
從貯油點I向貯油點I+1倒推的方法是：卡車在貯油點I和貯油點I+1間往返若干次?？ㄜ嚸看畏祷豂+1點時應該正好耗盡500公升汽油，而每次從I+1點出發(fā)時又必須裝足500公升汽油。兩點之間的距離必須滿足在耗油最少的條件下，使I點貯足I*500公升汽油的要求（0≦I≦n-1）。具體來說，第一個貯油點I=1應距終點I=0處500km，且在該點貯藏500公升汽油，這樣才能保證卡車能由I=1處到達終點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處的一趟空載，合計往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d12=500/3km，Way[2]=Way[1]+d12=Way[I]+500/3
此時的狀況如圖20所示。
圖21 倒推到第三步
為了在I=2處貯藏1000公升汽油，卡車至少從I=3處開三趟滿載油的車至I=2處。所以I=3處至少貯有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3處的二趟返程空車，合計5次。路途耗油亦應500公升，即d23=500/5，
Way[3]=Way[2]+d
8、23=Way[2]+500/5；
此時的狀況如圖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趟返程空間，合計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)；
此時的狀況如圖22所示。
最后，I=n至始點的距離為1000-Way[n],oil[n]=500*n。為了在I=n處取得n
9、*500公升汽油，卡車至少從始點開n+1次滿載車至I=n，加上從I=n返回始點的n趟返程空車，合計2n+1次，2n+1趟的總耗油量應正好為（1000-Way[n]）*(2n+1)，即始點藏油為oil[n]+(1000-Way[n])*(2n+1)。
程序設計如下：
program Oil_lib;
var
K: Integer; {貯油點位置序號}
D, {累計終點至當前貯油點的距離}
D1: Real; {I=n至終點的距離}
Oil, Way: array [1 .. 10] of
10、 Real;
i: Integer;
begin
Writeln(‘No.’, ‘Distance’:30, ‘Oil’:80);
K := 1;
D := 500; {從I=1處開始向終點倒推}
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; {置始點到終點的距離值}
D1 := 1000 – Way[K – 1]; {求I=n處至至點的距離}
Oil[K] := D1 * (2 * k + 1) + Oil[K – 1]; {求始點貯油量}
{由始點開始，逐一打印至當前貯油點的距離和貯油量}
for i := 0 to K do
Writeln(i, 1000 – Way[K – i]:30, Oil[K – i]:80);
end.
12、
二、順推法
順推法是從邊界條件出發(fā)，通過遞推關系式推出后項值，再由后項值按遞推關系式推出再后項值……，依次類推，直至從問題初始陳述向前推進到這個問題的解為止。
看看下面的問題。
例22昆蟲繁殖
科學家在熱帶森林中發(fā)現了一種特殊的昆蟲，這種昆蟲的繁殖能力很強。每對成蟲過x個月產y對卵，每對卵要過兩個月長成成蟲。假設每個成蟲不死，第一個月只有一對成蟲，且卵長成成蟲后的第一個月不產卵(過X個月產卵)，問過Z個月以后，共有成蟲多少對？x>=1,y>=1,z>=x
輸入：x,y,z的數值
輸出：成蟲對數
事例：
輸入：x=1 y=2 z=8
輸出：37
分析：首
13、先我們來看樣例：每隔1個月產2對卵，求過8月（即第8+1=9月）的成蟲個數
月份
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
…
設數組A[i]表示第I月新增的成蟲個數。
由于新成蟲每過x個月產y對卵，則可對每個A[I]作如下操作:
A[i+k*x+2]:=A[i+k*x+2]+A[i]*y （1<=k, I+k*x+2<=z+1）
因為A [i]的求得只與A[1]~A[i-1]有關，即可用遞推求法。
則總共的成蟲個數
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 個月才開始產卵，即第I+2+x個月才出現第一群新成蟲}
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); {對每個A[I]進行遞推}
ans:=0;
for i:=1 to z+1 do ans:=ans+a[i]; {累加總和}
writeln(ans);
end.
例23：實數數列（NOI94第3題）
一個實數數列共有N項，已知
ai=(ai-1-ai+1)/2+d，(1
16、=(ai-1-ai+1)/2+d 變形得，ai+1=ai-1-2ai+2d，因此該數列的通項公式為：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，這樣就可以根據公式遞推求出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的關系式。
設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
然后根據公式①遞推求出am，問題解決。
但仔細分析，上述算法有一個明顯的缺陷：在求由于在求a2要運用除法，因此會存在實數誤差，這個誤差在以后遞推求am的過程又不斷的擴大。在實際中，當m超過30時，求出的am就明顯偏離正確值。顯然，這種算法雖簡單但不可靠。
為了減少誤差，我們可設計如下算法：
∵ 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 ……⑤
根據公式⑤，可以順推a2、a3、…、aM。雖然仍然存在實數誤差，但由于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]：對應Pi；F[i,2]：對應Qi；F[i,3]：對應Ri}
procedure Init;
begin
Write(‘N, M, D =’);
Readln(N, M, D); {輸入項數、輸出項序號和常數}
Write(‘A1, A’, N, ‘ =’);
Readln(A[1], A[N]); {輸入a1和an}
end;
procedure Solve;
{根據公式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’, m, ‘ =’, A[M]:20 :10);
end;
begin
Init;
Main;
end.
2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞推法二
