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）按数列的多少
一元递推关系，只涉及一个数列，上面的均为一元；
多元递推关系，涉及多个数列，如
Fibonacci数列为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
给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
分析：
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(24)
inp[i][j]=inp[i-1][j]+inp[i-1][j-1];
int data[102][102];// 输入
Int inp[102][102]; // 数字和
int n;
while(cin>>n)
{
memset(inp,0,sizeof(inp));
memset(data,0,sizeof(data));
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>data[i][j];
if(i==1) inp[i][j]=data[i][j];
else
inp[i][j]=max(inp[i-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”。
分析：对字符串的长度进行递归处理，当长度为0或1时，结束递归调用。
例如，判定字符串”abcdcba”是否是回文。
当发现串的首字符和尾字符同是’a’时，问题就变成求字符串”bcdcb”是否是回文，继续求字符串”cdc”是否是回文，……，以此类推。当字符串的长度l<=1时，递归调用结束。 
例2．编程递归程序：输入一个自然数，试将其表示成质因数乘积的形式。
分析：对要分解的数字m或当前正在尝试的因子n进行递归调用，当m为1时，结束递归调用。
递归函数：void priNum(int m,int n);
参数 m 为待分解的数字，参数 n 为待尝试的因子。
m%n不为0时，n不是m的一个因子，调用递归函数，继续尝试用n+1去分解m；m%n为0时，n是m的一个因子，调用递归函数，继续用n去分解m/n
例3．编写程序，输入一个整数，将其各位上的数按逆序存放在一个数组中。
分析：设函数是reverse(int *a,int n)，其中第一个参数是存放位的数组，第二个参数是待处理的数。要将n的各位放在a中，就要将n/10（当n≥10时）放在a+1中。如：将n=12345，存放在数组a中，就要将1234放在a+1中，为此，就要将123放在a+2中，以此类推。当n<10时，将n放于a中，递归调用结束。
例4．写出Ackerman函数的非递归算法：
                n+1                      m=0
  akm(m,n)=  akm(m-1,1)            m≠0,n=0
                akm(m-1,akm(m,n-1))    m≠0,n≠0
分析：用栈结构实现其非递归的程序。定义栈元素有4项内容：m、m1、n和r ；
当r为0时，调用akm(m,n)，处理时直接弹栈；
当r为1时，调用akm(m-1,akm(m,n-1))，此时不弹栈而计算akm(m1,n)，即计算akm(m,n-1)。
4  母函数
母函数  对应数列
母函数把 的所有信息浓缩到了一个多项式里。
可以把它作为整体进行运算，而不需要单独考虑每一个ai 。
母函数可分为很多种，包括普通母函数、指数母函数、勒让德级数、贝尔级数和狄利克雷级数。
类似：指数型函数：
构造母函数的目的：解决某个特定的问题。
因此选用何种母函数视乎序列本身的特性和问题的类型。
x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元素a1，a2， …an中取两个组合的全体；
即：x2项的系数=从n个元素a1，a2， …an中取两个的组合
同理：x3项系数包含了从n个元素a1，a2， …an中取3个元素组合的全体；以此类推。 若令a1=a2= …=an=1，则：
(1+x)n是序列C(n,0),C(n,1),...,C(n,n)的母函数
例1：若有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？ 
如果用x的指数表示称出的重量，则：
    1个1克的砝码可以用函数1+x表示，
    1个2克的砝码可以用函数1+x2表示，
    1个3克的砝码可以用函数1+x3表示，
    1个4克的砝码可以用函数1+x4表示
(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)
=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10 
可称出从1克到10克，系数便是方案数。
    例如右端有2x5编程递归函数 项，即称出5克的方案有2：5=3+2=4+1；
同样，6=1+2+3=4+2；10=1+2+3+4。
故称出6克的方案有2，称出10克的方案有1 
例2：求用1分、2分、3分的邮票贴出不同数值的方案数。
因邮票允许重复，故母函数为：
以展开后的x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；
即 ：4=1+1+1+1=1+1+2=1+3=2+2
==母函数模板==
const int _max = 10001;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存没一次的情况
int c1[_max], c2[_max]; 
    int nNum; 
    int i, j, k;
    while(cin >> nNum)
    {
        for(i=0; i<=nNum; ++i)  // ---- ①
        {
            c1[i] = 1;
            c2[i] = 0;
        }
        for(i=2; i<=nNum; ++i)  // ----- ②
        {
            for(j=0; j<=nNum; ++j)  // ----- ③
                for(k=0; k+j<=nNum; k+=i)  // ---- ④
                {
                    c2[j+k] += c1[j];
                }
            for(j=0; j<=nNum; ++j)    // ---- ⑤
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout << c1[n] << endl;
解释上面标志的各个地方：
1 首先对c1初始化，由第一个表达式(1+x+x2+..xn)初始化，把质量从0到n的所有砝码都初始化为1.
2 i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。
③ j 从0到n遍历，这里j就是只一个表达式里第j个变量，比如在第二个表达式里：(1+x2+x4....)里，第j个就是x2*j.
3 k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。