Sposoby tworzenia liczby z sumą jedynek i dwójek

Aug 16 2020

Zastanawiam się, czy jest sposób, aby policzyć możliwe sposoby zsumowania liczby, używając tylko jedynek i dwójek

Na przykład:

Mamy liczbę 10. Liczbę 10 można podsumować wzorem:

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

Z góry dziękuję!

Odpowiedzi

1 amit Aug 17 2020 at 03:22

Jeśli kolejność elementów nie ma znaczenia, jak wyjaśniają komentarze (tj. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2Jest identyczna 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), jest to po prostu wybór liczby elementów w sumowaniu, która może wynosić od 5 do 10. Po wybraniu liczby elementów Wiedz dokładnie, ile z nich musi być 1, a ile z nich 2: Dla x elementów jest 10 x 2, a reszta to 1.

Ponieważ do wyboru jest 6 liczb, jest to liczba sposobów tworzenia 10.

another_CS_guy Aug 17 2020 at 05:36

Zamiast wdawać się w złożone wzory matematyczne, poleciłbym podejście 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

Liczba sposobów utworzenia liczby przy użyciu tylko jedynek = 1
Liczba sposobów utworzenia liczby przy użyciu co najmniej jednego z dwóch = floor(n/2)
Suma =1 + floor(n/2)

Zobacz javascriptfragment kodu poniżej:

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