递推与递归.ppt

递推和递归

1
递 推
有些问题中，相邻两项或多项数字（或状态）之间存在某种关系，可以通过前一项或多项按照某一规律推出其后一项数字（或状态），或者是通过后一项或多项按照某一规律推出其前一项数字（或状态）。我们可将这种规律归纳成如下递推关系式：
Fn=g(Fn-1)或者Fn-1=g＇(Fn)
2
递 推
已知初始值F1，通过递推关系式Fn=g(Fn-1)求出最终结果Fn的递推方式称为顺推法；同理，把已知最终结果为Fn，通过递推关系式Fn-1=g＇(Fn)求出初始值F1的递推方式称为倒推法。
3
递 推
Fibonacci数列：Hn = Hn-1 + Hn-2
Fibonacci数列大家都非常熟悉，来源于中世纪数学家Fibonacci提出的一个问题：一对刚出生的兔子过两个月后,可以繁殖一对新兔子,问原有雌雄各一只兔子，经过十一个月后，能繁殖多少只兔子。
4
递 推
【例题1】
同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？
5
递 推
【问题分析】
由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。
首先可以直接求出，p条相交于一点的直线将平面划分成的区域数为2p个；
然后在平面上已经有k（k≥p）条直线的基础上，再加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以fi=fi-1+i（i＞p），边界条件在前面已经计算过了，是fp=2p。
6
递 推
f(p)=2*p
f(i)=f(i-1)+i (i>p)
7
递 推
program ex1;
var
n,p,total,i:longint;
begin
readln(n,p);
total:=2*p;
for i:=p+1 to n do
total:=total+i;
writeln(total);
end.
8
递 推
【例题2】（NOIP2002初中组第4题）
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下或向右。
同时在棋盘上的任一点有
一个对方的马（如图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不能走到对方马的控制点。
9
递 推
棋盘用坐标表示，A点坐标（0,0）、B点坐标（n,m）（n，m为不超过20的整数，并由键盘输入），同样马的位置坐标C是需要给出的（C≠A且C≠B），现在从键盘输入B点的坐标（n,m）以及对方马的坐标（x,y），要求你计算出卒从A点能够到达B点的路径条数。
10