拆分null母函数及其应用
“拆分”母函数及其应用
“拆分”研究以下等式:研究以下等式: 可以看出:
x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元素a1,a2, …an中取两个组合的全体;同理x3项系数包含了从n个元素a1,a2, …an中取3个元素组合的全体。以此类推。 null
若令a1=a2= …=an=1,在(2-1-1)式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献,其他各项以此类推。故有:母函数定义:母函数定义:对于序列a0,a1,a2,…构造一函数:
称...
null母函数及其应用
“拆分”母函数及其应用
“拆分”研究以下等式:研究以下等式: 可以看出:
x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元素a1,a2, …an中取两个组合的全体;同理x3项系数包含了从n个元素a1,a2, …an中取3个元素组合的全体。以此类推。 null
若令a1=a2= …=an=1,在(2-1-1)式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献,其他各项以此类推。故有:母函数定义:母函数定义:对于序列a0,a1,a2,…构造一函数:
称函数G(x)是序列a0,a1,a2,…的母函数 For example: For example: (1+x)n是序列C(n,0),C(n,1),...,C(n,n)的母函数。 如若已知序列a0,a1,a2,…则对应的母函数G(x)便可根据定义给出。
反之,如若已经求得序列的母函数G(x),则该序列也随之确定。 序列a0,a1,a2,…可记为{an} 。 例一、若有1克、2克、3克、4克的砝码各一 枚,能称出哪几种重量?各有几种可能
? 例一、若有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 例二、求用1分、2分、3分的邮票贴出不同数值的方案数。 例二、求用1分、2分、3分的邮票贴出不同数值的方案数。 因邮票允许重复,故母函数为
以展开后的x4为例,其系数为4,即4拆分成1、2、3之和的拆分数为4,即 :
4=1+1+1+1=1+1+2=1+3=2+2概念:整数拆分 概念:整数拆分 所谓整数拆分即把整数分解成若干整数的和,相当于把n个无区别的球放到n个无标志的盒子,盒子允许空着,也允许放多于一个球。整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。 如n=5
n=5
n=4+1
n=3+2=3+1+1
n=2+2+1=2+1+1+1
n=1+1+1+1+1 拆分数: 7 练习:练习:例3:若有1克砝码3枚、2克砝码4枚、4克砝码2枚,问能称出哪几种重量?各有几种方案?
例4: 整数n拆分成1,2,3,…,m的和,求其母函数。如若其中m至少出现一次,其母函数又如何?
请自己写出以上两个问题的母函数。如何编写程序
实现母函数的应用呢?
关键:对多项式展开如何编写程序
实现母函数的应用呢?
关键:对多项式展开以整数拆分为例:以整数拆分为例:观察以下的母函数:
给定一个整数n,要找出n能拆分成多少种不同的若干个数的和与乘积的形式。比如:
4=4 12=1*12
4=1+3 12=2*6
4=2+2 12=3*4
4=1+1+2 12=2*2*3
4=1+1+1+1
4的加分拆分数位5,乘法拆分数位4给定一个整数n,要找出n能拆分成多少种不同的若干个数的和与乘积的形式。比如:
4=4 12=1*12
4=1+3 12=2*6
4=2+2 12=3*4
4=1+1+2 12=2*2*3
4=1+1+1+1
4的加分拆分数位5,乘法拆分数位4#include
using namespace std;
const int lmax=10000;
int c1[lmax+1],c2[lmax+1];
int main()
{int n,i,j,k;
while (cin>>n)
{
for (i=0;i<=n;i++)
{ 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<
using namespace std;
const int lmax=10000;
int c1[lmax+1],c2[lmax+1];
int main()
{int n,i,j,k;
while (cin>>n)
{
for (i=0;i<=n;i++)
{ 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<规划问题的最有子结构性质。 整数乘法拆分数整数乘法拆分数#include
using namespace std;
const int MAXN = 200000;
int dp[MAXN+1];
int main(){
int i,j,n;
for(dp[1]=1,i=2;i<=MAXN;i++)
for(j=1;i*j<=MAXN;j++)
dp[i*j]+=dp[j];
while(cin>>n) cout<m
拆分成n1=m,n1<=m-1
q(n,m)=q(n,n) n
int dp(int n,int m)
{
if(m<1 || n<1)
return 0;
if(m==1 || n==1)
return 1;
if(n
int dp(int n,int m)
{
if(m<1 || n<1)
return 0;
if(m==1 || n==1)
return 1;
if(n
using namespace std;
const int lmax=300;
int c1[lmax+1],c2[lmax+1];
int main(void)
{ int n,i,j,k;
while (cin>>n && n!=0)
{ for (i=0;i<=n;i++)
{ c1[i]=1; c2[i]=0; }
for (i=2;i<=17;i++)
{ for (j=0;j<=n;j++)
for (k=0;k+j<=n;k+=i*i)
{ c2[j+k]+=c1[j]; }
for (j=0;j<=n;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
cout<>n && n!=0)
{ for (i=0;i<=n;i++)
{ c1[i]=1; c2[i]=0; }
for (i=2; i<=17; i++)
{ for (j=0;j<=n;j++)
for (k=0;k+j<=n; k+=elem[i-1] )
{ c2[j+k]+=c1[j]; }
for (j=0;j<=n;j++)
{ c1[j]=c2[j]; c2[j]=0; }
}
cout<
本文档为【拆分】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。