递推递归算法 pascal

1、 递推和递归算法递推和递归算法 递推递推是迭代算法中最基本的表现形式，是迭代算法中最基本的表现形式，是一是一种不断用变量的旧值递推出新值的解决问题的种不断用变量的旧值递推出新值的解决问题的方法，方法，常见的的递推方式是从小规模问题推解常见的的递推方式是从小规模问题推解出大规模问题。出大规模问题。 问题求解的基本步骤1.确定迭代模型n 分析前一个（或几个）值与下一个值迭代关系的数学模型。2.建立迭代关系式n 将迭代模型转换为“循环不变式”-迭代关系式。3.控制迭代过程n 确定迭代过程的结束条件。（1）迭代次数确定 （2）迭代次数不确定基本步骤基本步骤递归算法递归算法是把问题转化为规模缩小了的同类

2、问是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来题的子问题。然后递归调用函数（或过程）来表示问题的解。表示问题的解。 一般来说，递归需要有边界条件、递归前进一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。归前进；当边界条件满足时，递归返回。 注意：注意： (1) (1) 递归就是在过程或函数里调用自身递归就是在过程或函数里调用自身; ;(2) (2) 在使用递增归策略时，必须有一个明确的递归结在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进

3、行下去（束条件，称为递归出口，否则将无限进行下去（死死锁锁）。）。 【例【例1 1】 快速练习：简单骨牌铺方格问题快速练习：简单骨牌铺方格问题【问题描述】：在2n的一个长方形方格中，用n个1 2的骨牌铺满方格，输入n (n0)，要求编程计算铺满方格的方案总数。例如n=3时，为2 3方格，骨牌的铺放方案有三种，如下图：v上述问题，如果思考方法不恰当，求解相当困难，我们可以上述问题，如果思考方法不恰当，求解相当困难，我们可以用递推迭代的方法归纳出问题解的一般规律。用递推迭代的方法归纳出问题解的一般规律。v当当n=1时，只能是一种铺法，表示为时，只能是一种铺法，表示为X1=1;算法分析算法分析v当当

4、n=2时，骨牌可以两个并列竖排，也可以两个并列横排，时，骨牌可以两个并列竖排，也可以两个并列横排，铺法总数表示为铺法总数表示为X2=2;算法分析算法分析v当当n=3时，可以分两种情况考虑：时，可以分两种情况考虑：先竖排放置先竖排放置 和和 先横排放置先横排放置；（1）若先竖排放置，剩下未铺满的区域为）若先竖排放置，剩下未铺满的区域为22的方格，有的方格，有X2=2种铺法。种铺法。算法分析算法分析n=2 的区域有X2种铺法即n=3时，若先竖排，则铺满整个方格有X2种铺法！v当当n=3时，可以分两种情况考虑：时，可以分两种情况考虑：先竖排放置先竖排放置 和和 先横排放置先横排放置；（2）若先横排放

5、置，下方的方格也必须横排，则剩下未铺满的区）若先横排放置，下方的方格也必须横排，则剩下未铺满的区域为域为21的方格，有的方格，有X1=1种铺法种铺法 。算法分析算法分析n=1 的区域有X1种铺法即n=3时，若先横排，则铺满整个方格有X1种铺法！算法描述算法描述 print(“Please Input N”);input(n);a1=1;a2=2;for i:=3 to n doai=ai-1+ai-2;print(an);骨牌铺方格升级版骨牌铺方格升级版【问题描述】：在1n的一个长方形方格中，用若干个11、 12、 13的骨牌铺满方格，输入n (n0)，要求编程计算铺满方格的方案总数。v输入样

6、例输入样例v36v输出样例输出样例v2082876103var f:array0.1000of longint; i,n:longint;procedure setio;beginassign(input,domino.in);assign(output,domino.out);reset(input);rewrite(output);end;procedure print;beginclose(input);close(output);end;begin setio; readln(n); f0:=1; f1:=1; f2:=2; for i:=3 to n do fi:=fi-1+fi-2

7、+fi-3; writeln(fn); print;end.【例【例2 2】快速练习】快速练习-马拦过河卒马拦过河卒棋盘上棋盘上A A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B B点。卒行走的规则：点。卒行走的规则：可以向下、或者向右。同时在棋盘上可以向下、或者向右。同时在棋盘上C C点有一个对方的马，该点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为因此称之为“马拦过河卒马拦过河卒”。棋盘用坐标表示，棋盘用坐标表示，A A点点(0, 0)(0, 0)、B B点点(n, m)(n, m(n,

8、m)(n, m为不超过为不超过2020的整数的整数) )，同样马的位置坐标是需要给出的。，同样马的位置坐标是需要给出的。C C!=!=A,CA,C!=!=B B ，假设马的位置是固定不动的，并不是卒走一步马走一步，现假设马的位置是固定不动的，并不是卒走一步马走一步，现在要求你计算出卒从在要求你计算出卒从A A点能够到达点能够到达B B点的路径的条数。点的路径的条数。输入：一行四个数据，分别表示输入：一行四个数据，分别表示B B点坐标和马的坐标。点坐标和马的坐标。输出：一个数据，表示从起点输出：一个数据，表示从起点(0,0)(0,0)到达到达B B点的所有路点的所有路 径的数目。径的数目。【样例

9、输入】【样例输入】 6 6 3 3【样例输出】【样例输出】 6【样例输入】【样例输入】 14 16 7 5【样例输出】【样例输出】 39217645v马的位置在马的位置在C(i,j)C(i,j)点，根据点，根据C C点可以计算出控制点的坐标点可以计算出控制点的坐标; ;v控制点共八个方向，实际计算应考虑是否越界。控制点共八个方向，实际计算应考虑是否越界。算法分析算法分析12 34B(4,8)P1(i+2,j+1)P2(i+1,j+2)C(i,j)P3(i-1,j+2)P4(i-2,j+1) 1 2 3 4 5 6 7 8 P5(i-2,j-1)P6(i-1,j-2)P7(i+1,j-2)P8(

10、i+2,j-1)A(0,0)v卒要到达棋盘上的一个点，只能来自卒要到达棋盘上的一个点，只能来自上点上点或者或者左点左点; ;v到达点到达点(4,8)(4,8)的路径数目：的路径数目：f48 = f38 + f47f48 = f38 + f47算法分析算法分析12 34B(4,8) 1 2 3 4 5 6 7 8 A(0,0)v根据上面的演示可以看出，卒不能经过马的控制点，可以用根据上面的演示可以看出，卒不能经过马的控制点，可以用数组数组gij表示点（表示点（i,j）是不是控制点，）是不是控制点，gij=0表示无障碍，表示无障碍， gij=1表示有障碍；表示有障碍；v卒要到达棋盘上的一个点，只能

11、来自卒要到达棋盘上的一个点，只能来自左点左点或者或者上点上点，根据加，根据加法原理，法原理，到达一个点的路径数目等于到达其相邻点的上点和到达一个点的路径数目等于到达其相邻点的上点和左点的路径数目之和左点的路径数目之和，因此可以通过逐行（或逐列）递推迭，因此可以通过逐行（或逐列）递推迭代的方法求出从起点到终点的路径数目。代的方法求出从起点到终点的路径数目。算法分析算法分析v递推关系式递推关系式 fij = fi-1j + fij-1算法分析算法分析递推关系成立的条件是什么？递推关系成立的条件是什么？i 0 and j0 and gi,j=0递推边界？递推边界？f00=1fij=0 / gij=1

12、fi0=fi-10 / i0 and gi0=0 上点f0j=f0j-1 / j0 and g0j=0 左点program Q1; var map:array0.20,0.20 of boolean; f:array0.20,0.20 of int64; n,m,x,y,i,j:longint;begin readln(m,n,y,x); fillchar(map,sizeof(map),true); mapx,y:=false; mapx+1,y+2:=false; mapx+2,y+1:=false; mapx-1,y-2:=false; mapx-2,y-1:=false; mapx+1

13、,y-2:=false; mapx+2,y-1:=false; mapx-1,y+2:=false; mapx-2,y+1:=false; f0,0:=1; for i:=1 to n do begin if not mapi,0 then break; fi,0:=1; end; for i:=1 to m do begin if not map0,i then break; f0,i:=1; end; for i:=1 to n do for j:=1 to m do if mapi,j then begin if mapi-1,j then fi,j:=fi,j+fi-1,j; if m

14、api,j-1 then fi,j:=fi,j+fi,j-1; end; writeln(fn,m);gram Q1; const dx:array1.8 of integer=(-2,-1,1,2,2,1,-1,-2); dy:array1.8 of integer=(1,2,2,1,-1,-2,-2,-1);var n,m,x,y,i,j: byte; g:array0.20,0.20 of 0.1; c:longint;procedure sol(x,y:integer);var i:integer;begin if (x=n) and (y=m) then c:=c+1

15、else begin if (ym) and (gx,y+1=0) then sol(x,y+1); if (x=0) and (x+dxi=0) and (y+dyi=m) then gx+dxi,y+dyi:=1; sol(0,0); writeln(c);end. 【例【例3 3】 ：m,nm,n为整数，且满足下列两个条件：为整数，且满足下列两个条件：m,n1,2m,n1,2，,k,k,即即1m,nk1m,nk； (n(n2 2-m-m* *n-mn-m2 2) )2 2=1=1。 编程输入正整数编程输入正整数k(1k10k(1k109 9), ),求一组满足上述两个求一组满足上述两个条

16、件的条件的m,nm,n，并且使，并且使mm2 2+n+n2 2的值最大。的值最大。 n输入：输入：Ex.inn1n输出：输出：Ex.ansnm=1 n=1n输入：输入：Ex.inn1995n输出：输出：Ex.ansnm=987 n=1597n输入：输入：Ex.inn1000000000n输出：输出：Ex.ansnm=433494437 n=701408733n首先，通过手工测试，我们得出了以下一首先，通过手工测试，我们得出了以下一些小的数据结果：些小的数据结果：nk2348163264nn 2338132155nm 122581334n令人惊奇的是：令人惊奇的是：n，m随着随着k的增长以斐波拉

17、的增长以斐波拉契数列形式增长！契数列形式增长！n问题的解就是小于等于问题的解就是小于等于k的最大的相临两个的最大的相临两个斐波拉契数斐波拉契数!program Exam3; var m,n,next,k :longint; begin readln(k); 读入数值读入数值kif (k1000000000) then halt; 如果如果k不在要求范围内，就终止不在要求范围内，就终止m:=1; n:=1; next:=m+n; 确定斐波拉契数列的头确定斐波拉契数列的头三项三项while next=k do 顺推，求出顺推，求出m,n的最大值的最大值 begin m:=n; n:=next; n

18、ext:=m+n; end; writeln(m=,m, n=,n); end.【例【例4 4】任何一个正整数都可以用任何一个正整数都可以用2 2的幂次方表示。的幂次方表示。 例如例如:137=27+23+20 :137=27+23+20 同时约定次方用括号来表示同时约定次方用括号来表示, ,即即abab可表示为可表示为a(b)a(b)。 由此可知由此可知,137,137可表示为可表示为 : 2(7)+2(3)+2(0) : 2(7)+2(3)+2(0) 进一进一步步:7=22+2+20 (21:7=22+2+20 (21用用2 2表示表示) 3=2+20 ) 3=2+20 所以最后所以最后1

19、37137可表示为可表示为:2(2(2)+2+2(0)+2(2+2(0)+2(0) :2(2(2)+2+2(0)+2(2+2(0)+2(0) 输入输入: :正整数正整数(n=20000) (n=20000) 输出输出: :符合约定的符合约定的n n的的0,20,2表示表示( (在表示中不能有空格在表示中不能有空格) )n输入：输入：Ex.inn73n输出：输出：Ex.ansn2(2(2)+2)+2(2+2(0)+2(0)n输入：输入：Ex.inn1384n输出：输出：Ex.ansn2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2)+2(2(2)+2(0)+2(2+2(0)Var n:longint;procedure find(n:longint);var i,j,k:longint;begin k:=trunc(ln(n)/ln(2); j:=1; for i:=1 to k do j:=j*2; n:=n-j; if j2 t