递推与递归精选文档.ppt

递推与递归本讲稿第一页，共四十四页递递 推推 有些问题中，相邻两项或多项数字（或状态）之间存在某种关系，可以通过前一项或多项按照某一规律推出其后一项数字（或状态），或者是通过后一项或多项按照某一规律推出其前一项数字（或状态）。我们可将这种规律归纳成如下递推关系式：Fn=g(Fn-1)或者Fn-1=g(Fn)本讲稿第二页，共四十四页递递 推推已知初始值F1，通过递推关系式Fn=g(Fn-1)求出最终结果Fn的递推方式称为顺推法；同理，把已知最终结果为Fn，通过递推关系式Fn-1=g(Fn)求出初始值F1的递推方式称为倒推法。本讲稿第三页，共四十四页递递 推推Fibonacci数列：Hn=Hn-1+Hn-2Fibonacci数列大家都非常熟悉，来源于中世纪数学家Fibonacci提出的一个问题：一对刚出生的兔子过两个月后,可以繁殖一对新兔子,问原有雌雄各一只兔子，经过十一个月后，能繁殖多少只兔子。本讲稿第四页，共四十四页递递 推推【例题1】同一平面内有n（n500）条直线，已知其中p（p2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？本讲稿第五页，共四十四页递递 推推【问题分析】由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考虑剩下的n-p条直线。首先可以直接求出，p条相交于一点的直线将平面划分成的区域数为2p个；然后在平面上已经有k（kp）条直线的基础上，再加上一条直线，最多可以与k条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以fi=fi-1+i（ip），边界条件在前面已经计算过了，是fp=2p。本讲稿第六页，共四十四页递递 推推 f(p)=2*p f(i)=f(i-1)+i (ip)本讲稿第七页，共四十四页递递 推推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.本讲稿第八页，共四十四页递递 推推【例题2】（NOIP2002初中组第4题）棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下或向右。同时在棋盘上的任一点有一个对方的马（如图的一个对方的马（如图的C C点），该马所在的点和所点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不有跳跃一步可达的点称为对方马的控制点。卒不能走到对方马的控制点。能走到对方马的控制点。本讲稿第九页，共四十四页递递 推推棋盘用坐标表示，A点坐标（0,0）、B点坐标（n,m）（n，m为不超过20的整数，并由键盘输入），同样马的位置坐标C是需要给出的（CA且CB），现在从键盘输入B点的坐标（n,m）以及对方马的坐标（x,y），要求你计算出卒从A点能够到达B点的路径条数。本讲稿第十页，共四十四页递递 推推【问题分析】在学习回溯或搜索时，跳马是一道典型的例题，有些同学在比赛时用了搜索，但事实证明：当n，m=15就会超时。其实，对本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（称之为左点）或是从上面过来（称之为上点）。本讲稿第十一页，共四十四页递递 推推根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐行（或逐列）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。本讲稿第十二页，共四十四页递递 推推假设用Fi,j表示到达点（i,j）的路径数目，用gi,j表示点（i,j）是否是对方马的控制点，gi,j=0表示不是对方马的控制点，gi,j=1表示是对方马的控制点。则可得到如下的递推关系式：Fi,j=0 gi,j=1 F0,j=F0,j-1 j0，g0,j=0 Fi,0=Fi-1,0 i0，gi,0=0 Fi,j=Fi-1,j+Fi,j-1 i0，j0，gi,j=0 本讲稿第十三页，共四十四页递递 推推program ex2;const maxn=20;maxm=20;dx:array1.8 of integer=(2,1,-1,-2,-2,-1,1,2);dy:array1.8 of integer=(1,2,2,1,-1,-2,-2,-1);var f:array0.maxn,0.maxm of int64;g:array-2.maxn+2,-2.maxm+2 of boolean;n,m,x,y:integer;i,j:integer;本讲稿第十四页，共四十四页递递 推推begin readln(n,m,x,y);fillchar(f,sizeof(f),0);fillchar(g,sizeof(g),true);gx,y:=false;for i:=1 to 8 do gx+dxi,y+dyi:=false;本讲稿第十五页，共四十四页递递 推推if g0,0 then f0,0:=1;for i:=1 to m do if g0,i then f0,i:=f0,i-1;for i:=1 to n do if gi,0 then fi,0:=fi-1,0;for i:=1 to n do for j:=1 to m do if gi,j then fi,j:=fi-1,j+fi,j-1;writeln(fn,m);本讲稿第十六页，共四十四页递递 推推【例题3】特殊的子集集合M=1,2,3,n的子集中，有一些是不含相邻自然数元素的。例如：n=4时，集合1,3是满足要求的，而1,3,4是不满足的，因为它含有相邻自然数3和4。把所有满足要求的子集记作Si，对于每一个Si计算出它的所有元素的乘积Ti，求Ti2。输入仅一行，包括一个正整数n(n100)输出仅一行，即Ti的平方和，可能会超出长整型范围。本讲稿第十七页，共四十四页递递 推推样例输入：4样例输出：1191,2,3,4中符合题目要求的子集有：1,2,3,4,1,3,1,4,2,4 12+22+32+42+(1*3)2+(1*4)2+(2*4)2=1+4+9+16+9+16+64=119本讲稿第十八页，共四十四页递递 推推1,2,3的情况：1,2,3,1,3f(3)1,2,3,4的情况：1,2,3,4,1,3,1,4,2,4f(4)1,2,3,4,5的情况：1,2,3,4,5,1,3,1,4,1,5,2,4,2,5,3,5,1,3,5 f(5)f(5)=f(4)+f(3)*5f(5)=f(4)+f(3)*52 2+5+52 2f(i)=f(i-1)+f(i-2)*if(i)=f(i-1)+f(i-2)*i2 2+i+i2 2本讲稿第十九页，共四十四页递递 推推f(1)=12=1f(2)=12+22=5f(3)=f(2)+f(1)*32+32=23f(4)=f(3)+f(2)*42+42=119f(n)=f(n-1)+f(n-2)*n2+n22!-13!-14!-15!-1(n+1)!-1本讲稿第二十页，共四十四页递递 推推【讨论1】平面分割问题设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。本讲稿第二十一页，共四十四页递递 推推【讨论2】Catalan数在一个凸n边形中，通过不相交于的n边形内部的对角线，把n边形拆分成若干三角形。拆分方法的数目用hn表示，hn即为Catalan数。例如，五边形有如下五种拆分方案，故h5=5。求一个任意的凸n边形相应的hn。本讲稿第二十二页，共四十四页递递 归归递归算法设一个未知函数f，用其自身构成的已知函数g来定义：f(n)=g(n,f(n-1)n0f(0)=a n=0则称函数f为递归函数（递归公式），为了求f(n)，我们必须先求f(n-1)，为了求f(n-1),又必须去求f(n-2)，为了求f(1),必须先求f(0),而f(0)是已知的。这种定义函数的方式称为递归定义。本讲稿第二十三页，共四十四页递递 归归一个递归定义必须是有确切含义的，也就是说一步比一步简单，最终是有终结的，决不能无限循环下去。比如上例中的f(0)=a，这种最简单的情况（终结条件），称为递归边界，它是递归定义必不可少的一部分。描述递归定义的函数或求解递归问题的过程称为递归算法。本讲稿第二十四页，共四十四页递递 归归不论是递归过程，还是递归函数，按其调用的方式一般分为直接递归（子程序P直接调用自己）和间接递归（子程序P调用其它子程序，其它子程序又调用P）。本讲稿第二十五页，共四十四页递递 归归递归算法一般适用在三个场合：一是数据的定义形式是递归的，如求Fibonacci数列问题；二是数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作；三是某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。本讲稿第二十六页，共四十四页递递 归归递归不仅可用于计算、计数，而且还可用于枚举，即把所有具有各某种特性的对象完全枚举出来，关键是如何从输入参数与输出结果之间的对应关系中归纳出递归公式和边界条件。本讲稿第二十七页，共四十四页递归的应用举例【例题4】集合的划分【问题描述】设是一个具有n个元素的集合，a1，a2，an，现将划分成K个满足下列条件的子集合s1，s2，sk，且满足：1si2sisj (1i，jk ij)3s1s2s3sk则称s1，s2，sk是集合的一个划分。它相当于把集合中的n个元素a1，a2，an 放入k个（0knk，k0)。本讲稿第三十二页，共四十四页递归的应用举例确定s(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，(n，k)0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即kn时,(n，k)0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，s(n,k)=1。因此，我们可以得出划分数(n，k)的递归关系式为：s(n，k)s(n1，k1)+k*s(n1，k)(nk，k0)s(n，k)0 (n0若直线存在，则递归计算所有的交叉情况then for r:=m downto 1 do try(m-r，j+r*(m-r)else gj1;否则确定m条直线存在j个交点end；本讲稿第四十一页，共四十四页递归的应用举例1、计算max：max=n*(n-1)/2；计算n条直线的最多交点数2、初始化：fillchar(g，sizeof(g)，0)；3、递归求gi：try(n，0)；4、统计方案数并输出：total：=0；for i：=0 to max do if gi=1 then begin total:=total+1；输出第total个方案的交点数i；end；本讲稿第四十二页，共四十四页递推与递归的比较递推与递归的比较共同点：1、数据元素可以用抽象的公式表示2、具有边界条件不同点：1、递推从边界出发求其结果2、递归从问题自身出发达到边界本讲稿第四十三页，共四十四页动态规划的实质动态规划的实质递归的思想，递推的做法本讲稿第四十四页，共四十四页