当前位置:首页 >> 学科竞赛 >>

第十讲 递归与递推式


第十讲 递归与递推式

递归的概念:

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

例:计算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页 免费 递归递推 29页 1下载券 递归与递推深入 81页 3下载券 第十讲 递归与递推式 26页 免费 【11】递推-递归关系 20页 免费 递归...
递推与递归练习题
第十讲 递归与递推式 26页 免费 (2)递归与递推 7页 1财富值喜欢...介绍计算机算法中的递归与递推,通过练习熟悉递归与递推。介绍计算机算法中的递归...
递归与递推练习
第十讲 递归与递推式 26页 免费喜欢此文档的还喜欢 递归习题 64页 免费 递归基础练习题 9页 2财富值 递归强化练习 8页 免费 递归算法习题 3页 免费 C语言...
递归与递推上机题
29页 5财富值 递归与递推 69页 2财富值 递推与递归应用 16页 免费 递归与递推深入 81页 8财富值 第十讲 递归与递推式 26页 免费喜欢此文档的还喜欢 ...
递归递推
递归与递推 8页 1财富值 递推与递归应用 16页 免费 递归与递推深入 81页 8财富值 递推和递归 4页 免费 第十讲 递归与递推式 26页 免费 (2)递归与递...
递推与递归算法
. 本程序的递推运算可用如下图示描述: 递推算法以初始{起点}值为基础,用相同...4 递推与递归 39页 免费 第十讲 递归与递推式 26页 免费 递推与递归应用...
递推与递归算法
授课教师:南京市拉萨路小学韩孟江 hanmengjiang@126.com 第七讲 递推与递归算法 学习重点 1、掌握基本的算法——递推。特别是迭代公式的建立。 2、了解递归...
递归和递推习题
(递归和递推) 1、 有一对兔子,从出生后第 3 个月起每个月都生一对兔子,小兔子长到第三个月后每个月 又生一对兔子,假如兔子都不死,问第 10 个月的兔子...
第3章 模拟训练(计算思维)
A.“递归”源自于数学上的递推式和数学归纳法 B.“递归与递推式一样,都是自递推基础计算起,由前项(第 n-1 项)计算后项(第 n 项),直至 最终结果的...
递规与递推
归纳推理(递推法) 9页 免费 第十七讲 递推法解...JSOI 2006 夏令营 递归与递推 递 归 与 递递归 ...包含一个自然数 n(1≤n≤10) ,即圆盘的个数。...
更多相关标签:
递推法和递归法 | 递推法和递归法的联系 | 递推和递归 | 递归和递推的区别 | 什么是递推法和递归法 | 递推 递归 | 递归与递推 | 递推与递归的区别 |