Chủ đề này có 1 trả lời

[betty]

Gọi $S_n$ là số lượng xâu nhị phân có có độ nài $n$ trong đó tồn tại ít nhất 1 xâu con $01$. Tìm hệ thức truy hồi của $S_n$.

 

[Nobodyv3]

Gọi $S_n$ là số lượng xâu nhị phân có có độ nài $n$ trong đó tồn tại ít nhất 1 xâu con $01$. Tìm hệ thức truy hồi của $S_n$.

Các xâu thỏa đề bài chỉ có 2 dạng:
- xA: với A là xâu thỏa đề bài dài n-1 bít, do x có thể là 0 hoặc 1 $\rightarrow$ số xâu dạng này là $2S_{n-1}$.
- 01B: với B là xâu dài n-2, không chứa xâu con 01$\rightarrow$ số xâu dạng này là $2^{n-2}-S_{n-2}$.
Vậy ta có HTTH:
$S_{n}=2S_{n-1}-S_{n-2}+2^{n-2}$, giá trị khởi tạo $ S_{1}=0, S_{2}=1 $.
Nhận xét : các xâu không thỏa đề bài phải có dạng 111....000, nên $S_{n}=2^{n}-(n+1)$.