Trả lời:
Đáp án đúng: C
Để giải bài toán này, ta có thể sử dụng phương pháp đệ quy hoặc quy hoạch động. Gọi $a_n$ là số xâu nhị phân độ dài $n$ không chứa hai bit 1 đứng cạnh nhau.
- Với $n = 1$, ta có 2 xâu là "0" và "1", vậy $a_1 = 2$.
- Với $n = 2$, ta có 3 xâu là "00", "01" và "10", vậy $a_2 = 3$.
Ta có thể xây dựng xâu độ dài $n$ từ xâu độ dài $n-1$ và $n-2$ như sau:
- Nếu xâu độ dài $n-1$ kết thúc bằng 0, ta có thể thêm 0 hoặc 1 vào cuối.
- Nếu xâu độ dài $n-1$ kết thúc bằng 1, ta chỉ có thể thêm 0 vào cuối.
Vậy, số xâu độ dài $n$ sẽ bằng số xâu độ dài $n-1$ kết thúc bằng 0 cộng với số xâu độ dài $n-1$ kết thúc bằng 1 cộng với số xâu độ dài $n-2$ kết thúc bằng 0 khi ta thêm '10' vào. Điều này dẫn đến công thức truy hồi: $a_n = a_{n-1} + a_{n-2}$.
Áp dụng công thức này:
- $a_3 = a_2 + a_1 = 3 + 2 = 5$
- $a_4 = a_3 + a_2 = 5 + 3 = 8$
- $a_5 = a_4 + a_3 = 8 + 5 = 13$
Vậy, có 13 xâu nhị phân độ dài 5 không chứa 2 bít 1 đứng cạnh nhau.
