首页 > 代码库 > 母函数及相关的算法题
母函数及相关的算法题
母函数即生成函数，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)，是组合数学中尤其是计数方面的一个重要理论和工具。
(1+a1x)(1+a2x)(1+a3x)...(1+anx)=1+(a1+a2+a3+...+an)x+(a1a2+a1a3+...+an-1an)x2+...+(a1a2a3*...*an)xn
由此可以看出:
1. x的系数是a1,a2,…an的单个组合的全体。相当于从a1,a2,…an选1个进行组合，然后加在一起
2. x2的系数是a1,a2,…an的两个组合的全体。相当于从a1,a2,…an选2个进行组合，然后加在一起
………
n. xn的系数是a1,a2,….an的n个组合的全体（只有1个）。相当于从a1,a2,…an选n个进行组合，然后加在一起
如果我们把a1,a2,…an的值设为1的话
原式就变成了
（1+x)n=1+C(n,1)x+C(n,2)x2+C(n,3)x3+…+C(n,n)xn
利用这种关系，我们可以解决一些算法问题
例1、有面值为1,2,3的硬币各一个，问有几种组合?
我们把所有的组合这么想：
(不拿面值为1的，拿一个面值为1的)*(不拿一个面值为2的，拿一个面值为2的)*(不拿一个面值为3的，拿一个面值为3的)
==（面值为0的个数，面值为1的个数，面值为2的个数，面值为3的个数，面值为4的个数，面值为5的个数，面值为6的个数）
我们用x表示硬币，x的指数表示硬币的面值，这样：
1克的硬币组合可以用函数x0+x1表示，x0表示不拿一个面值为1的，x1表示拿一个面值为1的
2克的硬币组合可以用函数x0+x2表示，x0表示不拿一个面值为2的，x2表示拿一个面值为2的
3克的硬币组合可以用函数x0+x3表示，x0表示不拿一个面值为3的，x3表示拿一个面值为3的
所有的组合就可以这么表示出来了：
（1+x)(1+x2)(1+x3)==1+x+x2+2x3+x4+x5+x6
x前的系数就相当于称出相应硬币的面值的组合数目
比如面值为3的有两种组合，（拿一个面值为3的，和那一个1个面值为1和面值为2的）
例2、有面值为1的硬币3个，面值为2的硬币2个，面值为3的硬币1个，问有多少种组合？
1克的硬币组合可以用函数x0+x1 +x2+x3表示，x0表示不拿一个面值为1的，x1表示拿1个面值为1的,x2表示拿2个面值为1的,x3表示拿3个面值为1的
2克的硬币组合可以用函数x0+x2+x4表示，x0表示不拿一个面值为2的，x2表示拿一个面值为2的，x4表示拿3个面值为2的
3克的硬币组合可以用函数x0+x3表示，x0表示不拿一个面值为3的，x3表示拿1个面值为3的,x6表示拿2个面值为3的
所有的组合就可以这么表示出来了：
(x0+x1 +x2+x3)*(x0+x2+x4)*( x0+x3)
例3、有面值为1,2,3的硬币无数个，问有多少种组合?
1克的硬币组合可以用函数x0+x1 +x2+…+xn表示，分别代表拿0个，1个，2个…n个的情况。
2克的硬币组合可以用函数x0+x2+x4+…+x2n表示,分别代表拿0个，1个，2个，n个的情况。
3克的硬币组合可以用函数x0+x3+x6+…+x3n表示,分别代表拿0个，1个，2个，n个的情况。
所有的组合就可以这么表示出来了：
(x0+x1 +x2+…+xn)*(x0+x2+x4+…+x2n)*(x0+x3+x6+…+x3n)
现在就例2的例子给出代码与分析
有面值为1的硬币3个，面值为2的硬币2个，面值为3的硬币1个，问有多少种组合？
//(x0+x1 +x2+x3)*(x0+x2+x4)*( x0+x3)struct Coin{ int value; int number;};const int MAX = 50;int main(){ Coin coin[3]; coin[0].value = http://www.mamicode.com/1; coin[0].number = 3; coin[1].value = http://www.mamicode.com/2; coin[1].number = 2; coin[2].value = http://www.mamicode.com/3; coin[2].number = 1; int result[MAX] = { 0 }; int temp[MAX] = { 0 }; int number; while (cin >> number) { for (int i = 0; i < MAX; i++) { result[i] = 0; temp[i] = 0; } for (int i = 0; i <=coin[0].number;i++) { result[i*coin[0].value] = 1; } for (int i = 1; i < 3; i++) { for (int j = 0; j <=number; j++) { for (int k = 0, index = 0; index <=coin[i].number && (k + j)<=number; index++, k += coin[i].value) { temp[j + k] += result[j]; } } for (int j = 0; j <=number; j++) { result[j] = temp[j]; temp[j] = 0; } } cout << result[number] << endl; }}
我们对②进行分析
它的循环不变式是result[0]-result[number]记录了每次新增面额为coin[i].value时的所有组合数目，面值为i的有result[i]种组合。
初始化：首先，先来证明在第一轮迭代之前，它是成立的。 在①中，把第一个面额硬币的组合赋给了result,for (int i = 0; i <=coin[0].number;i++)①
{
result[i*coin[0].value] = 1;
}
此时result记录了第一个面额硬币的所有组合及其数目。所以在循环开始前循环不变式是正确的。
保持： 这里的i代表了当前计算的式子，因为①已经计算完了第一个式子，所以i从1开始，到2截止(数组的下标是从0开始)
j每次需要更新的面值，所以从0开始到number截止，
k代表了第i个式子的增量，index第i个式子的第几个遍历。所以对于第i个式子，k为coin[i].value，index从0开始到coin[i].number截止;当index已经coin[i].number或是当前面值j加上增量k之后已经超过了所要求的面值即可停止循环
每次迭代面值为j的，现在面值变成了j+k的，所以面值为j+k的为为原有的面值为j的数目加上新的面值为j+k的数目
然后将temp赋予result，将temp清零，开始下一次迭代。
终止：对此算法来说，当i大于数组的长度（即所有面额的硬币都计算完毕），for循环结束。这时result[0]-result[number]记录了面额为0到number所有组合的数目
参考文章：
母函数（Generating function）详解 http://www.wutianqi.com/?p=596
什么是生成函数？ http://www.matrix67.com/blog/archives/120
母函数及相关的算法题