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

suma de numeros impares c++

Question

Diga S = 5 y N = 3 las soluciones se verían como - <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, se pueden usar N bucles anidados para resolver el problema. Ejecute un bucle anidado N, dentro de ellos verifique 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, mira si los números obtenidos suman S.

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

Answer 1

Esto realmente se parece mucho a un problema de Towers of Hanoi, sin la limitación de apilar discos solo 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 2

Esto se puede calcular en O(s+n) (o O(1) si no le importa una aproximación ) de la siguiente manera:

Imagina que tenemos una cadena con n-1 X''s y s ''s. Entonces para su ejemplo de s = 5, n = 3, una cadena de ejemplo sería

oXooXoo

Observe que las X dividen las o en tres grupos distintos: uno de longitud 1, longitud 2 y longitud 2. Esto 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 para s o''s, por lo que la respuesta es Choose(s+n-1, s) .

Answer 3

Hay una fórmula de formulario cerrado: binomial (s + n - 1, n)

Esos números son los números símplex .

Si desea calcularlos, use 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 4

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)

Answer 5

Prueba 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 usar la programación dinámica, puede almacenar en caché el valor de f después de evaluarlo y verificar si el valor ya existe en la memoria caché antes de evaluarlo.

Answer 6

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.

Intentemos.

• Si 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. Vamos a verificar 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 maneras de agregar números que serán 15.

(Nota: los anexos solo son números positivos).

(Puede probar otros números para verificar si nuestra fórmula es correcta o no).