Modi per creare un numero con la somma di uno e due

Question

Mi chiedo se esista un modo per contare i modi possibili per sommare un numero utilizzando solo uno e due

Per esempio:

Abbiamo il numero 10. Il numero 10 può essere riassunto da:

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...

Grazie a tutti in anticipo!

Answer 1

Se l'ordine degli elementi non è importante, come spiegano i commenti (cioè 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2è identico a 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), si tratta semplicemente di scegliere il numero di elementi nella somma, che può essere compreso tra 5 e 10. Una volta scelto il numero di elementi, sapere esattamente quanti devono essere 1 e quanti devono essere 2: per gli elementi x, ci sono 10-x 2 e il resto sono 1.

Poiché ci sono 6 numeri tra cui scegliere, questo è il numero di modi per crearne 10.

Answer 2

Piuttosto che entrare in complesse formule matematiche, consiglierei l'approccio 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

Answer 3

Numero di modi per creare un numero utilizzando solo uno = 1
Numero di modi per creare un numero utilizzando almeno uno due = floor(n/2)
Totale =1 + floor(n/2)

Vedi lo javascriptsnippet di codice di seguito:

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));