Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Zdravím, chtěl bych se zeptat, zda byste nevěděli jak řešit tuto úlohu. Děkuji.
Nechť Sn je počet binárních řetězců délky n ∈ N+ , které neobsahují podřetězec 01.
Odvoďte vhodný rekurentní vztah pro posloupnost Sn.
Offline
Téma už je zřejmě dávno "mrtvé", jen mě teď napadlo, že k rekurentnímu vztahu lze jednoduše dojít výpisem řetězců délky n = 1, 2, 3, ..., které podřetězec "01" neobsahují:
n Sn výpis ---------------------------------------------------- 1 2 0 1 2 3 00 10 11 3 4 000 100 110 111 4 5 0000 1000 1100 1110 1111 5 6 00000 10000 11000 11100 11110 11111 . . .
Řekl bych, že ostatní neuvedené řetězce dané délky podřetězec "01" nutně obsahují.
Takže rekurentní vztah by zřejmě mohl být
Nebo se pletu?
Offline
↑ Jj:podľa mňa ok, ale chcelo by to odvodenie napríklad by samohli "dobré" reťazce rozdeliť na tie čo končia nulou (nech ich je ) a na tie čo končia jednotkou (nech ich je )
Zrejme
Nulou môžeme rozšíriť každý "dobrý" reťazec a jednotkou len ten čo končí jednotkou preto
[mathjax]\begin{align}S_{0,n+1} &= S_{0,n}+S_{1,n}\\
S_{1,n+1} &= S_{1,n}
\end{align}[/mathjax]
Z dostávame
sčítaním a dostávame
Offline
Stránky: 1