资源描述：
《pascal递归算法 noip竞赛材料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、信息学竞赛―――递归算法一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).递归程序包含递归和递推两个过程，这两个过程又都是根据一个递推公式进行的。一般来说，能够用递归解决的问题应该满足以下三个条件①需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同；②递归调用的次数必须是有限的；③必须有结束递归的条件（边界条件）来终止递归。例1、楼梯共有N阶台阶，上楼可以以一步上一个台阶，也可以一步上二个台阶。编一个程序计算上N阶台
2、阶，共有多少种走法？programstair(input,output);vars,n:integer;functionf(n:integer):integer; begin ifn<3thenf:=n elsef:=f(n-1)+f(n-2); end;begin readln(n); s:=f(n); writeln('s=',s);end.例2、骨牌铺法有1*n的一个长方形，用一个1＊1、1＊2、1＊3的骨牌铺满方格。例如当n=3时为1＊3的方格。此时用1
3、＊1，1＊2，1＊3的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种铺法。● ● ●●●● ● ● ● 输入n(0<=n<=30) 输出 铺法总数分析:这道题可以采用猜测法，从具体的n=1,2,3,......开始，列举出结果，根据列举的部分结果进行猜测，推导出公式。这个猜测推导过程留给读者完成。问题是：这种方法中“猜”和“凑”的成分比较多，容易出错。我们不妨采用组合数学常用的待定系数进行归纳和推导。设推导公式如下：f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3
4、)+d*f(n-4)+....(a,b,c,d...是常系数)即1＊n的长方形的铺法由全部（a种）1＊（n-1）的长方形铺法总数加上全部（b种）1*(n-2)的长方形的铺法总数加上全部（c种）1*(n-3)的长方形的铺法总数......注意排除重复情况。（1）将n格分成1格和n-1格，计算f(n-1)的系数a。右端1格的铺法有一种（a）。显然，在一格中只有一种铺法，即f(n-1)的系数a=1。● ● (2)将n格分成2格和n-2格，计算f(n-2)的系数b。右端2格的铺法有两种（b）。由图可见，（b）
5、的铺法包含在(a)的铺法中，而（c）的铺法不同于（a），因此f(n-2)的系数b=1。 (3)将n格分成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)程序
6、：varn:integer;functionf(i:integer):longint;begin ifiin[1..2]thenf:=ielseifi=3thenf:=4elsef:=f(I-1)+f(I-2)+f(I-3);end;begin readln(n);writeln(f(n));end.“铺砖问题”有推广价值。例如某人走n级的楼梯，每步可以走1级、2级或3级，走完n级楼梯共有多少种走法。这个问题的数学意义和解法与“铺砖问题”相同。 例3:划分问题 设s是一个具有n个元素的集合s={a1,a2
7、,…an},现将s集合划分成k个满足下列条件的子集合s1,s2，s3。。。。； 1、si<>空； 2、si∩sj=空； 3、s1∪s2∪s3….∪sn=s (1<=i,j<=k,i<>j)则称s1,s2…sn是集合s的一个划分，它相当于把集合s中的n个元素放入k个无标号的盒子中，使得没有一个盒子为空，试确定n个元素的集合放入k个无标号盒的划分数s(n,k)【算法分析】: 例如S＝｛1，2，3，4｝，k＝3。细心的读者稍加分析后，不难得出S有6种不同的划分方案，即划分数为6。其
8、方案为｛1，2｝∪｛3｝∪｛4｝ ｛1，3｝∪｛2｝∪｛4｝ ｛1，4｝∪｛2｝∪｛3｝ ｛2，3｝∪｛1｝∪｛4｝ ｛2，4｝∪｛1｝∪｛3｝ ｛3，4｝∪｛1｝∪｛2｝ 如果对于任意的S集合和k值，就不能凭籍直觉和经验计算划分数和枚举划分方案了。必须总结出一个数学规律:设n个元素a1…an放入k个无标号盒的划分数为S(n，k)。在配置过程
