Matematické Fórum

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
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 20. 01. 2018 17:18

PierreLaplace
Zelenáč
Příspěvky: 18
Škola: SPŠ MOST
Pozice: student
Reputace:   
 

Odvození rekurentního vztahu pro posloupnost

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

 

#2 21. 03. 2018 17:38

Jj
Příspěvky: 6920
Škola: VŠB, absolv. r. 1970
Pozice: Důchodce
Reputace:   506 
 

Re: Odvození rekurentního vztahu pro posloupnost

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í:

Code:

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 $S_{n+1}=S_n+1,\;   S_1=2$

Nebo se pletu?


Pokud se tedy nemýlím.

Offline

 

#3 21. 03. 2018 19:30

jarrro
Příspěvky: 4859
Škola: UMB BB Matematická analýza
Reputace:   276 
Web
 

Re: Odvození rekurentního vztahu pro posloupnost

↑ 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 $S_{0,n}$) a na tie čo končia jednotkou (nech ich je $S_{1,n}$)
Zrejme $S_{0,1}=1, S_{1,1}=1$
Nulou môžeme rozšíriť každý "dobrý" reťazec a jednotkou len ten čo končí jednotkou preto
$$$\parstyle
\begin{align}S_{0,n+1} &= S_{0,n}+S_{1,n}\\
S_{1,n+1} &= S_{1,n}
\end{align}$$$
Z $\(2\)$dostávame
$S_{1,n}=1$
sčítaním $\(1\)$ a $\(2\)$ dostávame
$S_{n+1}=S_{0_n+1}+S_{1,n+1}=S_{0,n}+S_{1,n}+S_{1,n}=S_n+1$


MATH IS THE BEST!!!

Offline

 

#4 21. 03. 2018 19:34

Jj
Příspěvky: 6920
Škola: VŠB, absolv. r. 1970
Pozice: Důchodce
Reputace:   506 
 

Re: Odvození rekurentního vztahu pro posloupnost

↑ jarrro:

Díky.


Pokud se tedy nemýlím.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson