作业帮解m个自然数中取n个数的总和为a的组合数(a,m,n属于正整数)比如：m=100,n=20,a=1000,求其组合数是多少,不需要具体的组合.
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 21:46:09
解m个自然数中取n个数的总和为a的组合数(a,m,n属于正整数)比如：m=100,n=20,a=1000,求其组合数是多少,不需要具体的组合.
解m个自然数中取n个数的总和为a的组合数(a,m,n属于正整数)
比如：m=100,n=20,a=1000,求其组合数是多少,不需要具体的组合.
解m个自然数中取n个数的总和为a的组合数(a,m,n属于正整数)比如：m=100,n=20,a=1000,求其组合数是多少,不需要具体的组合.
可以用编程递归的方法做,想要求出一个关于m,n,a的表达式实在太难了吧.
设答案为f(m,n,a),那么这些情况中分成两类,取了1和没取1的情况
先看没取1的情况,假设存在一种2到m中找了n个数使得和为a的情况,我们把每个2到m的数都-1,那这些数的和就减少了n因为一共取了n个数.那么这个情况就化为了1到m-1个数里取n个,使得和为a-n.那么一共就有f(m-1,n,a-n）这样的情况（根据f的定义）
然后看取了1的情况,我们在2到m里取了剩下的n-1个数,使得和为a-1,那么同理这些情况的数量等同于在1到m-1的数里取n-1个数使得和为（a-1)-(n-1)=a-n,根据定义就等于f(m-1,n-1,a-n).
那么这个问题就变成了找一个f使得
f(m,n,a)=f(m-1,n,a-n)+f(m-1,n-1,a-n)
然后就可以根据递归的思想求出具体的函数值了,设定初始条件为
f(0或负数,*,*) = f(*,0或负数,*)=f(*,*,0或负数)=0,*是通配符.
那这个递归是会终结的,因为f的三个变量都是递减的,第一个和第三个变量是严格递减总有一部会打到0或者负数,f的值就求出来了.
楼上有位大神啊。
我先留个名，再慢慢想想。 ^.^
这m个数是1,2,3，。。m,还是给定的m个数？可重复取吗？
以下是假定这m个数是1,2,3，。。。m,且可重复取
(x+x^2+..x^m)^n 展开后 x^a前的系数即为所求
若这m个数是给定的就把次数换成给定的m个数即可
不可重复暂时没想出简单做法m个数是1,2,3......m个自然数 从中取n个不重复的数 求这n个数的总和为a的组合个数？...
全部展开
这m个数是1,2,3，。。m,还是给定的m个数？可重复取吗？
以下是假定这m个数是1,2,3，。。。m,且可重复取
(x+x^2+..x^m)^n 展开后 x^a前的系数即为所求
若这m个数是给定的就把次数换成给定的m个数即可
不可重复暂时没想出简单做法
收起
楼上的方法正确，只是代码方面有错误。但是这个递归函数运行起来效率很差。就楼主给的例子，基本上算不出来吧。C++如此，Maple就更算不出来了。建议再改进一下。