在数学中,某个序列的母函数是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
母函数可分为很多种,包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。
由此可以看出:
1.x的系数是a1,a2,…an的单个组合的全体。
2.x2的系数是a1,a2,…a2的两个组合的全体。
………
n.xn的系数是a1,a2,….an的n个组合的全体(只有1个)。
由此得到:
母函数的定义:
对于序列a0,a1,a2,…构造一函数:
称函数G(x)是序列a0,a1,a2,…的母函数
这里先给出2个例子,等会再结合题目分析:
第一种:
有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案?
考虑用母函数来接吻这个问题:
我们假设x表示砝码,x的指数表示砝码的重量,这样:
1个1克的砝码可以用函数1+x表示,
1个2克的砝码可以用函数1+x2表示,
1个3克的砝码可以用函数1+x3表示,
1个4克的砝码可以用函数1+x4表示,
上面这四个式子懂吗?
我们拿1+x2来说,前面已经说过,x表示砝码,x的指数表示重量,即这里就是一个质量为2的砝码,那么前面的1表示什么?1代表重量为2的砝码数量为0个。(理解!)
不知道大家理解没,我们这里结合前面那句话:
"把组合问题的加法法则和幂级数的t的乘幂的相加对应起来"
1+x2表示了两种情况:1表示质量为2的砝码取0个的情况,x2表示质量为2的砝码取1个的情况。
这里说下各项系数的意义:
在x前面的系数a表示相应质量的砝码取a个,而1就表示相应砝码取0个,这里可不能简单的认为相应砝码取0个就该是0*x2(想下为何?结合数学式子)。
Tanky Woo的程序人生:http://www.wutianqi.com/
所以,前面说的那句话的意义大家可以理解了吧?
几种砝码的组合可以称重的情况,可以用以上几个函数的乘积表示:
(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。
接着上面,接下来是第二种情况:
求用1分、2分、3分的邮票贴出不同数值的方案数:
大家把这种情况和第一种比较有何区别?第一种每种是一个,而这里每种是无限的。
以展开后的x4为例,其系数为4,即4拆分成1、2、3之和的拆分数为4;
即:4=1+1+1+1=1+1+2=1+3=2+2
这里再引出两个概念整数拆分和拆分数:
所谓整数拆分即把整数分解成若干整数的和(相当于把n个无区别的球放到n个无标志的盒子,盒子允许空,也允许放多于一个球)。
整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。
现在以上面的第二种情况每种种类个数无限为例,给出模板:
模板
关于什么是母函数,以及在现实生活中的应用,请大家详看或者HDU母函数PPT:
http://www.cppblog.com/MiYu/archive/2010/08/05/122290.html
对于给出的母函数模板,让人理解起来比较费劲的!以下给出几种解释,和自己理解
//madebysyx
//time2010年9月11日10:17:27
//母函数例题
/*//整数拆分模板
由于 可以把x^1看成 是重量为1的砝码 对于重量为1的砝码数是无限的 所以就有了式子(1+x^1+x^2+x^3.....)
重量为2的砝码可以组成式子(1+x^2+x^4+x^6+.....)
。。。。。。。
之后各个式子相乘 则x^n前的系数便是方案数
注意这里的每种砝码数量是无限的 当是有限的时候就要做下限值了 具体看埋葬的其它文章
#include<iostream>
usingnamespacestd;
constintlmax=10000;
//c1是用来存放展开式的系数的,而c2则是用来计算时保存的,
//他是用下标来控制每一项的位置,比如c2[3]就是x^3的系数。
//用c1保存,然后在计算时用c2来保存变化的值。
intc1[lmax+1],c2[lmax+1];
intmain()
{
intn,i,j,k;
//计算的方法还是模拟手动运算,一个括号一个括号的计算,
//从前往后
while(cin>>n)
{
//对于1+x+x^2+x^3+他们所有的系数都是1
//而c2全部被初始化为0是因为以后要用到c2[i]+=x;
for(i=0;i<=n;i++)
{
c1[i]=1;//蓝色字体表示埋葬个人理解的第一次运行的意义
c2[i]=0;//第一次运行表示出第一个式子的各项系数放进c1
}
//第一层循环是一共有n个小括号,而刚才已经算过一个了
//所以是从2到n
for(i=2;i<=n;i++)//第一个式子表示完毕从第二个式子开始乘一共有n个括号
{
//第二层循环是把每一个小括号里面的每一项,都要与前一个
//小括号里面的每一项计算。
for(j=0;j<=n;j++)//j是控制的第一个式子中的每一项(即前一个式子)
//第三层小括号是要控制每一项里面X增加的比例
//这就是为什么要用k+=i;
for(k=0;k+j<=n;k+=i)//k是控制第二个式子中的系数(后一个式子)
{//而且要保持次数不会超过n因为最多分解为x的
//n次方即表示1个质量为n的砝码
//合并同类项,他们的系数要加在一起,所以是加法,呵呵。
//刚开始看的时候就卡在这里了。
c2[j+k]+=c1[j];//把乘的的结果即系数的变化放进c2
}
//刷新一下数据,继续下一次计算,就是下一个括号里面的每一项。
for(j=0;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
cout<<c1[n]<<endl;
}
return0;
}
这句c2[j+k]+=c1[j];的理解还要自己好好的体会体会啊!
*/
自己理解:对于(#式)(1+x+x^2+x^3+x^4+x^5+....)*(1+x^2+x^4+x^6+x^8+x^10+....)*(1+x^3+x^6+x^9+x^12....).....
第一个for给c1和c2赋值,把上面#式的第一个括号(1+x+x^2+x^3+x^4+x^5+....)的系数给放在c1中,
从而再次计算从#的第二个括号开始,所以i就是代表的#式第几个括号,
而用程序模拟手工计算,就是先计算第一个括号与第二个括号计算,把结果放到c2中,
在把结果与第三个括号计算,把结果放到c2中,在和第四个括号计算,........
所以j就是指的已经计算出的各项的系数,比如第一次之后1+x+x^2+x^3+x^4+x^5+...,j=0指向1,
j=2指向x,....,而k就是指将要计算的那个括号中的项,因为第i个括号,中的指数为0,i,2i....所以k要+i;
而结果c2[j+k]+=c1[j];就是把以计算出的j项的系数和现在正在计算的括号的k项相乘,所以指数为j+k,所以结果放到c2[j+k]中,这就是这几个for的作用!
最后刷新下结果,下一组数据计算!
埋葬个人的理解
对于(#式)(1+x+x^2+x^3+x^4+x^5+....)*(1+x^2+x^4+x^6+x^8+x^10+....)*(1+x^3+x^6+x^9+x^12....).....
1第一个for给c1和c2赋值,把上面#式的第一个括号(1+x+x^2+x^3+x^4+x^5+....)的系数给放在c1中,
从而再次计算从#的第二个括号开始,
所以i就是代表的#式第几个括号
2j即第i个式子中的第j项
3而k就是指将要计算的那个括号中的项,因为第i个括号x中的指数为0,i,2i....所以k要+i;
4c2[j+k]+=c1[j];
c2[j]c1[j]是指即次数为j的系数;
c1是用来存放展开式的系数的而c2则是用来计算时保存的
这里指c1[j]乘以k之后次数也变成了j+k,故c2[j+k]的系数要增加c1[j]个;
5n是砝码的个数
新例题:hdu1085用125的硬币买不到的东西的价值(输出最小的)3者数量分别为num1num2num3
#include"stdio.h"
intc1[10000],c2[10000];
intmain()
{
inti,j,k,num1,num2,num3,n;
while(scanf("%d%d%d",&num1,&num2,&num3)!=EOF)
{
if(!num1&&!num2&&!num3)break;
n=num3*5+num2*2+num1;
for(i=0;i<=n;i++)
{
c1[i]=0;
c2[i]=0;
}
for(i=0;i<=num1;i++)
c1[i]=1;
for(j=0;j<=num1;j++)
//for(k=0;k+j<=num2*2;k=k+2)//num2*2表示最多可能达到的次数
for(k=0;k<=num2*2;k=k+2)//num2*2表示最多可能达到的次数
{//注意这里不要用k+j<=num2因为以前求整数拆分输入数n要保证次数小于n因为最大为
//x的n次方表示为1个重为n的砝码这里是求多项式相乘不用限制了
c2[j+k]+=c1[j];
}
for(j=0;j<=num2*2+num1;j++)//因为下面的c2[j]中的下标最大为j+k由上一步可以看出而j最大为num1k最大为num2*2
{
c1[j]=c2[j];
c2[j]=0;
}
for(j=0;j<=num2*2+num1;j++)//num1和num2*2不一定那个大那要表示出所有的项数所以要这样
for(k=0;k<=num3*5;k+=5)
c2[j+k]+=c1[j];
for(j=0;j<=num3*5+num2*2+num1;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
for(i=0;i<=n;i++)
if(!c1[i]){printf("%d\n",i);break;}
if(i==n+1)printf("%d\n",i);
}
}
说白了就是求多项式的值
分享到:
相关推荐
母函数(Generating function)详解
此文档不完整,请下载另外一份。 谢谢大家支持我。
母函数可用于解决整数划分、邮票问题等经典问题。本资料提供深入研究母函数的论文。 基于母函数的递推数列求解方法.pdf 基于母函数的若干离散型计数问题的解法研究.pdf 用母函数求解图的生成树问题.pdf 等等
1.“把组合问题的加法法则和幂级数的乘幂对应起来” 2.“母函数的思想很简单 — 就是把离散数列和幂级数一 一对应起来,把离散数列间的相互结合关系对 1.x的系
学习资料
这个matlab文件是通过计算均值和协方差矩阵的多变量高斯概率密度函数
Generating Functionology
Generating Artifacts问题三种解决办法
adv Generating a Map Application源码
adv Generating a Map Application 题目
Tom Copeland - Generating Parsers with JavaCC-Centennial Books (2009)
Generating Random Networks and Graphs By 作者: Ton Coolen – Alessia Annibale – Ekaterina Roberts ISBN-10 书号: 0198709897 ISBN-13 书号: 9780198709893 Edition 版本: 1 出版日期: 2017-05-23 pages 页数...
Episode-Based Prototype Generating Network for Zero-Shot Learning.pdf
In this paper, we analyze the disadvantage of common generating test paper algorithms, an improved Particle Swarm Optimization is proposed and used in Auto-generating Test Paper Algorithm. We design ...
WC Yeh-universal generating MPs
Herbert S. Wilf Department of Mathematics University of Pennsylvania Philadelphia, Pennsylvania
加权网络上消息传递的生成函数定向键渗流与SIR流行病_Generating functions for message-passing on weighted networks directed bond percolation and SIR epidemics.pdf
Generating Word Reports _ Documentssrc1
关于泊松点过程的生成方法-Generating Homogeneous Poisson Processes - PDF.pdf 在百度上看很多人问平面内泊松点怎么生成,以前我也迷茫的很久,刚好今天找到一个很有用的方法,分享给大家! Report1_...