普通型母函数和指数型母函数

2024-02-19 14:38
文章标签 函数 指数 型母 普通型

本文主要是介绍普通型母函数和指数型母函数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

母函数:摘自百度百科

生成函数即母函数,是组合数学中尤其是计数方面的一个重要理论和工具。生成函数有普通型生成函数和指数型生成函数两种,其中普通型用的比较多。形式上说,普通型生成函数用于解决多重集的组合问题,而指数型母函数用于解决多重集的排列问题。母函数还可以解决递归数列的通项问题(例如使用母函数解决斐波那契数列的通项公式)

理解:

什么是普通母函数呢,——把组合问题的加法法则和幂级数的的乘幂的相加对应起来,这句话可能一开始难以理解,不过其实学完了之后很容易理解,母函数的思想很简单—就是把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造。

 

        母函数分为:普通型母函数指数型母函数

        普通型母函数主要是来求组合的方案数,而指数型母函数是求多重排列数

普通母函数:

定义

若函数G(x)=a0+a1*x+a2*x^2+……+an*x^n,则称函数G(x)为序列a0、a1、a2、……an的母函数。

 

例如:(1+x)^n=1+C(n,1)*x+C(n,2)*x^2+……+C(n,n)*x^n 就是序列 C(n,1)、C(n,2)、……、C(n,n)的母函数,其中C(n,m)为组合数。

 

经典例题

有质量为1,2,4的砝码分别为1,3,2枚,问:

1.可以称出多少种不同的质量?

2.要称出质量为3的物品,有几种可能的方式?

 

则可以构造函数G(x) = (1+x)*(1+x^2+x^4+x^6)*(1+x^4+x^8),其中第一个括号中的1表示质量为1的砝码用了0枚,x表示质量为1的砝码用了1枚;第二个括号中的1表示质量为2的砝码用了0枚,x^2为质量为2的砝码用了1枚,x^4表示质量为2的砝码用了2枚,也就是x^(2*2),x^6表示质量为2的砝码用了3枚,也就是x^(2*3)。先不必理解为什么这样做,只需要知道怎样做。

 

总结一下,每个括号就表示一种砝码的使用情况。x^n就表示质量为n的砝码用了1枚。最少可以使用0枚,也就是式子里面的1。最多可以使用m枚,也就是x^(n*m)。

 

知道了对应关系,那么代码应该怎么写呢?其实也简单,就是模拟手动计算以上多项式相乘的过程。比如上面的

G(x) = (1+x)*(1+x^2+x^4+x^6)*(1+x^4+x^8)

= (1+x^2+x^4+x^6  + x+x^3+x^5+x^7)*(1+x^4+x^8)

= (1+x+x^2+x^3+x^4+x^5+x^6+x^7)*(1+x^4+x^8)

= (1+x+x^2+x^3+x^4+x^5+x^6+x^7  +  x^4+x^5+x^6+x^7+x^8+x^9+x^10+x^11  +  x^8+x^9+x^10+x^11+x^12+x^13+x^14+x^15)

=1+x+x^2+x^3+2*x^4+2*x^5+2*x^6+2*x^7+2*x^8+2*x^9+2*x^10+2*x^11+x^12+x^13+x^14+x^15

 

以上过程也就是不断的计算前 i 个多项式相乘的结果。最后得到的式子中 m*x^n 就表示可以有m种方式称出质量为n的物品。一共有x~x^15个不同的质量,也就是最多能称出15中不同质量的物品


#define MAXN 55int a[MAXN],b[MAXN];int s[MAXN],e[MAXN],v[MAXN];void mu(int n){ //n为因子个数 int i,j,k;memset(a,0,sizeof(a));a[0]=1;for(i=1;i<=n;i++){ //前i项相乘 memset(b,0,sizeof(b));//j为第i种物品可能的数量,j*v[i]即第i个括号中第j项的系数for(j=s[i];j<=e[i]&&j*v[i]<=MAXN;j++)for(k=0;k+j*v[i]<=MAXN;k++) //计算对前i-1项相乘的结果的第k项的系数产生的影响 b[k+j*v[i]]+=a[k];memcpy(a,b,sizeof(b)); //将b数组存回a数组 }	}

以上代码中MAXN为结果可能生成的x的指数的最大值。

a数组存储最终结果,b数组存储中间结果
s[i] (start数组)为第i个变量的最小个数,一般都为0,e[i] (end数组)为第i个变量的最大个数
v[i]表示第i个未知量的取值,即x^v[i]
a[i]存储的是未知量 x^i 前面的系数

 

也就是a存储前i-1项的相乘结果,然后遍历第i项中的每一个变量,让其与a中的每一项相乘,将结果临时存储到b数组中,最后存回a数组。

 

例如:求不同个数的不同质量的砝码可以组成的质量为 i 的种类数
v[i]存第i种砝码质量,s[i]存第i种砝码最小的个数,e[i]存第i种砝码最大的个数,a[i]存可以组成的质量为i的种类数、

指数函数:

模板:https://blog.csdn.net/SunPeishuai/article/details/81412049

参考:https://blog.csdn.net/agoniangel/article/details/51899372

          https://blog.csdn.net/zuzhiang/article/details/77948274

这篇关于普通型母函数和指数型母函数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/724987

相关文章

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域(Local)2.2 闭包作用域(Enclos

MySQL count()聚合函数详解

《MySQLcount()聚合函数详解》MySQL中的COUNT()函数,它是SQL中最常用的聚合函数之一,用于计算表中符合特定条件的行数,本文给大家介绍MySQLcount()聚合函数,感兴趣的朋... 目录核心功能语法形式重要特性与行为如何选择使用哪种形式?总结深入剖析一下 mysql 中的 COUNT

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典(dict)类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例:安全访问未知键三、案例:配置参数默认值简介python是一种高级编

python 常见数学公式函数使用详解(最新推荐)

《python常见数学公式函数使用详解(最新推荐)》文章介绍了Python的数学计算工具,涵盖内置函数、math/cmath标准库及numpy/scipy/sympy第三方库,支持从基础算术到复杂数... 目录python 数学公式与函数大全1. 基本数学运算1.1 算术运算1.2 分数与小数2. 数学函数

Python中help()和dir()函数的使用

《Python中help()和dir()函数的使用》我们经常需要查看某个对象(如模块、类、函数等)的属性和方法,Python提供了两个内置函数help()和dir(),它们可以帮助我们快速了解代... 目录1. 引言2. help() 函数2.1 作用2.2 使用方法2.3 示例(1) 查看内置函数的帮助(

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五