Witam,
Mam takie zadanie.
Mamy wyraz długości n składający się jedynie z '+' i '-' (np "+++--"). Ile różnych wyrazów o długości n mozną ułożyć z '+' i '-' z takim zastrzerzeniem, że '-' może być maksymalnie m pod rząd (m<=113).
Przykład:
dla
n=3 i m=2
odpowiedzią jest 7:
--+
-+-
-++
+--
+-+
++-
+++
Proszę o jakieś sugestie jak rozwiązać ten problem bez wypisywania kolejnych wyrazów.
Ilość różnych wyrazów o długości n z zastrzeżeniem
- amdfanatyk
- Użytkownik
- Posty: 98
- Rejestracja: 27 mar 2005, o 14:59
- Płeć: Mężczyzna
- Lokalizacja: /dev/zero
- Podziękował: 9 razy
- Pomógł: 7 razy
Ilość różnych wyrazów o długości n z zastrzeżeniem
ja bym to robil tak (ale zastrzegam sobie prawo do pomylki!)
wariacji z powtorzeniami jes 2^n
ilosc sposobow na jakie mozna wybrac sposrod n m powtorzen - wynosi ( (n - m + 1) po (m) ) czyli kombinacja z powtorzeniami
czyli:
2^n - ( (n - m + 1) po (m) )
dla n=3 i m=2 mamy:
2^3 - ( (3 - 2 + 1) po (2) ) = 8 - 1 = 7
ale sprawdz to sobie dla innych wariantow m i n !!
[ Dodano: Wto Kwi 12, 2005 6:33 pm ]
tylko slowko maksymalnie w tresci zadania mnie martwi a nie chce mi sie teraz nad tym myslec na to rozw wpadlem w ok 30 sek
wariacji z powtorzeniami jes 2^n
ilosc sposobow na jakie mozna wybrac sposrod n m powtorzen - wynosi ( (n - m + 1) po (m) ) czyli kombinacja z powtorzeniami
czyli:
2^n - ( (n - m + 1) po (m) )
dla n=3 i m=2 mamy:
2^3 - ( (3 - 2 + 1) po (2) ) = 8 - 1 = 7
ale sprawdz to sobie dla innych wariantow m i n !!
[ Dodano: Wto Kwi 12, 2005 6:33 pm ]
tylko slowko maksymalnie w tresci zadania mnie martwi a nie chce mi sie teraz nad tym myslec na to rozw wpadlem w ok 30 sek
Ilość różnych wyrazów o długości n z zastrzeżeniem
dzięki za odpowiedź.
Niestety, nie jest to prawidłowe, np dla:
n=2 i m=1
wedle wzoru wychodzi nam 2, prawidłową odpowiedzią jest 3:
-+
+-
++
Może jakieś inne pomysły?
Niestety, nie jest to prawidłowe, np dla:
n=2 i m=1
wedle wzoru wychodzi nam 2, prawidłową odpowiedzią jest 3:
-+
+-
++
Może jakieś inne pomysły?
- amdfanatyk
- Użytkownik
- Posty: 98
- Rejestracja: 27 mar 2005, o 14:59
- Płeć: Mężczyzna
- Lokalizacja: /dev/zero
- Podziękował: 9 razy
- Pomógł: 7 razy
Ilość różnych wyrazów o długości n z zastrzeżeniem
no to chyba sie tego nie zrobi prosto jesli wogole w samym 2^n jest juz uklad z samymi - wiec trza by odjac 1; jak dla mnie to potrzebna jest informacja ile jest + lub - bo warunek ze max ma byc m to troche zbyt malo bo nie wiem sposrod ilu - mam wybierac te uklady po m a powinno sie wybierac sposrod nich od m do 0 kombinacji to zsumowac i odjac od 2^n - 1; sam wymysliles to zadanie czy co?!
Ilość różnych wyrazów o długości n z zastrzeżeniem
Nie, jest ono związane z problem z jednego zadania z OI.
[ Dodano: Czw Kwi 14, 2005 3:23 pm ]
Pomyślałem, że możnaby np robić to w ten sposób:
mieć dwa zbiory, K i L.
Zbiór K zawierałby jeden element: +, a zbiór L zawierałby elementy składające się z samych minusów o długości 1,...,m.
Tzn na początku byłoby tak:
K: {+}, L: {-}
później:
K: {+}, L:{-,--}
...
i za każdym razem je jakoś permutować (oczywiście za każdym razm odpowiednio krótszy ciąg). Problem pojawia się wtedy jeśli dwa elementy ze zbioru L będą koło siebie. Może ktoś wie jak pójść dalej tym tropem?
[ Dodano: Czw Kwi 14, 2005 3:23 pm ]
Pomyślałem, że możnaby np robić to w ten sposób:
mieć dwa zbiory, K i L.
Zbiór K zawierałby jeden element: +, a zbiór L zawierałby elementy składające się z samych minusów o długości 1,...,m.
Tzn na początku byłoby tak:
K: {+}, L: {-}
później:
K: {+}, L:{-,--}
...
i za każdym razem je jakoś permutować (oczywiście za każdym razm odpowiednio krótszy ciąg). Problem pojawia się wtedy jeśli dwa elementy ze zbioru L będą koło siebie. Może ktoś wie jak pójść dalej tym tropem?
- amdfanatyk
- Użytkownik
- Posty: 98
- Rejestracja: 27 mar 2005, o 14:59
- Płeć: Mężczyzna
- Lokalizacja: /dev/zero
- Podziękował: 9 razy
- Pomógł: 7 razy
Ilość różnych wyrazów o długości n z zastrzeżeniem
a nie prosciej zobaczyc odpowiedzi do zadan z tej O? jesli chodzi o tego rodzaju konkursy to zadania sa takie, ze np z mat to jakby inna matematyka (glownie Sierpinskiego) niz ta, ktorej ucza w szkole; zadania z olimpiady matematycznej to sa dobre ale zeby sobie pocwiczyc konstruowanie algorytmow i ich implementowanie; przedstawilem problem z + i - nauczycielowi ale na szybka jesli wogole odpowiedz nie licze - jutro koniec klasy i za chwile matura
Ilość różnych wyrazów o długości n z zastrzeżeniem
dzięki,
Co do odpowiedzi. Oczywiście, że mogę zajrzeć ale najpierw, chciałbym samemu rozwiązać ten problem, a dopiero później zobaczyć jakie jest rozwiązanie wzorcowe.
Co do odpowiedzi. Oczywiście, że mogę zajrzeć ale najpierw, chciałbym samemu rozwiązać ten problem, a dopiero później zobaczyć jakie jest rozwiązanie wzorcowe.