第三章递推算法

1、第三章第三章 递推算法递推算法递推法是一种重要的数学方法，在数学的各个领域中都递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推

2、还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。来，可以将递推算法看成是一种特殊的迭代算法。【

3、例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。1、 一步可沿左斜线向下或右斜线向下走；2、 三角形行数小于等于100；3、 三角形中的数字为0，1，99；测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：573 88 1 02 7 4 44 5 2 6 5【算法分析】此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第I层向第I+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设a

4、i,j存放从i,j 出发到达n层的最大值，则ai,j=maxai,j+ai+1,j，ai,j+ai+1,j+1，a1,1 即为所求的数字总和的最大值。【参考程序】【参考程序】program ex3_1;var n,j,i:integer;a:array1.100,1.100 of integer;beginread(n);for i:=1 to n dofor j:=1 to i doread(ai,j); /输入数字三角形的值for i:=n-1 downto 1 dofor j:=1 to i dobeginif ai+1,j=ai+1,j+1 then ai,j:= ai,j+ai+1,

5、j /路径选择else ai,j:=ai,j+ai+1,j+1;end; writeln(a1,1);end.【例【例2】 有有 2n的一个长方形方格，用一个1*2的骨牌铺满方格。的骨牌铺满方格。编写一个程序，试对给出的任意一个 n(n0), 输出铺法总数。输出铺法总数。【算法分析】【算法分析】（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。（2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为X2=2；（4）当N=3时：骨牌

6、可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3. 由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。（5）推出一般规律：对一般的n，要求Xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为Xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为Xn-2。从第一骨牌排列方法考虑，只有这两种可能，所

7、以有：Xn=Xn-1+Xn-2 （n2）x1=1 x2=2 Xn=Xn-1+Xn-2就是问题求解的递推公式。任给n都可以从中获得解答。例如n=5，X3=X2+X1=3 X4=X3+X2=5 X5=X4+X3=8 下面是输入下面是输入n，输出X1Xn的的Pascal程序：程序：program ex3_2;vara:array1.100 of longint;a:array1.100 of longint;i,n:integer;beginwrite(Input n: ); read(n); /输入骨牌数输入骨牌数a1:=1; a2:=2;a1:=1; a2:=2;writeln(x1=,a1);

8、writeln(x1=,a1);writeln(x2=,a2);writeln(x2=,a2);for i:=3 to n do / 递推过程beginai:=ai-1+ai-2;writeln(x,i,=,ai);end;end.下面是运行程序输入下面是运行程序输入 n=30，输出的结果：，输出的结果：input n: 30 x1=1 x1=1 x2=2 x2=2 x3=3 . x29=832040 x30=1346269问题的结果就是有名的斐波那契数。问题的结果就是有名的斐波那契数。【例【例3】棋盘格数】棋盘格数设有一个N*M方格的棋盘（ l N100，1M100）。求出该棋盘中包含有多少

9、个正方形、多少个长方形（不包括正方形）。例如：当 N=2， M3时：正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长方形有2个：3*2的长方形有1个：程序要求：输入：N，M输出：正方形的个数与长方形的个数如上例：输入：2 3输出：8 10【算法分析】【算法分析】1.计算正方形的个数s1边长为1的正方形个数为n*m边长为2的正方形个数为(n-1)*(m-1)边长为3的正方形个数为(n-2)*(m-2)边长为minn，m的正方形个数为(m-minn，m+1)*(n-minn，m+1)根据加法原理得出

10、s1= ?1,min0)(*)(nmiimin2.长方形和正方形的个数之和s宽为1的长方形和正方形有m个，宽为2的长方形和正方形有m-1个，宽为m的长方形和正方形有1个；长为1的长方形和正方形有n个，长为2的长方形和正方形有n-1个，长为n的长方形和正方形有1个；根据乘法原理s=(1+2+n)*( 1+2+m)= 4*)1 (*)1 (mnmn?3.长宽不等的长方形个数s2显然，s2=s-s1= -4*)1 (*)1 (mnmn?1,min0)(*)(nmiimin由此得出算法：program ex7_3;var m,n,m1,n1,s1,s2:longint;beginreadln(m,n)

11、; m1:=m;n1:=n;s1:=m1*n1; /计算正方形的个数s1while (m10)and(n10)dobeginm1:=m1-1;n1:=n1-1;s1:=s1+m1*n1;end;s2:=(m+1)*(n+1)*m*n) div 4-s1; / 计算长方形的个数s2writeln(s1, ,s2);end.【例【例4】贮油点】贮油点一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以

12、消耗最少汽油的代价通过沙漠？（结果保留小数点后两位）编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：No. Distance(k.m.) Oil(litre) 1 2 【算法分析】【算法分析】设WayI第I个贮油点到终点（I=0）的距离；oilI第I个贮油点的贮油量；我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点。图19倒推过程 从贮油点I向贮油点I+1倒推的方法是：卡车在贮油点I和贮油点I+1间往返若干次。卡车每次返回I+1点时应该正好耗尽500公升汽油，而每次从I+1点出发时又必须装足500公升

13、汽油。两点之间的距离必须满足在耗油最少的条件下，使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 +

14、500/3。此时的状况如图20所示。图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所示。 图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趟返程空间，合计2

15、k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1)，Wayk+1=Wayk+dk,k+1=Wayk+500/(2k-1)；此时的状况如图22所示。图22倒推到第n步最后，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 ex7_4;var K: Integer;/

16、贮油点位置序号D, D1: Real; /累计终点至当前贮油点的距离Oil, Way: array 1 . 10 of Real; i: Integer; beginWriteln(No., Distance:30, Oil:80);K := 1; D := 500; Way1 := 500; Oil1 := 500; /从I=1处开始向终点倒推repeatK := K + 1;D := D + 500 / (2 * K 1);WayK := D;OilK := OilK 1 + 500;until D = 1000;WayK := 1000;/置始点到终点的距离值D1 := 1000 Way

17、K 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.【上机练习】【上机练习】1、走楼梯楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？【输入样例】Stairs.in3【输出样例】Stairs.out32、兔子繁殖有一种兔子，出生后一个月就可以长大，然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育一

18、对。现在，我们有一对刚出生的这种兔子，那么，n个月过后，我们会有多少对兔子呢？假设所有的兔子都不会死亡。【输入格式】输入文件仅一行，包含一个自然数n。【输出格式】输出文件仅一行，包含一个自然数，即n个月后兔子的对数。【输入样例】Rabbit.in5【输出样例】Rabbit.out53、平面分割同一平面内有n（n500）条直线，已知其中p（p2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？【输入格式】两个整数n（n500）和p（2pn）。【输出格式】一个正整数，代表最多分割成的区域数目。【输入样例】Surface.in12 5【输出样例】Surface.out734、骨牌

19、铺法有1n的一个长方形，用一个11、12和13的骨牌铺满方格。例如当n=3时为13的方格。此时用11、12和13的骨牌铺满方格，共有四种铺法。如下图：【输入样例】Domino.in3【输出样例】Domino.out45、蜜蜂路线、蜜蜂路线(bee.pas)【问题描述】【问题描述】一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房M开始爬到蜂房N，MN，有多少种爬行路线？【输入格式】【输入格式】输入M，N的值。【输出格式】【输出格式】爬行有多少种路线。【输入样例】【输入样例】bee.in1 14【输出样例】【输出样例】bee.out3776、数

20、塔问题、数塔问题(tower.pas)【问题描述】设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。【输入格式】第一行为n(n10)，表示数塔的层数从第2行至n+1行，每行有若干个数据，表示数塔中的数值。【输出格式】输出路径和最大的路径值。【输入样例】tower.in51311 812 7 266 14 15 812 7 13 24 11【输出样例】tower.out867、贮油点、贮油点【问题描述】一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力

21、为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？（结果保留小数点后两位）编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：No. Distance(k.m.) Oil(litre) 1 2 【输出样例】No. Distance oil0 0.0000000000 3881.36308140001 22.4331224330 3500.00000000002 60.8946608950 3000.0000000

22、0003 106.3492063500 2500.00000000004 161.9047619000 2000.00000000005 233.3333333300 1500.00000000006 333.3333333300 1000.00000000007 500.0000000000 500.00000000008 1000.0000000000 0.00000000008、过河卒（NOIP2002）(knight.pas)【问题描述】【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如图2_1中的C点和P1，P2，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，CA且CB。现在输入B点坐标和C点的坐标，要你计算出卒从A点能够到达B点的路径的条数。【输入样例】knight.in4 8 2 4【输出样例】【