Nie proszę o pomoc w rozwiązaniu całego zadania, ponieważ umiem rozwiązać rekurencje czy to jednorodną i niejednorodną. Problem tylko polega na tym aby znaleźć warunki początkowe i wzór ogólny.racujesz w firmie kryptograficznej. Odczytujesz zaszyfrowane wiadomości złożone jedynie z cyfr0,1,2. Z pewnego punktu widzeniainteresujące są te wiadomości, w których nie występują konfiguracje00oraz01. Takie wiadomości należą do klasyX. Odpowiedz na pytanie, ilejest różnych wiadomości klasyXzłożonych z czterdziestu znaków? Odpowiedź uzasadnij, przedstawiając stosowne obliczenia.
Rekurencja jednorodna, niejednorodna
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Rekurencja jednorodna, niejednorodna
Dawno o nic nie pytałem na tym forum więc pora o sobie przypomnieć. Mam takie zadanie z dyskretnej, z którym się broczę już trochę, a brzmi ono tak:
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
Skoro nie mogą występować konfiguracje 00 i 01, to jedyne co może wystąpić to 02 i 12. Czy to są jedyne konfiguracje czy może być ich więcej np. 20 i 21?
-
a4karo
- Użytkownik
- Posty: 22233
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3759 razy
Re: Rekurencja jednorodna, niejednorodna
Proponuję utworzyć trzy ciągi:
`z_n` - ilość ciagów o długości `n` zakończonych zerem
`j_n` - ilość ciagów o długości `n` zakończonych jedynką
`d_n` - ilość ciagów o długości `n` zakończonych dwójką
teraz łatwo napiszesz ukłąd trzech równań rekurencyjnych. Ciebie interesuje `s_n=z_n+j_n+d_n`
Dodano po 55 sekundach:
Sorry, trochę zamieszałem z poprzednią wskazówką. Ale nie tak bardzo
`z_n` - ilość ciagów o długości `n` zakończonych zerem
`j_n` - ilość ciagów o długości `n` zakończonych jedynką
`d_n` - ilość ciagów o długości `n` zakończonych dwójką
teraz łatwo napiszesz ukłąd trzech równań rekurencyjnych. Ciebie interesuje `s_n=z_n+j_n+d_n`
Dodano po 55 sekundach:
Sorry, trochę zamieszałem z poprzednią wskazówką. Ale nie tak bardzo
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
Te ciągi to to:
`z_n` - ilość ciagów o długości `n` zakończonych zerem(10, 20, 0)
`j_n` - ilość ciagów o długości `n` zakończonych jedynką(11(nie wiem czy powinno być), 21, 1)
`d_n` - ilość ciagów o długości `n` zakończonych dwójką(12,02,22(nie wiem czy powinno być),2)
i na tej podstawie chciałbym wyznaczyć wyrazy początkowe.
-
a4karo
- Użytkownik
- Posty: 22233
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3759 razy
Re: Rekurencja jednorodna, niejednorodna
Szczerze mówiąc nie wiem jak to, co przez ma się do zadania.
Żeby wyznaczysz warunki początkowe wystarczy pomyśleć czym jest `j_1,z_1,d_1`
Żeby wyznaczysz warunki początkowe wystarczy pomyśleć czym jest `j_1,z_1,d_1`
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
czyli żeby wyznaczyć wyrazy początkowe trzeba utworzyć ciągi, które kończą na 1, na 0 i na 2? Tak jak napisałeś wyżej?
Dodano po 5 minutach 16 sekundach:
Tylko teraz pytanie ile elementowe mogą być te ciągi. Czy to mają być 1-elementowe, 2, 3?
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
ilość ciagów o długości n zakończonych jedynką
1, 11, 21
ciąg o dł. 3 zakończonych jedynką
ilość ciagów o długości n zakończonych zerem
0, 10, 20
ciąg o dł. 3 zakończonych zerem
ilość ciagów o długości n zakończonych dwójką
02, 12, 22
ciąg o dł. 3 zakończonych dwójką
czyli potrzebujemy 3 wyrazów początkowych o dł. 3?
1, 11, 21
ciąg o dł. 3 zakończonych jedynką
ilość ciagów o długości n zakończonych zerem
0, 10, 20
ciąg o dł. 3 zakończonych zerem
ilość ciagów o długości n zakończonych dwójką
02, 12, 22
ciąg o dł. 3 zakończonych dwójką
czyli potrzebujemy 3 wyrazów początkowych o dł. 3?
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
A czemu zapisałeś \(\displaystyle{ j_1}\). \(\displaystyle{ j_1}\) to będzie pojedynczy ciąg czyli 1? Jest to pojedynczy ciąg o dł. 1. Ale może być też podwójny o dł. 2:
\(\displaystyle{ j_2}\): 11, 21
\(\displaystyle{ j_2}\): 11, 21
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
No to jeżeli mówimy o ciągach dł. 1 zakończonych jedynką no to jest 1. Nie ma innej cyfry tylko 1.
-
a4karo
- Użytkownik
- Posty: 22233
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3759 razy
Re: Rekurencja jednorodna, niejednorodna
Nie cyfry, tylko liczby. Tak. Wszystkie wyrazy początkowe są równe `1`.
Teraz musisz rozwiązać ten układ równań rekurencyjnych. Dasz radę?
Teraz musisz rozwiązać ten układ równań rekurencyjnych. Dasz radę?
-
hutsalo
- Użytkownik
- Posty: 143
- Rejestracja: 14 sty 2022, o 19:44
- Płeć: Mężczyzna
- Podziękował: 59 razy
Re: Rekurencja jednorodna, niejednorodna
A jak doszedłeś do tego że wszystkie wyrazy początkowe są równe 1? I ile ich jest?