2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 递推法二.doc

2019-2020 年高中信息技术 全国青少年奥林匹克联赛教案 递推法二 课题：递推法 目标： 知识目标：递推概念与利用递推解决实际问题 能力目标：递推方程 重点：递推方程 难点：递推方程写出 板书示意： 1） 递推的理解（例 20） 2） 倒推法（例 21） 3） 顺推法（例 22、例 23） 授课过程： 递推就是逐步推导的过程。我们先看一个简单的问题。 例 20：一个数列的第 0 项为 0，第 1 项为 1，以后每一项都是前两项的和，这个数列 就是著名的裴波那契数列，求裴波那契数列的第 N 项。 分析：我们可以根据裴波那契数列的定义：从第 2 项开始，逐项推算，直到第 N 项。 因此可以设计出如下算法： F0 := 1; F1 := 2; FOR I := 2 TO N DO FI := FI 1 + FI 2; 从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这 样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关 系式：F n=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件 （或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值） 。很多问题就 是这样逐步求解的。 对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果） ， 问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算， 真正起到“物尽其用”的效果。 21nffn 递推分倒推法和顺推法两种形式。算法流程如下： 一、倒推法 所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标， 根据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法。因为 这类问题的运算过程是一一映射的，故可分析其递推公式。看看下面的例题。 例 21：贮油点 一辆重型卡车欲穿过 1000 公里的沙漠，卡车耗汽油为 1 升/公里，卡车总载油能力为 500 公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油 点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽 油，才能使卡车以消耗最少汽油的代价通过沙漠？ 编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格 式如下： 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 点出发时又必须装足 图 19 倒推过程 满足求解 Y顺推 初始条件 F1 N倒推 由题意（或递推关系）定初始值 F1（边界条件）求出顺推关系式 Fi=g(Fi-1)； 由题意（或递推关系）确定最终结果 Fn；求出倒推关系式 Fi-1=g(Fi)； I=1；由边界条件 F1出发进行顺推 I=n；从最终结果 Fn出发进行倒推 While 当前结果 Fi非最终结果 Fn do While 当前结果 Fi非初始值 F1 do 由 Fi=g(Fi-1)顺推后项； 由 Fi-1=g(Fi)倒推前项； 输出顺推结果 Fn和顺推过程； 输出倒推结果 F1和倒推过程； 500 公升汽油。两点之间的距离必须满足在耗油最少的条件下，使 I 点贮足 I*500 公升汽 油的要求（0In-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=500/3km，Way2=Way1+d 12=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+d23=Way2+500/5； 此时的状况如图 21 所示。 依次类推，为了在 I=k 处贮藏 k*500 公升汽油，卡车至少从 I=k+1 处开 k 趟满载车至 I=k 处，即 oilk+1=(k+1)*500=oilk+500，加上从 I=k 返回 I=k+1 的 k-1 趟返程空间， 合计 2k-1 次。这 2k-1 次总耗油量按最省要求为 500 公升，即 dk,k+1=500/(2k-1)， 图 20 倒推到第二步 图 21 倒推到第三步 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 趟的总耗油量应正好为（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 := 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 步 二、顺推法 顺推法是从边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推 出再后项值，依次类推，直至从问题初始陈述向前推进到这个问题的解为止。 看看下面的问题。 例 22 昆虫繁殖 科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 x 个月产 y 对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成 虫，且卵长成成虫后的第一个月不产卵(过 X 个月产卵)，问过 Z 个月以后，共有成虫多少 对？x=1,y=1,z=x 输入：x,y,z 的数值 输出：成虫对数 事例： 输入：x=1 y=2 z=8 输出：37 分析：首先我们来看样例：每隔 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 （1=k, I+k*x+2z+1 end; begin readln(x,y,z); a1:=1; 初始化 for i:=1 to z do add(i); 对每个 AI进行递推 ans:=0; 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，a 1，a n，m，输出 am。 输入数据均不需判错。 分析： 根据公式 ai=(ai-1-ai+1)/2+d 变形得，a i+1=ai-1-2ai+2d，因此该数列的通项公式为： ai=ai-2-2ai-1+2d，已知 a1，如果能求出 a2，这样就可以根据公式递推求出 am a i=ai-2-2ai-1+2d =ai-2-2（a i-3-2ai-2+2d）+2d =-2ai-3+5（a i-4-2ai-3+2d）-2d =5ai-4-12ai-3+8d 一直迭代下去，直到最后，可以建立 ai和 a1与 a2的关系式。 设 ai=Pia2+Qid+Ria1，我们来寻求 Pi,Qi,Ri的变化规律。 a i=ai-2-2ai-1+2d a i=Pi-2a2+Qi-2d+Ri-2a1-2（P i-1a2+Qi-1d+Ri-1a1）+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 P i=Pi-2-2Pi-1 Qi=Qi-2-2Qi-1+2 Ri=Ri-2-2Ri-1 显然，P 1=0 Q1=0 R1=1 （i=1） P2=1 Q2=0 R2=0 （i=2） 将初值 P1、Q 1、R 1和 P2、Q 2、R 2代入可以求出 Pn、Q n、R n a n=Pna2+Qnd+Rna1 a 2=(an-Qnd+Rna1)/Pn 然后根据公式递推求出 am，问题解决。 但仔细分析，上述算法有一个明显的缺陷：在求由于在求 a2要运用除法，因此会存在 实数误差，这个误差在以后递推求 am的过程又不断的扩大。在实际中，当 m 超过 30 时， 求出的 am就明显偏离正确值。显然，这种算法虽简单但不可靠。 为了减少误差，我们可设计如下算法： a i=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 a n=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1 ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 根据公式，可以顺推 a2、a 3、a M。虽然仍然存在实数误差，但由于 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, 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、Q i、R i begin F1, 1 := 0; F1, 2 := 0; F1, 3:= 1; F2, 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; 递推 A2Am for i := 2 to M do Ai:=(ANFNi+2,2*DFNi+2,3*Ai1)/FNi+2,1; Writeln(a, m, =, AM:20 :10); end; begin Init; Main; end.