Ilość różnych wyrazów o długości n z zastrzeżeniem

apacz · Post autor: **apacz** » 12 kwie 2005, o 16:20

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.

amdfanatyk · Post autor: **amdfanatyk** » 12 kwie 2005, o 19:18

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

apacz · Post autor: **apacz** » 12 kwie 2005, o 22:22

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?

amdfanatyk · Post autor: **amdfanatyk** » 12 kwie 2005, o 23:05

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?!

apacz · Post autor: **apacz** » 13 kwie 2005, o 21:06

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?

amdfanatyk · Post autor: **amdfanatyk** » 14 kwie 2005, o 18:50

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

apacz · Post autor: **apacz** » 14 kwie 2005, o 21:12

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.