Maneiras de criar um número com soma de uns e dois

Question

Estou me perguntando se existe uma maneira de contar as maneiras possíveis de somar um número usando apenas uns e dois

Por exemplo:

Temos o número 10. O número 10 pode ser somado 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...

Obrigado a todos antecipadamente!

Answer 1

Se a ordem dos elementos não importa, como explicam os comentários (ou seja, 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2é idêntica a 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), basta escolher o número de elementos no somatório, que pode estar em qualquer lugar entre 5 a 10. Assim que o número de elementos for escolhido, você saiba exatamente quantos deles têm que ser 1s e quantos deles têm que ser 2s: Para x elementos, existem 10-x 2s e o resto são 1s.

Como existem 6 números para escolher, este é o número de maneiras de criar 10.

Answer 2

Em vez de entrar em fórmulas matemáticas complexas, eu recomendaria a abordagem 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

Número de maneiras de criar um número usando apenas uns = 1
Número de maneiras de criar um número usando pelo menos um dois = floor(n/2)
Total =1 + floor(n/2)

Veja o javascriptsnippet de código abaixo:

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