nbhkdz.com冰点文库

第十讲 递归与递推式

时间:2012-12-14


第十讲 递归与递推式

递归的概念:

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

例:计算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 }


递归与递推

递推与递归应用 16页 免费 递归与递推深入 81页 8财富值 第十讲 递归与递推式 26页 免费 (2)递归与递推 7页 1财富值 【11】递推-递归关系 20页 免费...

第三章整理

正确答案: C、E 10 单选(2 分) 关于查找和排序...问题抽象 E 形式化描述 正确答案: B、D、E 12 ...D.递推法比递归算法效率更高。 E 递归法算法的...

递推递归例题

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

递推与递归算法

授课教师:南京市拉萨路小学韩孟江 hanmengjiang@126.com 第七讲 递推与递归算法 学习重点 1、掌握基本的算法——递推。特别是迭代公式的建立。 2、了解递归...

递推递归

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

约瑟夫环递推推导过程

如果能得出一个通式,就可以利用递归、循环等手段解决...小面给出递推式: f(1)=0; f(i)=(f[i-1]...现在假设 m=10 0123 456789 k=3 第一个人出列后...

递推-递归-分治-回溯

递推—递归—分治—回溯 递推算法在程序编辑过程中,我们可能会遇到这样一类问题...递归与分治(一) 23页 免费 第十讲 递归与递推式 26页 免费喜欢...

...(10) 。采用递归方式编写的程序相对于递推方式的程...

当程序运行陷于死循环时,说明程序中存在 (10) 。采用递归方式编写的程序相对于递推方式的程序执行效率较低的原因是 (11) 。 A.递归程序经编译后形成较长目标...

递推与递归应用

春季函授讲义(B3) Jsoi2010 春季函授讲义(B3) 1/16 递推与递归应用一,递推...第十讲 递归与递推式 26页 免费 1 递推与递归 暂无评价 56页 免费 递归与...

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

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