Witajcie.
Mam oto takie dwa zadanka do których nie wiem wogóle jak podejść:
Zadanie 1. Niech \(\displaystyle{ \sum=\left\{ a,b\right\}}\), \(\displaystyle{ A_{n}}\) będzie zbiorem słów słownika \(\displaystyle{ \sum*}\)niezawierających kolejnych liter \(\displaystyle{ a}\), a \(\displaystyle{ s_{n}}\) - liczbą słów długości \(\displaystyle{ n}\), w których nie występują kolejno dwie litery \(\displaystyle{ a}\), tzn. nie zawierają ciągu \(\displaystyle{ aa}\). Wyznaczyć wzór rekurencyjny na \(\displaystyle{ s_{n}}\).
Zadanie 2. Niech \(\displaystyle{ \sum=\left\{ a,b,c \right\}}\), \(\displaystyle{ A_{n}}\) będzie zbiorem słów słownika \(\displaystyle{ \sum*}\) w których występuje parzysta liczba liter \(\displaystyle{ a}\), a \(\displaystyle{ s_{n}}\) - liczbą słów długości \(\displaystyle{ n}\), ze zbioru \(\displaystyle{ A_{n}}\). Wyznaczyć wzór rekurencyjny na \(\displaystyle{ s_{n}}\).
Jakieś wskazówki jak zacząć?
Wzory rekurencyjne.
-
norwimaj
- Użytkownik
- Posty: 5091
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Wzory rekurencyjne.
Do pierwszego mam rozwiązanie dość pokrętne, ale skuteczne. Każde takie słowo może się kończyć na \(\displaystyle{ a}\) albo na \(\displaystyle{ b}\). Czyli możemy sobie zdefiniować nowe ciągi \(\displaystyle{ a_n}\) i \(\displaystyle{ b_n}\), takie że \(\displaystyle{ a_n+b_n=s_n}\). Dla tych ciągów układamy równania rekurencyjne
\(\displaystyle{ a_n=b_{n-1},\quad\quad b_n=a_{n-1}+b_{n-1}}\).
Z nich można otrzymać równania
\(\displaystyle{ a_n=b_{n-1}=a_{n-2}+b_{n-2}=a_{n-2}+a_{n-1}}\),
\(\displaystyle{ b_n=a_{n-1}+b{n-1}=b_{n-2}+b_{n-1}}\),
które po dodaniu stronami dają równanie rekurencyjne na \(\displaystyle{ s_n}\).
Drugie zadanie jest dużo łatwiejsze. Jeśli \(\displaystyle{ s_n}\) jest liczbą słów długości \(\displaystyle{ n}\) o parzystej liczbie liter \(\displaystyle{ a}\), to liczba słów długości \(\displaystyle{ n}\) o nieparzystej liczbie liter \(\displaystyle{ a}\) jest równa \(\displaystyle{ 3^n-s_n}\).
\(\displaystyle{ a_n=b_{n-1},\quad\quad b_n=a_{n-1}+b_{n-1}}\).
Z nich można otrzymać równania
\(\displaystyle{ a_n=b_{n-1}=a_{n-2}+b_{n-2}=a_{n-2}+a_{n-1}}\),
\(\displaystyle{ b_n=a_{n-1}+b{n-1}=b_{n-2}+b_{n-1}}\),
które po dodaniu stronami dają równanie rekurencyjne na \(\displaystyle{ s_n}\).
Drugie zadanie jest dużo łatwiejsze. Jeśli \(\displaystyle{ s_n}\) jest liczbą słów długości \(\displaystyle{ n}\) o parzystej liczbie liter \(\displaystyle{ a}\), to liczba słów długości \(\displaystyle{ n}\) o nieparzystej liczbie liter \(\displaystyle{ a}\) jest równa \(\displaystyle{ 3^n-s_n}\).