Formas de crear un número con la suma de unos y de dos

Aug 16 2020

Me pregunto si hay una manera de contar las posibles formas de sumar un número usando solo unos y dos

Por ejemplo:

Tenemos el número 10. El número 10 se puede sumar por:

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1  
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2
2 + 2 + 2 + 2 + 2 
etc...

¡Gracias a todos de antemano!

Respuestas

1 amit Aug 17 2020 at 03:22

Si el orden de los elementos no importa, como explican los comentarios ( 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2es decir, es idéntico a 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), esto es simplemente elegir el número de elementos en la suma, que puede estar entre 5 y 10. Una vez que se elige el número de elementos, saber exactamente cuántos de ellos tienen que ser 1 y cuántos de ellos tienen que ser 2: Para los elementos x, hay 10-x 2 y el resto son 1.

Dado que hay 6 números para elegir, este es el número de formas de crear 10.

another_CS_guy Aug 17 2020 at 05:36

En lugar de entrar en fórmulas matemáticas complejas, recomendaría el enfoque de DP.


    int arr[N+1]; // Represents no. of ways to produce a number at index 1
    // Like arr[5] is no. of ways to produce number 5
    
    for(int i=0;i<=N;i++) {
      arr[i] = 1; // As all 1s
    }
    
    for(int i=2;i<=N;i++) {
      // if we add 2 now, check for no. of ways i-2 can be made, 
      // add it to current arr[i] value.
      arr[i] += arr[i-2];
    }
    
    cout<< (arr[N]); // print

RahulBhobe Aug 17 2020 at 18:07

Número de formas de crear un número utilizando solo unos = 1
Número de formas de crear un número utilizando al menos uno dos = floor(n/2)
Total =1 + floor(n/2)

Vea el javascriptfragmento de código a continuación:

let numWays = n => 1 + Math.floor(n/2);

for (let i=1; i<=20; i++)
    console.log("Number of ways to create " + i + " is: " + numWays(i));