Número de formas de sumar una suma S con N números

Question

Digamos que S = 5 y N = 3 serían las soluciones - < 0,0,5> < 0,1,4> < 0,2,3 > < 0,3,2> < 5,0,0> < 2,3,0> < 3,2,0> < 1,2,2> etc etc.

En el caso general, N anidados los bucles se pueden usar para resolver el problema. Ejecute bucle anidado N, dentro de ellos compruebe si las variables de bucle se suman a S.

Si no conocemos N con anticipación, podemos usar una solución recursiva. En cada nivel, ejecute un ciclo que comienza de 0 a N, y luego llame a la función de nuevo. Cuando alcanzamos una profundidad de N, verifique si los números obtenidos se suman a S.

¿Alguna otra solución de programación dinámica?

Answer 1

Pruebe esta función recursiva:

f(s, n) = 1         if s = 0 
     = 0         if s != 0 and n = 0 
     = sum f(s - i, n - 1) over i in [0, s] otherwise 

Para utilizar la programación dinámica se puede almacenar en caché el valor de f después de evaluarla, y comprobar si el valor ya existe en la caché antes de su evaluación.

Answer 2

Hay una forma fórmula cerrada: binomial (s + n - 1, n)

Esos números son los números simplex.

Si desea calcularlos, utilice la función de registro gamma o la aritmética de precisión arbitraria.

Ver https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers

Answer 3

En realidad, esto se parece mucho a un problema Torres de Hanoi, sin la limitación de apilamiento de discos sólo en discos más grandes. Tienes discos S que pueden estar en cualquier combinación en N torres. Entonces eso es lo que me hizo pensar sobre eso.

Lo que sospecho es que hay una fórmula que podemos deducir que no requiere la programación recursiva. Aunque necesitaré un poco más de tiempo.

Answer 4

Esto se puede calcular en O(s+n)(o O(1) si no te importa un approximation) de la siguiente manera:

Imaginemos que tenemos una cadena con n-1 X está en él y s o de. Así que para su ejemplo de s = 5, n = 3, una cadena de ejemplo sería

oXooXoo 

en cuenta que las X dividen los o en tres grupos distintos: uno de longitud 1, longitud 2, y la longitud 2. Este corresponde a su solución de < 1,2,2>. Cada cadena posible nos da una solución diferente, al contar el número de o en una fila (un 0 es posible: por ejemplo, XoooooX correspondería a < 0,5,0>). Entonces al contar la cantidad de cadenas posibles de este formulario, obtenemos la respuesta a su pregunta.

Hay s+(n-1) posiciones para elegir s o's, por lo que la respuesta es Choose(s+n-1, s).

Answer 5

Tengo mi propia fórmula para esto. Nosotros, junto con mi amigo Gio, hicimos un informe de investigación sobre esto.La fórmula que obtenemos es [2 raised to (n-1) - 1], donde n es el número que buscamos cuántos sumandos tiene.

Probemos.

• If n es 1: sus sumandos son o. No hay dos o más números que podamos agregar para obtener una suma de 1 (excluyendo 0). Probemos con un número más alto.
• Probemos 4. 4 has addends: 1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 1+3, 2+2, 3+1. Su total es 7. Comprobemos con la fórmula. 2 elevado a (4-1) - 1 = 2 elevado a (3) - 1 = 8-1 = 7.
• Probemos 15. 2 elevado a (15-1) - 1 = 2 elevado a (14) - 1 = 16384 - 1 = 16383. Por lo tanto, hay 16383 formas de agregar números que serán igual a 15.

(Nota: Sumandos son números positivos solamente.)

(puede probar otros números, para comprobar si nuestra fórmula es correcta o no.)

Answer 6

Hay una fórmula fija para encontrar la respuesta . Si desea encontrar el número de formas de obtener N como la suma de los elementos R. La respuesta es siempre: (N + R-1)!/((R-1)! * (N)!) o en otras palabras: (N + R-1) C (R-1)