Strona 1 z 2
Rekurencja jednorodna, niejednorodna
: 8 lip 2023, o 14:06
autor: hutsalo
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:
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.
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.
Re: Rekurencja jednorodna, niejednorodna
: 8 lip 2023, o 14:35
autor: a4karo
To pomyśl co w interesującej wiadomośći może wystapić po zerze a co po jedynce
Re: Rekurencja jednorodna, niejednorodna
: 8 lip 2023, o 16:03
autor: hutsalo
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?
Re: Rekurencja jednorodna, niejednorodna
: 8 lip 2023, o 23:03
autor: a4karo
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
Re: Rekurencja jednorodna, niejednorodna
: 11 lip 2023, o 16:44
autor: hutsalo
a4karo pisze: ↑8 lip 2023, o 23:04
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ą
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.
Re: Rekurencja jednorodna, niejednorodna
: 11 lip 2023, o 19:37
autor: a4karo
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`
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 17:40
autor: hutsalo
a4karo pisze: ↑11 lip 2023, o 19:37.
Żeby wyznaczysz warunki początkowe wystarczy pomyśleć czym jest `j_1,z_1,d_1`
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?
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 18:15
autor: a4karo
Przeczytaj definicję `j_1`
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 18:23
autor: hutsalo
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?
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 18:36
autor: a4karo
No nie: `j_n` to ilość ciągó o długości `n` zakończonych jedynką. Ile wynosi `n` przy `j_1`?
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 18:46
autor: hutsalo
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
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 18:58
autor: a4karo
Ale ciebie interesuje warunek początkowy, czyli ilość ciągów o długości `1`
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 19:04
autor: hutsalo
No to jeżeli mówimy o ciągach dł. 1 zakończonych jedynką no to jest 1. Nie ma innej cyfry tylko 1.
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 19:09
autor: a4karo
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ę?
Re: Rekurencja jednorodna, niejednorodna
: 13 lip 2023, o 19:16
autor: hutsalo
A jak doszedłeś do tego że wszystkie wyrazy początkowe są równe 1? I ile ich jest?