szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 lut 2018, o 20:45 
Użytkownik

Posty: 52
Lokalizacja: Kraków
Witam, czy mógłby ktoś wyjaśnić mi jak rozwiązywać zadania tego typu jak w temacie. Przykładowo:
ile jest ciągów binarnych długości n, które nie zawierają trzech jedynek na sąsiednich miejscach.
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2018, o 23:38 
Użytkownik
Avatar użytkownika

Posty: 6616
Obawiam się, że zdecydowanie zbyt wiele oczekujesz od krótkiej odpowiedzi.

To zadanie rozwiązywałbym tak:
Niech a_k będzie ilością ciągów o długości k .

Ile może być ciągów długości k?
Na pewno na końcu każdego ciągu k-1 elementowego mogę dopisać 0.
A mogę dopisać 1? Nie, gdyż ciąg k-1 elementowy mógł kończyć się sekwencją 11.
Ale mogę na końcu każdego ciągu k-2 elementowego mogę dopisać 01.
A mogę dopisać 11? Nie, gdyż ciąg k-2 elementowy mógł kończyć się cyfrą 1.
Oznacza to, że ciągi k elementowe kończące się na 11 otrzymam przez dopisanie sekwencji 011 do ciągów k-3 elementowych.
Mam więc ciągi k-elementowe kończące się układami (X-dowolna cyfra) : XX0, X01 i 011, czyli wszystkie dopuszczalne przez treść zadania ciągi.

Sumując powyższe dostaję zależność rekurencyjną:
a_k=a _{k-1}+ a _{k-2}+a _{k-3}
o (wypisanych i zliczonych) warunkach początkowych:
a_1=2 \wedge a_2=4 \wedge a_3=7

Nawet nie zamierzam próbować wyliczać wzoru jawnego tego ciągu.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Znajdź a_n wyraz rozwinięcia dwumianu  Anonymous  1
 Wariacje z powtorzeniami : wzor  hipero  3
 Ile monitorów można wybrać ?? jaki wzor?  Anonymous  1
 [Dyskretna/Kombinacje] Wzór - twierdzenie do udowodnienia  Szczawik  0
 wzór newtona  net  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl