¿Cuántos posibles combinaciones de las variables a, b, c, d, e si sé que:número de posibles combinaciones son posibles
a+b+c+d+e = 500
y que son todos los números enteros y> = 0, por lo que sabe que son finitos.
@ Torlack, @Jason Cohen: La recursividad es una mala idea aquí, porque hay "subproblemas superpuestos". Es decir, si elige a como 1 y b como 2, entonces le quedan 3 variables que deberían sumar hasta 497; usted llega al mismo subproblema seleccionando a como 2 y b como 1. (El número de tales coincidencias aumenta a medida que crecen los números.)
La forma tradicional de atacar un problema de este tipo es dynamic programming: compilar una tabla de abajo a arriba de las soluciones a los sub-problemas (comenzando con "cuántas combinaciones de 1 variable sume hasta 0? ") Y luego compilación a través de la iteración (la solución a" ¿cuántas combinaciones de n variables suman k? "Es la suma de las soluciones a" cuántas combinaciones de n- 1 las variables se suman a j?" con 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
¡Tienes razón, la programación dinámica es la mejor! En mi solución de código anterior, sugiero usar una tabla de pares de caché, pero hay MUCHOS pares, por lo que DP es mejor. Sin embargo, traté de encontrar la solución DP y fue muy difícil para mí. :-) –
En realidad solo suma * pares suma, por lo que no es tan malo en 5 x 500. –
@ Chris Estoy teniendo problemas para entender el significado de los valores en la matriz que construyes en tu solución. ¿Podría darme algún ejemplo? En su matriz [2] [1] = 3 y significa "¿cuántas combinaciones de (2 + 1) vars suman 1? ¿Cuáles son estas combinaciones? (Supongo que como son combinaciones, el orden no importa) –
Si son números reales, entonces infinitos ... de lo contrario, es un poco más complicado.
(OK, para cualquier representación por ordenador de un número real no habría un recuento finita ... pero sería grande!)
Son mayores que 0, así que no es tan grande – Turambar
también declaró números enteros –
Una forma de enfocar el problema es el siguiente:
Primero, a puede ser cualquier valor de 0 a 500. Entonces si sigue eso b + c + d + e = 500-a. Esto reduce el problema en una variable. Repetir hasta que esté hecho.
Por ejemplo, si a es 500, entonces b + c + d + e = 0 lo que significa que para el caso de a = 500, solo hay una combinación de valores para b, c, d y e.
Si a es 300, entonces b + c + d + e = 200, que es de hecho el mismo problema que el problema original, solo reducido por una variable.
Nota: Como Chris señala, esta es una forma horrible de tratar de resolver el problema.
Incluyendo negativos? Infinito.
¿Se incluyen solo aspectos positivos? En este caso, no se llamarían "enteros", sino "naturales". En este caso ... Realmente no puedo resolver esto, desearía poder hacerlo, pero mis matemáticas están demasiado oxidadas. Probablemente exista una forma completamente loca de resolver esto. Puedo dar algunos consejos para los expertos en matemáticas.
siendo x el resultado final, el rango de A sería de 0 a x, el intervalo de b sería de 0 a (x - a), del intervalo de C sería de 0 a (x - a - b), y así sucesivamente hasta el e.
La respuesta es la suma de todas esas posibilidades.
Estoy tratando de encontrar alguna fórmula más directa en Google, pero estoy realmente bajo en mi Google-Fu hoy ...
La respuesta a su pregunta es 2656615626.
Aquí está el código que genera la respuesta:
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;
}
En su caso, es summands 5 y sum es 500.
Tenga en cuenta que este código es lento. Si necesita velocidad, guarde en caché los resultados de summand,sum pares.
Supongo que quiere los números >=0. Si desea >0, reemplace la inicialización de bucle con a = 1 y la condición de bucle con a < sum. También estoy asumiendo que quieres permutaciones (p.1+2+3+4+5 plus 2+1+3+4+5 etc.). Podría cambiar el for-loop si quisiera a >= b >= c >= d >= e.
He resuelto este problema para mi padre hace un par de meses ... extienda para su uso. Estos tienden a ser un problemas de tiempo, así que no voy por la mayor parte reutilizable ...
a + b + c + d = suma
i = número de combinaciones
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++
}
}
}
realidad, esto sería una buena pregunta para preguntar en una entrevista, ya que es bastante simple que se podría escribir en una pizarra blanca, pero lo suficientemente compleja que podría tropezar con él si ellos don' Pienso cuidadosamente sobre eso. Además, también puede elegir entre dos respuestas diferentes que hacen que la implementación sea bastante diferente.
El orden es importante
Si las cuestiones de orden entonces cualquier solución debe permitir cero a aparecer para ninguna de las variables; por lo tanto, la solución más directa sería la siguiente:
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);
}
}
que devuelve 2656615626.
orden no importa
Si el orden no importa entonces la solución no es mucho más difícil a medida solo necesita asegurarse de que cero no sea posible a menos que ya se haya encontrado la suma.
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);
}
}
que devuelve 2573155876.
Tiene fórmulas generales, si
a + b + c + d = N
Luego número de solución integral no negativo será C(N + number_of_variable - 1, N)
@ La respuesta de Chris Conway es correcta. He probado con un código simple que es adecuado para sumas más pequeñas.
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);
¡La respuesta en matemáticas es 504!/(500! * 4!).
Formalmente, para x1 + x2 + ... xk = n, el número de combinación del número no negativo x1, ... xk es el coeficiente binomial: (k-1) -combinación de un conjunto que contiene (n + k-1) elementos.
La intuición consiste en elegir (k-1) puntos de (n + k-1) puntos y usar el número de puntos entre dos puntos elegidos para representar un número en x1, .. xk.
Disculpa por la pobre edición matemática de mi primera vez que respondí Stack Overflow.
Just a test for code block
Just a test for code block
Just a test for code block
Esa es una linda cosa que pensar. – jjnguy
¿Es esta una pregunta de tarea? –
No, un compañero de trabajo me preguntó al respecto porque estudié un poco de Probabilidad, pero no pude resolverlo – Turambar