设为首页 加入收藏

TOP

整数的拆分2
2019-03-19 12:01:56 】 浏览:61
Tags:整数 拆分

方法二——母函数

下面我们从另一个角度,即“母函数”的角度来考虑这个问题。

所谓母函数,即为关于x的一个多项式G(x):

有G(x) = a0 + a1*x + a2*x^2 + a3*x^3 + ......

则我们称G(x)为序列(a0, a1, a2,.....)的母函数。关于母函数的思路我们不做更过分析。

我们从整数划分考虑,假设n的某个划分中,1的出现个数记为a1,2的个数记为a2,.....,i的个数记为ai,

显然有:ak <= n/k(0<= k <=n

因此n的划分数f(n,n),也就是从1到n这n个数字抽取这样的组合,每个数字理论上可以无限重复出现,即个数随意,使它们的综合为n。显然,数字i可以有如下可能,出现0次(即不出现),1次,2次,......,k次等等。把数字i用(x^i)表示,出现k次的数字i用(x^(i*k))表示,不出现用1表示。

例如,数字2用x^2表示,2个2用x^4表示,3个2用x^6表示,k个2用x^2k表示。

则对于从1到N的所有可能组合结果我们可以表示为:

G(x) = ( 1 + x + x^2 + x^3 + ... + x^n)*(1 + x^2 + x^4 + x^6 + ....)....(1 + x^n)

= g(x,1)*g(x,2)*g(x,3)*....*g(x,n)

= a0 + a1*x + a2*x^2 +...+ an*x^n + ....//展开式

上面的表达式中,每个括号内的多项式代表了数字i的参与到划分中的所有可能情况。因此,该多项式展开后,由于x^a *x^b = x^(a+b),因此x^i就代表了i的划分,展开后(x^i)项的系数也就是i的所有划分个数,即f(n,n) = an。

由此我们找到了关于整数划分的母函数G(x);剩下的问题就是,我们需要求出G(x)的展开后的所有系数。

为此,我们首先要做多项式乘法,对于我们来说,并不困难。我们把一个关于x的多项式用一个整数数组a[]表示,a[i]代表x^i的系数,即:

g(x) = a[0] + a[1]x + a[2]x^2 + ... + a[n]x^n;

则关于多项式乘法的代码如下,其中数组a和数组b表示两个要相乘的多项式,结果存储到数组c中。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//母函数法求整数划分

#define MAXNUM 100            //最高次数
unsigned long a[MAXNUM];
unsigned long b[MAXNUM];
unsigned long c[MAXNUM];    //保存结果

//两个多项式进行乘法,系数分别保存在a和b中,结果保存到c,项的最大次数到MAXNUM
void Poly()
{
    int i;
    int j;
    memset(c, 0, sizeof(c));
    for(i = 0; i < MAXNUM; i++)
    {
        for(j = 0; j < MAXNUM - i; j++)    //j < MAXNUM - i,确保i+j不越界
        {
            c[i + j] += a[i] * b[j];
        }
    }
}
//计算前N项的系数,即g(x,1)*g(x,2)*....*g(x,n)的展开结果
void Init(int m)
{
    int i;
    int j;
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
    //第一个多项式:g(x) = x^0 + x^1 + x^2 + ... + x^n
    for(i = 0; i < MAXNUM; i++)
    {
        a[i] = 1;
    }
    //for(j = 2; j <= MAXNUM; j++)//只能求f(n,n)
    //通过修改这里,使得可以求f(n,m),对于任意的正整数n,m都适合
    for(j = 2; j <= m; j++)
    {
        memset(b, 0, sizeof(b));
        //第i个多项式:g(x) = x^0 + x^i + x^(2k) + ...
        for(i = 0; i <= MAXNUM; i += j)
        {
            b[i] = 1;
        }
        //多项式相乘:c = a * b
        Poly();    
        //将结果c保存到a中
        memcpy(a, c, sizeof(c));
    }
}

//母函数方法得出整数划分相应的划分数目
//n:整数
//m:划分方法
void CalPrint(int n, int m)
{
    if(n < m)
    {
        Init(n);
        //由于n小于m,此时按n == m打印
        printf("由于n小于m,所有(%d,%d) = (%d,%d) = %ld\n", n, m, n, n, c[n]);
    }
    else
    {
        
        Init(m);
        printf("整数划分(%d,%d)方法数目f(%d,%d) = %ld\n", n, m, n, m, c[n]);
    }
}

int main(int argc, char **argv)
{
    int n;
    int m;
    printf("请输入要划分的整数:");
    scanf("%d", &n);
    printf("请输入划分数:");
    scanf("%d", &m);
    if(n <= 0) 
    {
        fprintf(stderr, "输入的整数不能为非正数.n");
        return -1;
    }
    if(m <= 0)
    {
        fprintf(stderr, "输入的划分数不能为非正数.n");
        return -1;
    }
    printf("母函数法");
    CalPrint(n,m);
 
    return 0;
}

改进:现在要求整数只能拆分成1,2,4,10,20,40,100,200,400,1000,2000这11个数

母函数法求解整数划分

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//母函数法求整数划分

#define MAXNUM 6001            //最高次数
unsigned long a[MAXNUM];
unsigned long b[MAXNUM];
unsigned long c[MAXNUM];    //保存结果

int d[] = {1,2,4,10,20,40,100,200,400,1000,2000} ;
//两个多项式进行乘法,系数分别保存在a和b中,结果保存到c,项的最大次数到MAXNUM
void Poly()
{
    int i;
    int j;
    memset(c, 0, sizeof(c));
    for(i = 0; i < MAXNUM; i++)
    {
        for(j = 0; j < MAXNUM - i; j++)    //j < MAXNUM - i,确保i+j不越界
        {
            c[i + j] += a[i] * b[j];
        }
    }
}
//计算前N项的系数,即g(x,1)*g(x,2)*....*g(x,n)的展开结果
void Init(int m)
{
    int i;
    int j;
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
    //第一个多项式:g(x) = x^0 + x^1 + x^2 + ... + x^n
    for(i = 0; i < MAXNUM; i++)
    {
        a[i] = 1;
    }
    //for(j = 2; j <= MAXNUM; j++)//只能求f(n,n)
    //通过修改这里,使得可以求f(n,m),对于任意的正整数n,m都适合
    for(j = 1; j <= m; j++)
    {
        memset(b, 0, sizeof(b));
        //第i个多项式:g(x) = x^0 + x^i + x^(2k) + ...
        for(i = 0; i <= MAXNUM; i += d[j])
        {
            b[i] = 1;
        }
        //多项式相乘:c = a * b
        Poly();    
        //将结果c保存到a中
        memcpy(a, c, sizeof(c));
    }
}

int main(int argc, char **argv)
{
    int n;
	int m = 10 ;
    printf("请输入要划分的整数:");
    scanf("%d", &n);
    if(n <= 0) 
    {
        fprintf(stderr, "输入的整数不能为非正数\n");
        return -1;
    }
	Init(m);
	printf("母函数法");
    printf("整数划分(%d)方法数目为%ld\n",n,c[n]);
    return 0;
}


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Condition java1.8 下一篇hdfs命令行客户端的常用操作命令

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目