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

ACM暑期集训组合数学(4) 递推递归母函数
1 递推关系
序列{an}=a0,a1,…,an,…,把 an 与某些ai(i<n)联系起来的等式叫做关于序列{an}的递推方程。当给定递推方程和适当的初值就唯一确定了序列。
递推关系分类:
(1)按常量部分:
齐次递推关系:指常量=0,如F(n)=F(n-1)+F(n-2)
非齐次递推关系:指常量≠0,如F(n)=2*F(n-1)+1
(2)按运算关系:
线性关系,如上面的两个;
非线性关系,如F(n)=F(n-1)*F(n-2)。
(3)按系数:
常系数递推关系,如(1)中的两个;
变系数递推关系,如D(n)=(n-1)(D(n-1)+D(n-2)。
(4)按数列的多少
一元递推关系,只涉及一个数列,上面的均为一元;
多元递推关系,涉及多个数列,如
i数列为1,1,2,3,5,8,13,.....
long long data[100];
data[1]=1;
data[2]=1;
for(int i=3;i<=50;i++) data[i]=data[i-1]+data[i-2];
while(cin>>n) cout<<data[n]<<endl;
例1:直线割平面问题。在一个无限的平面上有N条直线,试问这些直线最多能将平面分割成多少区域?
F(1) = 2; F(2) = 4; F(3) = 7; F(n)=F(n-1)+n; (n>1)
int recurrence(int n) //递推
{
f[1]=2;
for(i=2;i<=n;i++) f[n]=f[n-1]+n;
return f[n];
}
int recursion(int n) 递归:
{
if(n==1) return 2;//递归终止条件
else return recursion(n-1)+n;
}
更快的方法是求出通项:F(n)=n^(n+1)/2+1
例2:HDOJ2050 折线割平面问题在一个无限的平面上有N条折线,试问这些折线最多能将平面分割成多少区域?
F(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=2
0出现偶数次的数 00,11,12,13,14,15,…,77,共50个
0出现奇数次的数 01,10,02,20,03,30,…,70,共14个
数字三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数