Witam,
Mam dane stałą N, czyli ograniczenie zbioru A : 0..N.
Następnie mam daną jakąś liczbę X.
I teraz jest pytanie, ile jest wariacji o długości H, zaczynających się na dowolną liczbę różną od zera, takich że suma elementów w tej wariacji jest równa X.
Czyli inaczej można to sformuować : ile można skonstruować (multi)zbiorów ze zbioru A, takich że każdy (multi)zbiór sumuje się do wartości X.
Dla przykładu \(\displaystyle{ A \left\{0,1,2,3 \right\}}\)
Szukamy \(\displaystyle{ X=3 \wedge H=4}\)
możliwe ułożenia
1110
1011
1101
1200
1020
1002
3000
Mam nadzieję, że niczego nie zgubiłem
Edit: Wpadłem na prostsze wyjaśnienie problemu. Na ile sposobów można wybrać H elementów ( elementy mogą się powtarzać ) ze zbioru A, aby ich suma była równa X( tutaj chyba gubimy założenie że pierwszy element nie może być zerem )?
Jak się zabrać za takie zadanie ?
Pozdrawiam.
Liczba wariacji zbioru 0..N
-
- Użytkownik
- Posty: 147
- Rejestracja: 14 cze 2011, o 16:36
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 28 razy
Liczba wariacji zbioru 0..N
Jeśli dobrze rozumiem to brakuje Ci paru opcji w rozpatrywanym przypadku: \(\displaystyle{ 2100, 2010, 2001}\).
Pytanie wydaje się bardzo trudne w ogólnym przypadku, ale chyba warto zacząć od tego, że \(\displaystyle{ 0}\)-a możesz traktować jako "zapychacze" tych wariacji i przejść do rozpatrywania wariacji zbioru \(\displaystyle{ 1,2,...,N}\). To pokazuje złożoność problemu.
Pytanie wydaje się bardzo trudne w ogólnym przypadku, ale chyba warto zacząć od tego, że \(\displaystyle{ 0}\)-a możesz traktować jako "zapychacze" tych wariacji i przejść do rozpatrywania wariacji zbioru \(\displaystyle{ 1,2,...,N}\). To pokazuje złożoność problemu.