资源描述：
《pascal递归算法-noip竞赛材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、信息学竞赛递归算法一个过程(或函数)直接或间接调用自己木身，这种过程(或函数)叫递归过程(或函数)•递归程序包含递归和递推两个过程，这两个过程又都是根据一个递推公式进行的。一般來说，能够丿IJ递归解决的问题应该满足以下三个条件①需要解决的问题町以化为一个或多个了问题來求解，而这些了问题的求解方法与原來的问题完全相同，只是在数量规模上不同；②递归调用的次数必须是有限的；③必须有结束递归的条件(边界条件)來终止递归。例1、楼梯共有N阶台阶，上楼可以以一步上一个台阶，也可以一步上二个台阶。编一个程序计算上
2、N阶台阶，共有多少种走法？programstair(input,output);vars,n:integer;functionf(n:integer):integer;beginifn<3thenf:=nelsef:=f(n-1)+f(n-2);end;beginreaclln(n);s:=f(n);writeln('s二'，s);end.例2、骨牌铺法有l*n的一个长方形，用一个1*1、1*2、1*3的骨牌铺满方格。例如当n=3时为1*3铺法。的方格。此时用1*1,1*2,1*3的骨牌铺满方格，共
3、有四种铺法。图4.4.3列出了四种输入n(0<=n<=30)输出铺法总数分析:这道题可以采用猜测法，从具体的n=l,2,3,开始，列举出结果,根据列举的部分结果进行猜测，推导出公式。这个猜测推导过程留给读者完成。问题是：这种方法屮“猜”和“凑”的成分比较多，容易出错。我们不妨采用纽合数学常用的待定系数进行归纳和推导。设推导公式如下：f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)+....(a,b,c,d...是常系数)即l*n的长方形的铺法由全部种)1*(n-1)的
4、长方形铺法总数加上全部(b种)信息学竞赛递归算法一个过程(或函数)直接或间接调用自己木身，这种过程(或函数)叫递归过程(或函数)•递归程序包含递归和递推两个过程，这两个过程又都是根据一个递推公式进行的。一般來说，能够丿IJ递归解决的问题应该满足以下三个条件①需要解决的问题町以化为一个或多个了问题來求解，而这些了问题的求解方法与原來的问题完全相同，只是在数量规模上不同；②递归调用的次数必须是有限的；③必须有结束递归的条件(边界条件)來终止递归。例1、楼梯共有N阶台阶，上楼可以以一步上一个台阶，也可以一
5、步上二个台阶。编一个程序计算上N阶台阶，共有多少种走法？programstair(input,output);vars,n:integer;functionf(n:integer):integer;beginifn<3thenf:=nelsef:=f(n-1)+f(n-2);end;beginreaclln(n);s:=f(n);writeln('s二'，s);end.例2、骨牌铺法有l*n的一个长方形，用一个1*1、1*2、1*3的骨牌铺满方格。例如当n=3时为1*3铺法。的方格。此时用1*1,1
6、*2,1*3的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种输入n(0<=n<=30)输出铺法总数分析:这道题可以采用猜测法，从具体的n=l,2,3,开始，列举出结果,根据列举的部分结果进行猜测，推导出公式。这个猜测推导过程留给读者完成。问题是：这种方法屮“猜”和“凑”的成分比较多，容易出错。我们不妨采用纽合数学常用的待定系数进行归纳和推导。设推导公式如下：f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)+....(a,b,c,d...是常系数)即l*n的长方形的
7、铺法由全部种)1*(n-1)的长方形铺法总数加上全部(b种)l*(n-2)的长方形的铺法总数加上全部(c种)l*(n-3)的长方形的铺法总数注意排除垂复情况。(1)将n格分成1格和n-1格，计算f(n-l)的系数a。右端1格的铺法有一种(a)0显然,在一格中只有一种铺法,即f(n-l)的系数沪1。•■(2)将n格分成2格和n-2格，计算f(n-2)的系数b。右端2格的铺法有两种(b)o由图可见，(b)的铺法包含在(a)的铺法中，而(c)的铺法不同于(a),因此f(n-2)的系数b=l。(3)将n格分
8、成3格和n-3格,计算f(n-3)的系数c。右端3格的铺法有两种(图4.4.5)。由图可见，(d)(e)(f)的铺法都可以归结到1格或2格屮去，只有1*3的铺法(g)属于新的，因此f(n-3)的系数c二1。将n格分成n-x格和x格(4<=x<=n-4)的情况都是重复的，因此不再讨论。由此得出：f(1)=1,f(2)=2,f(3)=4,f(n)=f(n-1)+f(n~2)+f(n-3)(n>=5)程序：varn:iriteger;functionf(i:integer)
