pascal递归算法 noip竞赛材料

pascal递归算法 noip竞赛材料

ID:6647681

大小:119.50 KB

页数:21页

时间:2018-01-21

pascal递归算法 noip竞赛材料_第1页
pascal递归算法 noip竞赛材料_第2页
pascal递归算法 noip竞赛材料_第3页
pascal递归算法 noip竞赛材料_第4页
pascal递归算法 noip竞赛材料_第5页
资源描述:

《pascal递归算法 noip竞赛材料》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、信息学竞赛―――递归算法一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).递归程序包含递归和递推两个过程,这两个过程又都是根据一个递推公式进行的。一般来说,能够用递归解决的问题应该满足以下三个条件①需要解决的问题可以化为一个或多个子问题来求解,而这些子问题的求解方法与原来的问题完全相同,只是在数量规模上不同;②递归调用的次数必须是有限的;③必须有结束递归的条件(边界条件)来终止递归。例1、楼梯共有N阶台阶,上楼可以以一步上一个台阶,也可以一步上二个台阶。编一个程序计算上N阶台阶,共有多少种走法?programstair(input,output);vars

2、,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*1,1*2,1*3的骨牌铺满方格,共有四种铺法。图4.4.3列出了四种铺法。●  ●  ●●●●   ●        ●  ●  输入n(0<=n<=30)  

3、输出 铺法总数分析:这道题可以采用猜测法,从具体的n=1,2,3,......开始,列举出结果,根据列举的部分结果进行猜测,推导出公式。这个猜测推导过程留给读者完成。问题是:这种方法中“猜”和“凑”的成分比较多,容易出错。我们不妨采用组合数学常用的待定系数进行归纳和推导。设推导公式如下:f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)+....(a,b,c,d...是常系数)即1*n的长方形的铺法由全部(a种)1*(n-1)的长方形铺法总数加上全部(b种)1*(n-2)的长方形的铺法总数加上全部(c种)1*(n-3)的长方形的铺法总数......注意排除重

4、复情况。(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)的铺法包含在(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格和

5、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: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级楼梯共有多少种走法。这个

6、问题的数学意义和解法与“铺砖问题”相同。 例3:划分问题 设s是一个具有n个元素的集合s={a1,a2,…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种不同的划分方

7、案,即划分数为6。其方案为{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)。在配置过程

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。