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

ACM 暑期集训组合数学( 4)递推递归母函数 1 递推关系序列{a n }= a 0,a 1,…,a n,…,把 a n 与某些 a i(i<n) 联系起来的等式叫做关于序列{a n} 的递推方程。当给定递推方程和适当的初值就唯一确定了序列。递推关系分类: (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 )按数列的多少一元递推关系,只涉及一个数列, 上面的均为一元; 多元递推关系,涉及多个数列,如11 117 7 nnn nnnabb baa 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 出现偶数次的共有 na 个,0 出现奇数次的共有 nb 个。求na 和 nb 满足的递推关系。对0 出现偶数次的 n 位八进制数分两种情况讨论: (1 )最高位是 0 ,则其余 n-1 位应该含有奇数个 0 ,这类数共有 1nb 个。(2 )最高位非 0 ,则其余 n-1 位应该含有偶数个 0 ,这类数共有 71na 个。因此有 na =71na +1nb 。同理可得 nb =1na +71nb ,所以 na 、nb 满足1,7 ,7 ,7 11 11 11ba abb baa nnn nnn 例n=20 出现偶数次的数 00, 11, 12, 13, 14, 15,…, 77 ,共 50个 0 出现奇数次的数 01, 10, 02, 20, 03