Ile jest ciągów n - wyrazowych o wyrazach ze zbioru \(\displaystyle{ \{ 1, 2, 3, 4, 5\}}\) takich, że dwie parzyste liczby nie mogą stać obok siebie? Znajdź zależność rekurencyjną.
Na razie znalazłam tylko \(\displaystyle{ a_0 =0, a_1 = 5, a_2 = 21}\), tworzenie kolejnych ciągów polega na dodaniu do już istniejących jednej liczby na końcu - parzystej lub nieparzystej, w zależności od tego, co w danym ciągu się znajduje. Jak to jednak wykorzystać do rekurencji? Będę wdzięczna za pomoc
ciągi n-wyrazowe - rekurencja
- niebieska_biedronka
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
-
- 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
ciągi n-wyrazowe - rekurencja
\(\displaystyle{ \begin{cases} a_0 = 1 \\ a_1 = 5\\ a_n=3a_{n-1}+6a_{n-2}\end{cases}}\)
Ciągi długości \(\displaystyle{ n}\) dzielimy na dwa typy - zakończone liczbą parzystą (wtedy przedostania liczba musi być nieparzysta, a reszta dowolnie) lub nieparzystą (wtedy reszta dowolnie). Spróbuj sama dopracować szczegóły.
Q.
Ciągi długości \(\displaystyle{ n}\) dzielimy na dwa typy - zakończone liczbą parzystą (wtedy przedostania liczba musi być nieparzysta, a reszta dowolnie) lub nieparzystą (wtedy reszta dowolnie). Spróbuj sama dopracować szczegóły.
Q.
- niebieska_biedronka
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
ciągi n-wyrazowe - rekurencja
Dlaczego \(\displaystyle{ a_0 = 1}\)?
Wiem, jak taki ciąg stworzyć, ale nadal nie wiem, skąd ten wzór... Jeśli ciąg kończy się liczbą parzystą, to możemy do niego dostawić 3 znaki, czyli z każdego takiego ciągu powstają 3 nowe; ale jeśli kończy się nieparzystą, to możemy dostawić 5. Nie widzę jednak związku ze wzorem
Wiem, jak taki ciąg stworzyć, ale nadal nie wiem, skąd ten wzór... Jeśli ciąg kończy się liczbą parzystą, to możemy do niego dostawić 3 znaki, czyli z każdego takiego ciągu powstają 3 nowe; ale jeśli kończy się nieparzystą, to możemy dostawić 5. Nie widzę jednak związku ze wzorem
-
- 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
ciągi n-wyrazowe - rekurencja
Bo istnieje tylko jedna idąca do podanego zbioru.niebieska_biedronka pisze:Dlaczego \(\displaystyle{ a_0 = 1}\)?
Ale my nic nie dostawiamy.możemy do niego dostawić
W takich zadaniach rozumowanie idzie w drugą stronę - rozważamy zbiór ciągów \(\displaystyle{ n}\)-wyrazowych i dzielimy je na takie, które kończą się liczbą parzystą i takie które kończą się liczbą nieparzystą. I następnie badamy co w takim razie może się znajdować na \(\displaystyle{ n-1}\) pierwszych miejscach ciągu.
Przykładowo, jeśli ciąg \(\displaystyle{ n}\) wyrazowy kończy się dwójką, to przedostatnia cyfra może być tylko jedynką, trójką lub piątką. A wtedy na \(\displaystyle{ n-2}\) pierwszych miejscach może być dowolny ciąg spełniający warunki zadania - a tych jest oczywiście \(\displaystyle{ a_{n-2}}\). Stąd wniosek, że żądanych ciągów o długości \(\displaystyle{ n}\) kończących się dwójką jest \(\displaystyle{ 3\cdot a_{n-2}}\).
Q.
- niebieska_biedronka
- Użytkownik
- Posty: 397
- Rejestracja: 8 paź 2011, o 15:31
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 96 razy
- Pomógł: 19 razy
ciągi n-wyrazowe - rekurencja
... a ponieważ sytuacja, kiedy mamy czwórkę zamiast dwójki jest analogiczna, dlatego we wzorze mamy 6, tak?
Zupełnie inaczej patrzyłam na to zadanie. Bardzo dziękuję za pomoc
Zupełnie inaczej patrzyłam na to zadanie. Bardzo dziękuję za pomoc