专栏首页magicsoar母函数及相关的算法题

母函数及相关的算法题

母函数即生成函数,构造这么一个多项式函数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 = 1;
    coin[0].number = 3;

    coin[1].value = 2;
    coin[1].number = 2;

    coin[2].value = 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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 初识nginx——配置解析篇

    一、nginx的介绍     nginx是由俄罗斯人开发的一款高性能的http和反向代理服务器,也可以用来作为邮件代理。相比较于其他的服务器,具有占用内存少,稳...

    magicsoar
  • Nginx平滑升级源码分析

    一、平滑升级步骤 1、重命名之前的sbin/nginx文件,将新的nginx文件放到sbin/目录下 #mv ./sbin/nginx ./sbin/nginx...

    magicsoar
  • 微信储存数据的分析

    iphone上微信聊天记录的储存分析 由于隐私的原因,这里不能将自己的聊天记录奉献出来 设备:越狱后的iphone5 ios7.0.4            微...

    magicsoar
  • 13,Matplotlib面向对象绘图

    Matplotlib是Python数据分析中用于数据可视化的最著名的一个库,其绘图方式和matlab中的绘图方式非常相似。

    lyhue1991
  • Java位操作

         无论说是在哪一门计算机语言,位操作运算对于计算机来说肯定是最高效的,因为计算机的底层是按就是二进制,而位操作就是为了节省开销,加快程序的执行速度,以及...

    lwen
  • 一文理清 Go 引用的常见疑惑

    之所以要谈它,一方面是之前的我也有些概念混乱,想梳理下,另一方面是因为很多人对引用都有疑问。我经常会看到与引用有关的问题。

    波罗学
  • Web前端学习 第3章 JavaScript基础教程5 循环语句

    条件语句的代码可以被想象成是一条条分支的路径,而循环语句的代码则是程序路径的一个回路,可以让一部分代码重复执行。JavaScript中的循环语句有for语句和w...

    学习猿地
  • 【融职培训】Web前端学习 第3章 JavaScript基础教程5 循环语句

    条件语句的代码可以被想象成是一条条分支的路径,而循环语句的代码则是程序路径的一个回路,可以让一部分代码重复执行。JavaScript中的循环语句有for语句和w...

    学习猿地
  • 理解python函数的参数访问方式

    在《简书》上看到了一个讨论python函数参数传递的文章,仔细读了几遍,有些不是很明白的地方,于是有了此文,欢迎阅读讨论,如有错误,也欢迎指正:

    干点啥吧
  • ELK学习笔记之ELK6.0 X-pack设置用户名和密码

    Jetpropelledsnake21

扫码关注云+社区

领取腾讯云代金券