Способы создания числа с помощью суммы единиц и двоек

Question

Мне интересно, есть ли способ подсчитать возможные способы суммирования числа, используя только единицы и двойки

Например:

У нас есть число 10. Число 10 можно суммировать следующим образом:

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

Спасибо всем заранее!

Answer 1

Если порядок элементов не имеет значения, как поясняется в комментариях (т.е. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2идентичен 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), это просто выбор количества элементов в суммировании, которое может быть от 5 до 10. После выбора количества элементов вы точно знать, сколько из них должно быть единиц и сколько из них должно быть двоек: для x элементов есть 10-x 2, а остальные - 1.

Так как есть 6 чисел на выбор, это количество способов создать 10.

Answer 2

Вместо того, чтобы вдаваться в сложные математические формулы, я бы рекомендовал подход 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

Количество способов создать число, используя только единицы = 1
Количество способов создать число, используя хотя бы одну двойку = floor(n/2)
Всего =1 + floor(n/2)

См. javascriptФрагмент кода ниже:

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