c++ - 求和特定数字以获得 100 的不同方法

Question

我想写一段代码来显示有多少种方法可以将 5 个不同的数字相加得到 100。例如，数字是 2,5,10,20,50，它们可以重复任意次数。这里 50+50 是一种方式，20+20+20+20+20。我不知道如何对此进行编程。

我认为它应该通过一个递归函数来完成，我已经尝试编写一个但实际上不知道如何编写，所以这是我想出的最好的:

#include<iostream>
#include<vector>

using namespace std;


int i,sum,n=5,counter=0;


int add(vector<int> &m){

    if(m.size()==0) return 0 ;

    for(i=0 ; i<m.size() ; i++ ){

          sum=m[i]+add(m);
          cout<< sum<<endl;
        if(n>0) n--;
        m.resize(n);
    }


}


int _tmain(int argc, _TCHAR* argv[])
{
    int i,sum,n=5;

vector<int> m;

m.resize(5);

m[0]=2;
m[1]=5;
m[2]=10;
m[3]=20;
m[4]=50;

add(m);


    return 0;
}

Answer 1

这个问题理论上可以用generating functions来解决.生成函数不是函数，它不生成任何东西(好名字，嗯？)，但它确实很好地跟踪信息。结果是你的问题的答案是路数等于 x^100 在

的展开中的系数

1/(1-x^2) * 1/(1-x^5) * 1/(1-x^10) * 1/(1-x^20) * 1/(1-x^50) 

这是关于原因的解释。回想一下 1/(1-x) = 1 + x + x^2 + x^3 + ...。这是我们要用来解决问题的基本生成函数。

假设您有数字 A、B、...、N(在您的示例中，它们是 2、5、10、20、50)，您可以重复任意次数。然后考虑(生成)函数

f(x) = 1/(1-x^A) * 1/(1-x^B) * ... * 1/(1-x^N)

f(x) 中x^M 的系数是将M 写成M 形式之和的方法数

M = a*A + b*B + ... + n*N

其中 a,b,...,n 是非负整数。

为什么这样做？因为展开 f(x) 中的任何单项式项都来自 1/(1-x^A ) 对于一些非负的 a 看起来像 x^(a*A)，对于其他项也类似。由于指数相加，x^M的系数就是这样的和的所有写法，得到M。

我知道这不是编程答案，但希望您可以使用这个想法编写程序。