https://stackoverflow.com/questions/59743
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
有多少可能的组合变量的a，b，c，d，e是可能的，如果我知道的是：
a+b+c+d+e = 500
他们都整数和>=0,所以我知道他们是有限的。
解决方案
@Torlack,@Jason Cohen:递归是一个糟糕的想法来这里，因为有"重叠子问题." 即， 如果你选择 a 作为 1 和 b 作为 2, 然后你有3个变量左，应当添加到497;你到达的同样子问题的选择 a 作为 2 和 b 作为 1.(数这样的巧合爆炸的数字增长。)
传统的方式攻击这样一个问题是 动态规划:建立一个表下而上的解决方案的子的问题(开始"多少组合的1个变量加起来0?") 然后建立通过迭代(解决"多少组合 n 变量加起来 k?"是的总和的解决方案"多少组合 n-1 变量加起来 j?"0 <= j <= k).
public static long getCombos( int n, int sum ) {
// tab[i][j] is how many combinations of (i+1) vars add up to j
long[][] tab = new long[n][sum+1];
// # of combos of 1 var for any sum is 1
for( int j=0; j < tab[0].length; ++j ) {
tab[0][j] = 1;
}
for( int i=1; i < tab.length; ++i ) {
for( int j=0; j < tab[i].length; ++j ) {
// # combos of (i+1) vars adding up to j is the sum of the #
// of combos of i vars adding up to k, for all 0 <= k <= j
// (choosing i vars forces the choice of the (i+1)st).
tab[i][j] = 0;
for( int k=0; k <= j; ++k ) {
tab[i][j] += tab[i-1][k];
}
}
}
return tab[n-1][sum];
}
$ time java Combos 2656615626 real 0m0.151s user 0m0.120s sys 0m0.012s
其他提示
回答你的问题是2656615626.
这里的代码生成的答案：
public static long getNumCombinations( int summands, int sum )
{
if ( summands <= 1 )
return 1;
long combos = 0;
for ( int a = 0 ; a <= sum ; a++ )
combos += getNumCombinations( summands-1, sum-a );
return combos;
}
在你的情况， summands 是5和 sum 500.
注意，这个代码是缓慢的.如果你需要的速度、高速缓存的结果 summand,sum 对。
我假设你想要数字 >=0.如果你想要的 >0, 更换的环初始化 a = 1 和循环的条件与 a < sum.我还假设你想要的排列组合(例如 1+2+3+4+5 再加上 2+1+3+4+5 等等)。你可以改变对于环如果你想要的 a >= b >= c >= d >= e.
我解决了这个问题对于我的爸爸几个月前...延长。这些往往是一个时间问题，所以我不去多数可重复使用的...
a+b+c+d=总和
i=数量的组合
for (a=0;a<=sum;a++)
{
for (b = 0; b <= (sum - a); b++)
{
for (c = 0; c <= (sum - a - b); c++)
{
//d = sum - a - b - c;
i++
}
}
}
这实际上会是一个很好的问题问上一次访谈，因为它是很简单的，你可以写在白板上，但是复杂的，它可能旅行的人，如果他们不仔细考虑有足够的了解。此外，还可以用于两个不同答案会导致实现是相当不同。
顺序事项
如果订购的事项，则任何解决方案需要允许零出现的任何变量；因此，最直接的解决方案如下：
public class Combos {
public static void main() {
long counter = 0;
for (int a = 0; a <= 500; a++) {
for (int b = 0; b <= (500 - a); b++) {
for (int c = 0; c <= (500 - a - b); c++) {
for (int d = 0; d <= (500 - a - b - c); d++) {
counter++;
}
}
}
}
System.out.println(counter);
}
}
其返回2656615626.
订单并不重要
如果订单并不重要那么解决方案是不是很难的因为你只是需要确保零是不可能的，除非总已经发现。
public class Combos {
public static void main() {
long counter = 0;
for (int a = 1; a <= 500; a++) {
for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
counter++;
}
}
}
}
System.out.println(counter);
}
}
其返回2573155876.
一方式看待问题如下：
第一，可以是任何价值从0至500人。然后，如果下，b+c+d+e=500。这降低了本问题的一个变量。Recurse，直到完成。
例如，如果一个500，则b+c+d+e=0这意味着对于情况的一=500，只有一个组合的价值观对于b、c、d和e中。
如果是300,然后b+c+d+e=200，这实际上是同样的问题，因为原来的问题，只是减少通过一个变量。
注：克里斯指出的，这是一个可怕的方式的实际上试图解决的问题。
如果他们是一个真正的数字，然后无限的...否则，它是一个有点棘手。
(好，对于任何计算机表示的一个真正的数量会有一个有限的数...但是，这将是大！)
它具有一般性公式，如果
a+b+c+d=N
然后量非消极的整体解决方案将是 C(N + number_of_variable - 1, N)
@克里斯*康威的答案是正确的。我已经测试了一个简单的代码，适用于较小的款项。
long counter = 0;
int sum=25;
for (int a = 0; a <= sum; a++) {
for (int b = 0; b <= sum ; b++) {
for (int c = 0; c <= sum; c++) {
for (int d = 0; d <= sum; d++) {
for (int e = 0; e <= sum; e++) {
if ((a+b+c+d+e)==sum) counter=counter+1L;
}
}
}
}
}
System.out.println("counter e "+counter);
答案在数学是504!/(500!*4!).
从形式上看，对于x1+x2+...xk=n、数量结合非负数x1,...xk二项系数：(k-1)-联合出的一套包含(n+k-1)的单元。
直觉是选择(k-1)点(n+k-1)点，并使用的数量点之间的两个选点来表示一个数量在x1,..xk。
对不起有关贫穷的数学版本为我拳头的时间回答堆溢出。
Just a test for code block
Just a test for code block
Just a test for code block
包括底片？无限的。
仅仅包括报?在这种情况下，他们不会被称为"整数"，但是"自然"，而不是。在这种情况下...我真的不能解决这个问题，我希望我可以，但是我的数学是太生锈。有可能是一些疯狂的整体方式来解决这个问题。我可以给予一些指引的数学技能的周围。
正在x最终的结果， 范围就能从0到x， 范围b将从0至(x-a) c的范围内将从0至(x-a-b)， 等等，直到e.
答案是所有这些可能性。
我试图找到一些更直接式上谷歌，但我真的很低谷歌-Fu今天...
