nbhkdz.com冰点文库

第十讲 递归与递推式


第十讲 递归与递推式

递归的概念:

一个过程(或函数)直接或间接调 用自己本身,这种过程(或函数)叫 递归过程(或函数).

例:计算n!
可用递归公式如下: Fac(1)=1 fac(n)=n*fac(n-1)

当 n=1 时 当n>1时

var n:

integer; function fac(i:integer):integer; begin if i=1 then fac:=1 else fac:=i*fac(i-1); end; begin readln(n); writeln(fac(n)); end.

递归的关键:
1.确定递归公式(关系) 2.确定边界(终了)条件

一、阅读程序,写出结果 1、 function f(m:integer):integer; var va:integer; begin if m=0 then va:=3 else va:=f(m-1)+5; f:=va; end. Begin writeln(f(3)); End.

2、 var n:integer; procedure f(n:integer); begin if n<>0 then begin f(n-1); write(n); f(n-1); end; end; begin f(3); end.

3、已知ack(m,n)函数的计算公式如下:

?n ? 1 ack(m,n)= ?ack( m ? 1,1) ? ?ack(m ? 1, ack(m, n ? 1)) ?

M=0 N=0 M<>0 n<>0

编程实现,并手工求出ack(1,2)和ack(2,2)的值。

ack(1,3)、 ack(2,4)、 ack(3,3)、 ack(3,4)

Ack(1,2)=4 ack(2,2)=7

var m,n:integer; function ack(m,n:integer):integer; begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1) else ack:=ack(m-1,ack(m,n-1)); end; begin read(m,n); writeln(ack(m,n)); end.

二、递推式的应用:
1、楼梯有N阶,上楼可以一步上一价,也可以一次上二阶,还可以一 步上三阶。编一个程序,计算共有多少种不同的走法。

var n:integer; function f(n:integer):integer; begin if n=1 then f:=1 else if n=2 then f:=2 else if n=3 then f:=4 else f:=f(n-3)+f(n-2)+f(n-1); end; begin read(n); writeln(f(n)); end.

2、在一个平面上有一个圆和n条直线,这些直线中每一 条在圆内同其他直线相交,假设没有3条直线相交于一 点,试问这些直线将圆分成多少区域。 var n:integer; function f(n:integer):integer; begin if n=0 then f:=1 else f:=f(n-1)+n; end; begin read(n); writeln(f(n)); end.

3、问题描述 将整数n分成k份,且每份不能为空,任意两种分法不能 相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。
样例 输入: 7 3 输出:4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

分析:用f(I,j)表示将整数I分成j分的分法,可以划分为两类: 第一类 :j分中不包含1的分法,为保证每份都>=2,可以先 那出j个1分到每一份,然后再把剩下的I-j分成j份即可,分法 有:f(I-j,j). 第二类 : j份中至少有一份为1的分法,可以先那出一个1作 为单独的1份,剩下的I-1再分成j-1份即可,分法有:f(I-1,j-1).

所以:f(I,j)= f(I-j,j)+ f(I-1,j-1)

const maxn=200; maxk=6;

var
n,k,i,j:longint; f:array[0..maxn,0..maxk] of longint; begin readln(n,k); f[0,0]:=1; for i:=1 to n do for j:=1 to k do if(i>=j) then writeln(f[n,k]); end.

f[i,j]:=f[i-j,j]+f[i-1,j-1];

4、n个有区别的球放到m个相同的盒子中,要求无一空盒,求不同的方 案数S(n,m)表示

解:设有n个不同的球,分别用b1,b2,……bn表示。从中取出一 个球bn,bn的放法有以下两种: 1)bn独自占一个盒子;那么剩下的球只能放在m-1个盒子中,方 案数为S(n-1,m-1); 2)bn与别的球共占一个盒子;那么可以事先将b1,b2,……bn-1这 n-1个球放入m个盒子中,然后再将球bn可以放入其中一个盒 子中,方案数为mS(n-1,m)。 综合以上两种情况: S(n,m)=mS(n-1,m)+S(n-1,m-1) (n>1,m1) 边界条件可以由定义2推导出: S2(n,1)=1;S2(n,n)=1;S2(n,k)=0(k>n)。

var n,k:integer; function s(n,k:integer):integer; begin if r(n<k) then s:=0 else if (k=1)or(n=k) then s:=1 else s:=s(n-1,k-1)+k*s(n-1,k); end; begin read(n,k); write(s(n,k)); end.

var s:array[1..100,1..100] of longint; n,m,i,j:integer; begin read(n,m); fillchar(s,sizeof(s),0); for i:=1 to n do s[i,1]:=1; for i:=1 to m do s[i,i]:=1; for i:=2 to m do for j:=i to n do s[j,i]:=i*s[j-1,i]+s[j-1,i-1]; writeln(s[n,m]); end.

5、设f(n,k)是从集合{1,2,。。。,n}中能够选择的没有两个连续整 数的k个元素子集的数目,求递归式f(n,k)。

【问题分析】: N有两种情况: ① 当n在子集时,则n-1一定不在子集中,即在{1,2,。。。,n2}中选k-1个元素,数目为f(n-2,k-1)。 ② 当n不在子集中时,则在{1,2,。。。,n-1}中选k个元素,数 目为f(n-1,k)。 所以:f(n,k)= f(n-2,k-1) +f(n-1,k) 边界条件:F(n,1)=n, f(n,k)=0 ( n<=k)

var n,k:integer; function f(n,k:integer):integer; begin if k=1 then f:=n else if n<=k then f:=0 else f:=f(n-2,k-1)+f(n-1,k); end; begin read(n,k); writeln(f(n,k)); end.

var f:array[1..100,1..100] of int64; i,j,n,k:integer; begin fillchar(f,sizeof(f),0); readln(n,k); for i:=1 to n do f[i,1]:=i; for i:=2 to k do for j:=i+1 to n do f[j,i]:=f[j-2,i-1]+f[j-1,i]; writeln(f[n,k]); end.

6、设有一个N*M(l<= N<=50, l<= M<= 50)的街道(如图 一):(40%) 北
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * B

A 图一 规定行人从A(1,1)出发,在街道上只能向东或北方向行走。 图二为N=3,M=3的街道图: 若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的的街道)不 让行人通 行,如图一中用“*”表示的部分。 此矩形障碍区域用2对顶点坐 标给出,图一中的2对顶点坐标为:(2,2),(8,4),此时从 A出发到达B的路径仅有 两条。 程序要求 任务一:给出N,M后,求出所有从A出发到达B的路径的条数。 任务二:给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标 (X1,y1), (X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。

1、 const k=50; var f:array[1..k,1..k] of extended; i,j,m,n:integer; begin read(n,m); for i:=1 to n do f[1,i]:=1; for i:=1 to m do f[i,1]:=1; for i:=2 to m do for j:=2 to n do f[i,j]:=f[i-1,j]+f[i,j-1]; writeln(f[m,n]:0:0); end.

2、 const k=50; var f:array[1..k,1..k] of extended; i,j,m,n,x1,y1,x2,y2:integer; begin read(n,m); read(x1,y1); read(x2,y2); for i:=1 to n do f[1,i]:=1; for i:=1 to m do f[i,1]:=1; for i:=2 to m do for j:=2 to n do if (i<=x2)and(i>=x1)and(j>=y1)and(j<=y2) then f[i,j]:=0 else f[i,j]:=f[i-1,j]+f[i,j-1]; writeln(f[m,n]:0:0); end.

7、过河卒(存盘名:NOIP2002C4) [问题描述]: 如图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以向下、或 者向右。同时在棋盘上的任一点有一个对方的马(如上图的C点),该马所在的点 和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点(图中的P1,P2 … P8 和 C)。卒不能通过对方马的控制点。

棋盘用坐标表示,A 点(0,0)、B 点(n,m)(n,m 为不超过 20 的整数, 并由键盘输入),同样马的位置坐标是需要给出的(约定: C<>A,同时 C<>B)。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 [输入]: 键盘输入 B点的坐标(n,m)以及对方马的坐标(X,Y){不用盘错} [输出]: 屏幕输出 一个整数(路径的条数)。 [输入输出样例]: 输入: 6632 输出: 17

program P2002_4; var a:array[-2..22,-2..22] of 0..1; s:array[-1..20,-1..20] of EXTENDED; temp,g,i,j,n,m,x0,y0,t:integer; begin{main} readln(n,m,x0,y0); a[x0,y0]:=1;a[x0-2,y0+1]:=1;a[x0-1,y0+2]:=1; a[x0+1,y0+2]:=1;a[x0+2,y0+1]:=1;a[x0+2,y0-1]:=1; a[x0+1,y0-2]:=1;a[x0-1,y0-2]:=1;a[x0-2,y0-1]:=1; a[0,0]:=1;s[0,0]:=1; for i:=0 to n do for j:=0 to m do if a[i,j]<1 then s[i,j]:=s[i-1,j]+s[i,j-1]; writeln(s[n,m]:0:0); end.
输入 8 6 0 4 10 10 4 4 20 20 4 0 19 19 1 0 14 16 7 5 输出 1617 6802 56477364570 2203961430 39217645 }


递推与递归算法

. 本程序的递推运算可用如下图示描述: 递推算法以初始{起点}值为基础,用相同...4 递推与递归 39页 免费 第十讲 递归与递推式 26页 免费 递推与递归应用...

递推递归

递归与递推 8页 1财富值 递推与递归应用 16页 免费 递归与递推深入 81页 8财富值 递推和递归 4页 免费 第十讲 递归与递推式 26页 免费 (2)递归与递...

递归与递推上机习题

第4讲 递归专题讲座 33页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 递归与递推上机习题 递归与递推上机...

第3章 模拟训练(计算思维)

A.“递归”源自于数学上的递推式和数学归纳法 B.“递归与递推式一样,都是自递推基础计算起,由前项(第 n-1 项)计算后项(第 n 项),直至 最终结果的...

递推递归例题

Sample Input 1 1 1 2 2 2 10 4 6 50 50 ...计算出的子问题的解(记忆化搜索) ,减少递归的重复...[j+1]时,显然可以得出递推式 d(i+1,j+1)=d...

pascal中级教程第二章递归与递推

pascal 第7讲 递归与回溯 52页 免费 pascal中级教程...序列总数目,所以我们希望能找出相应的递推公式进行...2.10 电话号码源程序名 可执行文件名 输入文件名 ...

离散数学 用递归和递推分别实现第二类Stirling数

离散数学 用递归和递推分别实现第二类Stirling数_计算机软件及应用_IT/计算机_专业资料。用递归和递推分别实现第二类Stirling数用递归和递推分别实现第二类Stirling数...

算法设计与分析第二版课后习题解答

9.证明下面的公式: 可以使用数学归纳法,也可以像 10 岁的高斯一样,用洞察力...对于计算 n!的递归算法 F(n),建立其递归调用次数的递推关系并求解。 解: 3...

用递推关系理论分析递归算法的时间复杂度

结论在分析递归算法的时间复杂度 t(n)时,如果 t(n)的递推关系式是一个常系数 线性递推关系式,则可以利用母函数与递推关系理论求出其时间复杂度。 [ 参考...

(2)递归与递推

递归与递推深入 81页 3下载券 第十讲 递归与递推式 26页 免费喜欢...A​C​M​之​递​归​与​递​推​例​题​及​解​...