《高中信息技术全国青少年奥林匹克联赛教案递推法二.pdf》由会员分享，可在线阅读，更多相关《高中信息技术全国青少年奥林匹克联赛教案递推法二.pdf（8页珍藏版）》请在三一文库上搜索。
1、1 递推法 课题：递推法 目标： 知识目标：递推概念与利用递推解决实际问题 能力目标：递推方程 重点：递推方程 难点：递推方程写出 板书示意： 1） 递推的理解（例20） 2） 倒推法（例21） 3） 顺推法（例22、例 23） 授课过程： 递推就是逐步推导的过程。我们先看一个简单的问题。 例 20：一个数列的第0 项为 0，第 1 项为 1，以后每一项都是前两项的和，这个数列就 是著名的裴波那契数列，求裴波那契数列的第N项。 分析：我们可以根据裴波那契数列的定义：从第2 项开始，逐项推算，直到第N项。因 此可以设计出如下算法： F0 := 1; F1 := 2; FOR I := 2 TO
2、N DO FI := FI 1 + FI 2; 从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样， 相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式： Fn=g(Fn-1) ，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件 （或是最终 结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步 求解的。 对一个试题， 我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果） ， 问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算， 真正起到“物尽其用”的效果。 2 1
3、2 01 21 nff n n f nn n 2 递推分倒推法和顺推法两种形式。算法流程如下： 一、倒推法 所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根 据递推关系， 采用倒推手段， 一步步的倒推直至求得这个问题的初始陈述的方法。因为这类 问题的运算过程是一一映射的，故可分析其递推公式。看看下面的例题。 例 21：贮油点 一辆重型卡车欲穿过1000 公里的沙漠， 卡车耗汽油为1 升/ 公里， 卡车总载油能力为500 公升。 显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使 卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存
4、储多少汽油，才能 使卡车以消耗最少汽油的代价通过沙漠？ 编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式 如下： No. Distance(k.m.) Oil(litre) 1 2 , 分析： 设 WayI 第 I 个贮油点到终点（I=0 ）的距离； oilI第 I 个贮油点的贮油量； 我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及 存油量。图19 表示倒推时的返回点。 从贮油点I 向贮油点I+1 倒推的方法是：卡车在贮油点 I 和贮油点I+1 间往返若干次。 卡车每次返回I+1 点时应该正好耗尽500 公升汽油， 而每次从I+1 点出
5、发时又必须装足500 图 19 倒推过程 满足求解 Y 顺推 初始条件 F1 N 倒推 由题意 （或递推关系）定初始值F1（边 界条件）求出顺推关系式Fi=g(F i-1) ； 由题意（或递推关系）确定最终结果 Fn；求出倒推关系式 Fi-1 =g (Fi) ； I=1 ； 由边界条件F1出发进行顺推 I=n ； 从最终结果Fn出发进行倒推 While 当前结果Fi非最终结果Fn do While 当前结果Fi非初始值F1 do 由 Fi=g(F i-1) 顺推后项； 由 Fi-1=g(F i) 倒推前项； 输出顺推结果Fn和顺推过程；输出倒推结果F1和倒推过程； 3 公升汽油。 两点之间的距
6、离必须满足在耗油最少的条件下，使 I 点贮足 I*500 公升汽油的要 求（ 0I n-1 ） 。具体来说，第一个贮油点I=1 应距终点I=0 处 500km ，且在该点贮藏500 公升汽油，这样才能保证卡车能由I=1 处到达终点I=0 处，这就是说 WayI=500 ；oilI=500； 为了在 I=1 处贮藏 500 公升汽油，卡车至少从I=2 处开两趟满载油的车至I=1 处，所以 I=2 处至少贮有2*500 公升汽油 ，即 oil2=500*2=1000；另外，再加上从I=1 返回至 I=2 处的一趟空载，合计往返3 次。三次往返路程的耗油量按最省要求只能为500 公升，即 d12=5
7、00/3km，Way2=Way1+d12=WayI+500/3 此时的状况如图20 所示。 为了在 I=2 处贮藏 1000 公升汽油，卡车至少从I=3 处开三趟满载油的车至I=2 处。所 以 I=3 处至少贮有3*500 公升汽油，即oil3=500*3=1500。加上 I=2 至 I=3 处的二趟返程 空车，合计5 次。路途耗油亦应500 公升， 即 d23=500/5 ， Way3=Way2+d 23=Way2+500/5 ； 此时的状况如图21 所示。 依次类推，为了在 I=k 处贮藏 k*500 公升汽油，卡车至少从I=k+1 处开 k 趟满载车至I=k 处，即 oilk+1=(k+
8、1)*500=oilk+500，加上从 I=k 返回 I=k+1 的 k-1 趟返程空间，合计 2k-1 次。这 2k-1 次总耗油量按最省要求为500 公升，即dk,k+1=500/(2k-1)， 图 20 倒推到第二步 图 21 倒推到第三步 4 Wayk+1=Wayk+dk,k+1=Wayk+500/(2k-1)； 此时的状况如图22 所示。 最后， I=n 至始点的距离为1000-Wayn,oiln=500*n。为了在 I=n 处取得 n*500 公升 汽油，卡车至少从始点开n+1 次满载车至I=n ，加上从 I=n 返回始点的n 趟返程空车，合计 2n+1 次 ， 2n+1趟 的 总
9、 耗 油 量 应 正 好 为 （ 1000-Wayn ） *(2n+1) ， 即 始 点 藏 油 为 oiln+(1000-Wayn)*(2n+1)。 程序设计如下： program Oil_lib; var K: Integer; 贮油点位置序号 D, 累计终点至当前贮油点的距离 D1: Real; I=n至终点的距离 Oil, Way: array 1 10 of Real; i: Integer; begin Writeln(No., Distance :30, Oil :80); K := 1; D := 500; 从 I=1 处开始向终点倒推 Way1 := 500; Oil1 :=
10、 500; repeat K := K + 1; D := D + 500 / (2 * K 1); WayK := D; OilK := OilK 1 + 500; until D = 1000; WayK := 1000; 置始点到终点的距离值 D1 := 1000 WayK 1; 求 I=n 处至至点的距离 OilK := D1 * (2 * k + 1) + OilK 1; 求始点贮油量 由始点开始，逐一打印至当前贮油点的距离和贮油量 for i := 0 to K do Writeln(i, 1000 WayK i:30, OilK i:80); end. 图 22 倒推到第 n 步
11、 5 二、顺推法 顺推法是从边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出 再后项值 , ，依次类推，直至从问题初始陈述向前推进到这个问题的解为止。 看看下面的问题。 例 22 昆虫繁殖 科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x 个月产 y 对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫， 且卵长成成虫后的第一个月不产卵( 过 X 个月产卵 ) ，问过Z 个月以后，共有成虫多少对？ x=1,y=1,z=x 输入： x,y,z的数值 输出：成虫对数 事例： 输入： x=1 y=2 z=8 输出： 37 分析：首先我们
12、来看样例：每隔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 , 设数组 Ai表示第 I 月新增的成虫个数。 由于新成虫每过x 个月产 y 对卵，则可对每个AI 作如下操作 : Ai+k*x+2:=Ai+k*x+2+Ai*y （ 1z+1 1 1 z i iAans 6 end; begin readln(x,y,z); a1:=1; 初始化 for i:=1 to z do add(i); 对每个 AI 进行递推 ans:=0
13、; for i:=1 to z+1 do ans:=ans+ai; 累加总和 writeln(ans); end. 例 23：实数数列（NOI94第 3 题） 一个实数数列共有N项，已知 ai=(ai-1-ai+1)/2+d ，(1IN) (N60) 键盘输入 N，d，a1，an，m ，输出 am。 输入数据均不需判错。 分析： 根据公式ai=(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
14、-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的变化规律。 ai=ai-2-2ai-1+2d a i=Pi-2a2+Qi-2d+Ri-2a1-2 （Pi-1a2+Qi-1d+Ri-1a1） +2d =(P i-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 ,
15、显然， 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+Qnd+Rna1 a2=(an-Qnd+Rna1)/Pn 然后根据公式递推求出am，问题解决。 但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在 实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过 30 时，求 出的 am就明显偏离正确值。显然，这种算法虽简单但不可靠。 为了减少误差，我们可设计如下算法： ai=Pia2+Qid+Ria1 =Pi-1a3+Q
16、i-1d+Ri-1a2 7 =Pi-2a4+Qi-2d+Ri-2a3 , =Pi-2+kak+Qi-2+kd+Ri-2+kak-1 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:
17、array 1 MaxN, 1 3 of Real; Fi,1：对应 Pi；Fi,2：对应 Qi；Fi,3：对应 Ri procedure Init; begin Write(N, M, D = ); Readln(N, M, D); 输入项数、输出项序号和常数 Write(A1, A , N, = ); Readln(A1, AN); 输入 a1和 an end; procedure Solve; 根据公式PiPi-2-2*Pi-1,QiQi-2-2*Qi-1,RiRi-2-2*Ri-1求 Pi、Qi、Ri begin F1, 1 := 0; F1, 2 := 0; F1, 3:= 1; F
18、2, 1 := 1; F2, 2 := 0; F2, 3 := 0; for i := 3 to N do begin Fi, 1 := Fi 2, 1 2 * Fi 1, 1; Fi, 2 := Fi 2, 2 2 * Fi 1, 2 + 2; Fi, 3 := Fi 2, 3 2 * Fi 1, 3; end; end; procedure Main; begin Solve; 递推 A2,Am 8 for i := 2 to M do Ai:=(AN FNi+2,2*DFNi+2,3*Ai1)/FNi+2,1; Writeln(a, m, = , AM:20 :10); end; begin Init; Main; end.