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

1递推法递推法课题：递推法目标：知识目标：递推概念与利用递推解决实际问题能力目标：递推方程重点：递推方程难点：递推方程写出板书示意：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;从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值） 很多问题就是这样逐步求解的对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果） ，问题就可以递推了，接下来便是让计算机一步步了。

让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果2120121nffnnfnnn2递推分倒推法和顺推法两种形式算法流程如下：一、倒推法所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法因为这类问题的运算过程是一一映射的，故可分析其递推公式看看下面的例题例 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顺推 初始条件 F1N倒推由题意（或递推关系）定初始值F1（边界条件）求出顺推关系式Fi=g(Fi-1)；由题意（或递推关系）确定最终结果Fn；求出倒推关系式 Fi-1=g(Fi)；I=1；由边界条件 F1出发进行顺推I=n；从最终结果 Fn出发进行倒推While 当前结果 Fi非最终结果 Fn doWhile 当前结果 Fi非初始值 F1 do由 Fi=g(Fi-1)顺推后项；由 Fi-1=g(Fi)倒推前项；输出顺推结果 Fn和顺推过程；输出倒推结果 F1和倒推过程；3500 公升汽油两点之间的距离必须满足在耗油最少的条件下，使 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+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+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 倒推到第三步4Wayk+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 步5二、顺推法顺推法是从边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出再后项值，依次类推，直至从问题初始陈述向前推进到这个问题的解为止。

看看下面的问题例 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 月）的成虫个数月份123456789新增卵0222610142646成虫111357132337设数组 Ai表示第 I 月新增的成虫个数由于新成虫每过 x 个月产 y 对卵，则可对每个 AI作如下操作:Ai+k*x+2:=Ai+k*x+2+Ai*y （1=k, I+k*x+2z+111ziiAans6 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，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-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 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+Qnd+Rna1 a2=(an-Qnd+Rna1)/Pn然后根据公式递推求出 am，问题解决。

但仔细分析，上述算法有一个明显的缺陷：在求由于在求 a2要运用除法，因此会存在实数误差，这个误差在以后递推求 am的过程又不断的扩大在实际中，当 m 超过 30 时，求出的 am就明显偏离正确值显然，这种算法虽简单但不可靠为了减少误差，我们可设计如下算法： ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a27 =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-1ak=(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, 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; 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; 递推 A2Am8 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.。