设一个未知函数f.ppt

《设一个未知函数f.ppt》由会员分享，可在线阅读，更多相关《设一个未知函数f.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归法定义n设一个未知函数f，用其自身构成的已知函数g来定义：nF(n)=g(n,f(n-1)n0nF(0)=a n=0n为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2)，类似这种用自身的简单情况来定义自己的方式称为递归定义。递归与递推n相同点：都需要边界条件，递归需要边界条件终止，而递推需要边界条件做为起点。n不同点：在递归过程中，系统用堆栈把每次调用的中间结果保存在栈内，直至求出递归边界值f(0)=a。然后返回调用函数。返回过程中，中间结果依次出栈恢复。简单例子：斐波拉契数列nF(n)=f(n-1)+f(n-2)，f(0)=1，f(1)=2。n对应递

2、归程序为：nFunction fib(n:integer):integer;nBeginnIf n=0 then fib:=1;边界条件qElse if n=1 then fib:=2qElse fib:=fib(n-2)+fib(n-1);nEnd;要点n问题的递归定义，是否能用递归来解决n递归边界，在编写程序的时候有判断和函数返回值n参与递归运算的变量有那些，其中有那些作为值参，哪些作为局部变量。如果有全局变量参与递归运算的话，回溯过程中必须恢复其递归前的状态。典型实例n回忆学过哪些递归算法。计算交点数n在平面上有n条直线，且无三线共点。问这些直线能有多少种不同的交点数？n输入：n n输出

3、：以下若干行列出所有相交方案。其中一行为某一方案的交点个数。计算交点数n分析：我们将n条直线排成一个序列。直线2与直线1最多有一个交点；直线3与直线1和直线2最多有2个交点，直线n与其他n-1条直线最多有n-1个交点。由此得出n条直线互不平行且无三线交于一点的最多交点数为 1+2+3+(n-1)=n*(n-1)/2。设ngi=0表示 交点数i不存在；gi=1表示 交点数i存在计算交点数nn=1 n=2 n=4 ng0=1 g0=1 g1=1 g0=1 g3=1n g4=1 g5=1 n g6=1计算交点数n4条直线的情况n1.4条直线全部平行，无交点，g0=1n2.其中3条平行，交点数为(n-

4、1)*1+0=3，g3=1n3.其中2条平行，这两条直线与另外两条直线之间的交点数为(n-2)*2=4。而另外两条直线本身即可能平行也能相交，因此n(n-2)*2+0=4 g4=1 n(n-2)*2+1=5 g5=1 n4.4条互不平行，交点数为(n-1)*1+3情况n(n-1)*1+0=3 g3=1 n(n-1)*1+2=5 g5=1 n(n-1)*1+3=6 g6=1计算交点数n即n=4时，有0个，3个，4个，5个，6个不同的交点数。由此可得：nM条直线的交点方案(m-r)条平行线与r条直线交叉的交点数+r条直线本身的交点方案(m-r)r+r条直线本身的交点数(1=r=m)n显然，计算不同交点数的问题是递归的。