注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

母函数的思维 主要的思想 以及模板代码 常见的问题  

2014-04-16 21:24:49|  分类: 母函数 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

若令a1=a2=
=an=1,在(8-1)式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献,其他各项以此类推。故有

母函数的思维  主要的思想  以及模板代码  常见的问题 - 983433479 - jet sky

对于序列a0,a1,a2构造一函数

母函数的思维  主要的思想  以及模板代码  常见的问题 - 983433479 - jet sky


称函数G(x)是序列a0,a1,a2的母函数



(1+x)n是序列C(n,0),C(n,1),...,C(n,n)的母函数。 

    
如若已知序列a0,a1,a2则对应的母函数G(x)便可根据定义给出。



  反之,如若已经求得序列的母函数G(x),则该序列也随之确定。     
序列a0,a1,a2可记为{an}
例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分的邮票贴出不同数值的方案数—— 
n因邮票允许重复,故母函数为:母函数的思维  主要的思想  以及模板代码  常见的问题 - 983433479 - jet sky
 


以展开后的x4为例,其系数为4,即4拆分成1、2、3之和的拆分数为4

 :4=1+1+1+1=1+1+2=1+3=2+2

概念:整数拆分

所谓整数拆分即把整数分解成若干整数的(相当于把n个无区别的球放到n个无标志的盒子,盒子允许空,也允许放多于一个球)。


整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。

例3:若有1克砝码3枚、2克砝码4枚、4克砝码2枚,问能称出哪几种重量?各有几种方案? 

1+x1+x2+x3)(1+x2+x4+x6)(1+x4+x8)

例4:
整数n拆分成1,2,3,
,m

(1+x1+x2+x3….)(1+x2+x4+..)(1+x3+x6+…)(….)

例5:如若上例中m至少出现一次,其母函数又如何最后的变为多少啊

(1+x1+x2+..)(1+x2+x4+x6…)(….)(xm+x(m*2)…);





核心问题——如何编写程序

实现母函数的应用呢?


关键:对多项式展开

首先思考:如果让你手工计算,你是怎样处理的?


第一项和第二项进行展开;展开的在和和为一项后在和别的进行合并后展开;

#include <iostream>
using namespace std;
const int lmax=10000;
int c1[lmax+1],c2[lmax+1];
nt main()
{
int n,i,j,k;
while (cin>>n)//n个数;
{
for (i=0;i<=n;i++)
{
c1[i]=0; c2[i]=0;
}
for (i=0;i<=n;i++) c1[i]=1;
for (i=2;i<=n;i++)//有多少的垮号啊?
{
for (j=0;j<=n;j++)//第一个垮号的第一项
for (k=0;k+j<=n;k+=i)第二个垮号的某项
{
c2[j+k]+=c1[j];
}//储存两个垮号的结果,细数只有一而已;
for (j=0;j<=n;j++)//把他还给我们的第一个垮号啊!
{
c1[j]=c2[j]; c2[j]=0;
}
}
cout<<c1[n]<<endl;
}
return 0;
}



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017