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

递推法

课题：递推法

目标：

知识目标：递推概念与利用递推解决实际问题

能力目标：递推方程

重点：递推方程

难点：递推方程写出

板书示意：

1） 递推的理解（例20）

2） 倒推法（例21）

3） 顺推法（例22、例23）

授课过程：

递推就是逐步推导的过程。我们先看一个简单的问题。

例20：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就

是著名的裴波那契数列，求裴波那契数列的第N项。

1n0







f2n1

n







ffn2



n2n1



分析：我们可以根据裴波那契数列的定义：从第2项开始，逐项推算，直到第N项。因

此可以设计出如下算法：

F[0] := 1; F[1] := 2;

FOR I := 2 TO N DO

F[I] := F[I – 1] + F[I – 2];

从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，

相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：

F=g(F)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终

nn-1

结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步

求解的。

对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），

问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，

真正起到“物尽其用”的效果。

1

递推分倒推法和顺推法两种形式。算法流程如下：

初始条件F

1

满足求解

Y{顺推} N{倒推}

由题意（或递推关系）定初始值F

1

（边

由题意（或递推关系）确定最终结果

界条件）求出顺推关系式F

ii-1ni-1i

=g(F)； F；求出倒推关系式F=g’(F)；

I=1；{由边界条件F出发进行顺推} I=n；{从最终结果F出发进行倒推}

1n

While 当前结果F非最终结果F do While 当前结果F非初始值Fdo

ini1

由F

ii-1i-1i

=g(F)顺推后项； 由F=g(F)倒推前项；

输出顺推结果F

n1

和顺推过程； 输出倒推结果F和倒推过程；

一、倒推法

所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根

据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法。因为这类

问题的运算过程是一一映射的，故可分析其递推公式。看看下面的例题。

例21：贮油点

一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500

公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使

卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能

使卡车以消耗最少汽油的代价通过沙漠？

编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式

如下：

No. ) Oil(litre)

1 × × × ×

2 × × × ×

… … … … …

分析：

设Way[I]——第I个贮油点到终点（I=0）的距离；

oil[I]——第I个贮油点的贮油量；

我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及

存油量。图19表示倒推时的返回点。

图19倒推过程

从贮油点I向贮油点I+1倒推的方法是：卡车在贮油点I和贮油点I+1间往返若干次。

卡车每次返回I+1点时应该正好耗尽500公升汽油，而每次从I+1点出发时又必须装足500

2

公升汽油。两点之间的距离必须满足在耗油最少的条件下，使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处至少贮有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上从I=1返回至I=2

处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即

d=500/3km，Way[2]=Way[1]+d=Way[I]+500/3

1212

此时的状况如图20所示。

图21 倒推到第三步

为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所

以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程

空车，合计5次。路途耗油亦应500公升，即d=500/5，

23

Way[3]=Way[2]+d=Way[2]+500/5；

23

此时的状况如图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公升，即d=500/(2k-1)，

k,k+1

3

Way[k+1]=Way[k]+d=Way[k]+500/(2k-1)；

k,k+1

图22倒推到第n步

此时的状况如图22所示。

最后，I=n至始点的距离为1000-Way[n],oil[n]=500*n。为了在I=n处取得n*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 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] + 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);

4

end.

二、顺推法

顺推法是从边界条件出发，通过递推关系式推出后项值，再由后项值按递推关系式推出

再后项值……，依次类推，直至从问题初始陈述向前推进到这个问题的解为止。

看看下面的问题。

例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 …

新增卵 2 2 2 6 10 14 26 46 …

成虫 1 1 1 3 5 7 13 23 37 …

0

设数组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]有关，即可用递推求法。

则总共的成虫个数为：

z1

ansA[i]



i1

程序如下：

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

5

until j>z+1

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项，已知

a=(a-a)/2+d，(1

ii-1i+1

键盘输入N，d，a，a，m，输出a。

1nm

输入数据均不需判错。

分析：

根据公式a=(a-a)/2+d 变形得，a=a-2a+2d，因此该数列的通项公式为：

ii-1i+1i+1i-1i

a=a-2a+2d，已知a，如果能求出a，这样就可以根据公式递推求出a

ii-2i-112m

∵ a=a-2a+2d ……①

ii-2i-1

=a-2（a-2a+2d）+2d

i-2i-3i-2

=-2a+5（a-2a+2d）-2d

i-3i-4i-3

=5a-12a+8d

i-4i-3

……

一直迭代下去，直到最后，可以建立a和a与a的关系式。

i12

设a=Pa+Qd+Ra，我们来寻求P,Q,R的变化规律。

ii2ii1iii

∵ a=a-2a+2d

ii-2i-1

∴ a=Pa+Qd+Ra-2（Pa+Qd+Ra）+2d

ii-22i-2i-21i-12i-1i-11

=(P-2P)a+(Q-2Q+2)d+(R-2R)a

i-2i-12i-2i-1i-2i-11

∴ P=P-2P……②

ii-2i-1

Q=Q-2Q+2……③

ii-2i-1

R=R-2R……④

ii-2i-1

显然，P=0 Q=0 R=1 （i=1）

111

P=1 Q=0 R=0 （i=2）

222

将初值P、Q、R和P、Q、R代入②③④可以求出P、Q、R

111222nnn

∵ a=Pa+Qd+Ra

nn2nn1

∴ a=(a-Qd+Ra)/P

2nnn1n

然后根据公式①递推求出a，问题解决。

m

但仔细分析，上述算法有一个明显的缺陷：在求由于在求a要运用除法，因此会存在

2

实数误差，这个误差在以后递推求a的过程又不断的扩大。在实际中，当m超过30时，求

m

出的a就明显偏离正确值。显然，这种算法虽简单但不可靠。

m

为了减少误差，我们可设计如下算法：

∵ a=Pa+Qd+Ra

ii2ii1

6

=Pa+Qd+Ra

i-13i-1i-12

i-24i-2i-23

=Pa+Qd+Ra

……

=Pa+Qd+Ra

i-2+kki-2+ki-2+kk-1

∴ a=Pa+Qd+Ra

nn-k+2kn-k+2n-k+2k-1

a=(a-Qd+Ra)/P……⑤

knn-k+2n-k+2k-1n-k+2

根据公式⑤，可以顺推a、a、…、a。虽然仍然存在实数误差，但由于P递减，因

23Mn-k+2

此最后得出的a要比直接利用公式①精确得多。

m

程序如下：

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;

{F[i,1]：对应P；F[i,2]：对应Q；F[i,3]：对应R}

iii

procedure Init;

begin

Write(‘N, M, D =’);

Readln(N, M, D); {输入项数、输出项序号和常数}

Write(‘A1, A’, N, ‘ =’);

Readln(A[1], A[N]); {输入a和a}

1n

end;

procedure Solve;

{根据公式PP-2*P,QQ-2*Q,RR-2*R求P、Q、R }

ii-2i-1ii-2i-1ii-2i-1iii

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;

7

{递推A…A}

2m

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.

8