组合数学(4)递推递归母函数

《组合数学(4)递推递归母函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM暑期集训组合数学（4）递推递归母函数1递推关系序列{an}=a0，a1，…，an，…，把an与某些ai(i

2、(n-1)(D(n-1)+D(n-2)。（4）按数列的多少一元递推关系，只涉及一个数列，上面的均为一元；多元递推关系，涉及多个数列，如Fibonacci数列为1,1,2,3,5,8,13,.....longlongdata[100];data[1]=1;data[2]=1;for(inti=3;i<=50;i++)data[i]=data[i-1]+data[i-2];while(cin>>n)cout<

3、1)=2;F(2)=4;F(3)=7;F(n)=F(n-1)+n;(n>1)intrecurrence(intn)//递推{f[1]=2;for(i=2;i<=n;i++)f[n]=f[n-1]+n;returnf[n];}intrecursion(intn)递归：{if(n==1)return2;//递归终止条件elsereturnrecursion(n-1)+n;}更快的方法是求出通项：F(n)=n^(n+1)/2+1例2：HDOJ2050折线割平面问题在一个无限的平面上有N条折线，试问这些折线最多能将平面分割成多少区域？F

4、(n)=F(n-1)+4n-3;F(n)=2*n^2-n+1;例3：椭圆割平面问题。在一个无限的平面上有N个椭圆，试问这些椭圆最多能将平面分割成多少区域？F(n)=F(n-1)+4(n–1);设n位八进制数中0出现偶数次的共有个，0出现奇数次的共有个。求和满足的递推关系。对0出现偶数次的n位八进制数分两种情况讨论：（1）最高位是0，则其余n－1位应该含有奇数个0，这类数共有个。（2）最高位非0，则其余n－1位应该含有偶数个0，这类数共有7个。因此有＝7＋。同理可得＝＋7，所以、满足例n＝20出现偶数次的数00，11，12，13，

5、14，15，…，77，共50个0出现奇数次的数01，10，02，20，03，30，…，70，共14个数字三角形738810274445265给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。分析：7（7）3（10）8（15）8（18）1(max(10,15)+1=16)0(15)2(20)7(25)4(20)4(19)4(24)5(30)2(27)6(26)5

6、(24)inp[i][j]=inp[i-1][j]+inp[i-1][j-1];intdata[102][102];//输入Intinp[102][102];//数字和intn;while(cin>>n){memset(inp,0,sizeof(inp));memset(data,0,sizeof(data));for(inti=1;i<=n;i++)for(intj=1;j<=i;j++){cin>>data[i][j];if(i==1)inp[i][j]=data[i][j];elseinp[i][j]=max(inp[i-

7、1][j],inp[i-1][j-1])+data[i][j];}}2常系数线性齐次递推方程求解例：Fibnacci序列F(n)=F(n-1)+F(n-2),F(1)=1,F(2)=1特征方程为，有两个实根：，通解：，代入n=1，n=2解得：，3递归关系递归就是函数直接或间接调用自己，是一种描述问题和解决问题的基本方法。递归有两个基本要素：⑴边界条件：确定递归到何时终止；⑵递归模式：大问题是如何分解为小问题的例1．编写一个递归函数，完成回文的判定。回文是如下形式的对称字符串：”a”，”abccba”，”abcdcba”。分析：对

8、字符串的长度进行递归处理，当长度为0或1时，结束递归调用。例如，判定字符串”abcdcba”是否是回文。当发现串的首字符和尾字符同是’a’时，问题就变成求字符串”bcdcb”是否是回文，继续求字符串”cdc”是否是回文，……，以此类推。当字符串的长度l<=1时，