Mam 2 zadanka z rekurencji z którymi nie moge sobie poradzić...
z1. Niech \(\displaystyle{ \sum =\{a,b\}}\), \(\displaystyle{ A_{n}}\) będzie zbiorem słów słownika \(\displaystyle{ \sum \frac{}{}^*}\) niezawierających kolejnych liter a, a \(\displaystyle{ S_{n}}\) - liczbą
słów długości n, w których nie występują kolejno dwie litery a, tzn. nie zawierają ciągu aa.
Wyznaczyć wzór rekurencyjny na \(\displaystyle{ S_{n}}\)
z2. Przypuscmy, ze pewien prymitywny organizm osiaga dojrzałosc po dwóch godzinach od urodzenia i ma wtedy pierwszych czterech potomków, a nastepnie co godzine ma szesciu kolejnych potomków. Zakładajac, ze wszystkie urodzone organizmy zachowuja sie tak samo oraz ze rozpoczelismy z jednym nowo urodzonym organizmem, obliczyc ilosc organizmów po upływie n godzin od momentu urodzenia pierwszego z nich.
Rekurencja - trudne
Rekurencja - trudne
Ostatnio zmieniony 15 sty 2011, o 21:59 przez Crizz, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Nawiasy klamrowe to w LaTeXu '\{', '\}'.
Powód: Poprawa wiadomości. Nawiasy klamrowe to w LaTeXu '\{', '\}'.
-
Crizz
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Rekurencja - trudne
Nie wiem, czy dobrze rozumiem: mamy do dyspozycji dwie litery \(\displaystyle{ a,b}\) i układamy z nich n-elementowe ciągi, w których nie ma dwóch liter \(\displaystyle{ a}\) obok siebie. \(\displaystyle{ A_n}\) jest zbiorem wszystkich takich ciągów, a \(\displaystyle{ S_n}\) liczbą elementów \(\displaystyle{ A_n}\)?
Jeśli to się zgadza, to zastanów się, jak z \(\displaystyle{ A_{n-1}}\) (i ewentualnie \(\displaystyle{ A_{n-2},A_{n-3},...}\)) stworzyć \(\displaystyle{ A_n}\).
Bierzemy \(\displaystyle{ A_{n-1}}\) i możemy utworzyć wszystkie możliwe słowa ze zbioru \(\displaystyle{ A_n}\) w wyniku czterech operacji:
do każdego z elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na początku \(\displaystyle{ b}\)
do każdego z elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na końcu \(\displaystyle{ b}\)
do elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na początku \(\displaystyle{ a}\) (ale tylko do tych, które nie miały na początku \(\displaystyle{ a}\), bo utworzy się \(\displaystyle{ aa}\))
do elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na końcu \(\displaystyle{ a}\) (ale tylko do tych, które nie miały na końcu \(\displaystyle{ a}\), bo utworzy się \(\displaystyle{ aa}\))
Z pierwszych dwóch operacji wynika, że \(\displaystyle{ S_{n}=2S_{n-1}+...}\). Wartość \(\displaystyle{ ...}\) zależy od tego, ile elementów w zbiorze \(\displaystyle{ A_{n-1}}\) nie ma na początku \(\displaystyle{ a}\) oraz ile elementów w tym zbiorze nie ma na końcu \(\displaystyle{ a}\).
"nie ma na początku a" oznacza "ma na początku b", podobnie będzie z "nie ma na końcu a". Co możemy "dokleić" do \(\displaystyle{ b}\), zeby dostać zbiór wszystkich elementów \(\displaystyle{ A_n}\), które nie mają na początku \(\displaystyle{ a}\)?
Jeśli to się zgadza, to zastanów się, jak z \(\displaystyle{ A_{n-1}}\) (i ewentualnie \(\displaystyle{ A_{n-2},A_{n-3},...}\)) stworzyć \(\displaystyle{ A_n}\).
Bierzemy \(\displaystyle{ A_{n-1}}\) i możemy utworzyć wszystkie możliwe słowa ze zbioru \(\displaystyle{ A_n}\) w wyniku czterech operacji:
do każdego z elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na początku \(\displaystyle{ b}\)
do każdego z elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na końcu \(\displaystyle{ b}\)
do elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na początku \(\displaystyle{ a}\) (ale tylko do tych, które nie miały na początku \(\displaystyle{ a}\), bo utworzy się \(\displaystyle{ aa}\))
do elementów \(\displaystyle{ A_{n-1}}\) "dokładamy" na końcu \(\displaystyle{ a}\) (ale tylko do tych, które nie miały na końcu \(\displaystyle{ a}\), bo utworzy się \(\displaystyle{ aa}\))
Z pierwszych dwóch operacji wynika, że \(\displaystyle{ S_{n}=2S_{n-1}+...}\). Wartość \(\displaystyle{ ...}\) zależy od tego, ile elementów w zbiorze \(\displaystyle{ A_{n-1}}\) nie ma na początku \(\displaystyle{ a}\) oraz ile elementów w tym zbiorze nie ma na końcu \(\displaystyle{ a}\).
"nie ma na początku a" oznacza "ma na początku b", podobnie będzie z "nie ma na końcu a". Co możemy "dokleić" do \(\displaystyle{ b}\), zeby dostać zbiór wszystkich elementów \(\displaystyle{ A_n}\), które nie mają na początku \(\displaystyle{ a}\)?
-
Crizz
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Rekurencja - trudne
Wskazówka: niech \(\displaystyle{ a_n}\) będzie liczbą organizmów istniejących w danej godzinie. Spróbuj wyrazić \(\displaystyle{ a_n}\) jako sumę:
ilości organizmów, które istniały godzinę wcześniej
potomstwa (z ostatniej godziny) organizmów, które "urodziły się" dokładnie 2 godziny temu
potomstwa (z ostatniej godziny) organizmów, które "urodziły się" wcześniej niż 2 godziny temu
W drugim i trzecim składniku to będzie 6 lub 4 razy różnica odpowiednich wyrazów ciągu.
ilości organizmów, które istniały godzinę wcześniej
potomstwa (z ostatniej godziny) organizmów, które "urodziły się" dokładnie 2 godziny temu
potomstwa (z ostatniej godziny) organizmów, które "urodziły się" wcześniej niż 2 godziny temu
W drugim i trzecim składniku to będzie 6 lub 4 razy różnica odpowiednich wyrazów ciągu.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Rekurencja - trudne
W pierwszym zadaniu dużo prościej zauważyć, że wyrazy długości \(\displaystyle{ n}\) mogą się kończyć tylko na \(\displaystyle{ b}\) lub \(\displaystyle{ ba}\) - tych pierwszego typu jest \(\displaystyle{ S_{n-1}}\), a drugiego typu \(\displaystyle{ S_{n-2}}\), zatem rekurencja to \(\displaystyle{ S_n=S_{n-1}+S_{n-2}}\)
Q.
Q.
Rekurencja - trudne
odpowiedz do zd nr 2 ma być
\(\displaystyle{ a_{n} = (-1)^{n} - \frac{1}{ \sqrt{3} } (1- \sqrt{3})^{n} -\frac{1}{ \sqrt{3} } (1+ \sqrt{3})^{n}}\)
Zrobiłem tabelkę z ilością urodzeń w poszczególnych godzinach:
wycięto obrazek
\(\displaystyle{ P_{n}=4R_{n}+6S_{n}}\)
\(\displaystyle{ Q_{n}=P_{n-1}}\)
\(\displaystyle{ R_{n}=Q_{n-1}}\)
\(\displaystyle{ S_{n}=R_{n-1} + S_{n-1}}\)
\(\displaystyle{ Suma=P_{n}+Q_{n}+R_{n}+S_{n}}\)
\(\displaystyle{ a_{n} = (-1)^{n} - \frac{1}{ \sqrt{3} } (1- \sqrt{3})^{n} -\frac{1}{ \sqrt{3} } (1+ \sqrt{3})^{n}}\)
Zrobiłem tabelkę z ilością urodzeń w poszczególnych godzinach:
wycięto obrazek
\(\displaystyle{ P_{n}=4R_{n}+6S_{n}}\)
\(\displaystyle{ Q_{n}=P_{n-1}}\)
\(\displaystyle{ R_{n}=Q_{n-1}}\)
\(\displaystyle{ S_{n}=R_{n-1} + S_{n-1}}\)
\(\displaystyle{ Suma=P_{n}+Q_{n}+R_{n}+S_{n}}\)
Ostatnio zmieniony 17 sty 2011, o 20:30 przez Qń, łącznie zmieniany 2 razy.
Powód: Zamieszczanie obrazków jest dozwolone wyłącznie w przypadkach, kiedy nie da się zapisać czegoś w LaTeX-u.
Powód: Zamieszczanie obrazków jest dozwolone wyłącznie w przypadkach, kiedy nie da się zapisać czegoś w LaTeX-u.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Rekurencja - trudne
Układ rekurencji który napisałeś jest poprawny, ale prościej znaleźć rekurencję na samą sumę. Jeśli oznaczymy ją przez \(\displaystyle{ S_n}\), to dostajemy:
\(\displaystyle{ S_n=S_{n-1}+4 \cdot (S_{n-2}-S_{n-3}) + 6 \cdot S_{n-3}}\)
Zastanów się dlaczego, a następnie rozwiąż tę rekurencję (np. przy pomocy funkcji tworzących albo wielomianu charakterystycznego).
Q.
\(\displaystyle{ S_n=S_{n-1}+4 \cdot (S_{n-2}-S_{n-3}) + 6 \cdot S_{n-3}}\)
Zastanów się dlaczego, a następnie rozwiąż tę rekurencję (np. przy pomocy funkcji tworzących albo wielomianu charakterystycznego).
Q.