Vận dụng (M3)

Số lượng các xâu nhị phân (chỉ gồm bit 0 và 1) có độ dài bằng 8 sao cho không có bất kỳ 2 bit '1' nào đứng liền kề nhau là

1

Xác nhận

Giải thích đáp án:

Độ dài 1 ô: Điền '0' hoặc '1' 2 xâu.

Độ dài 2 ô: Đuôi '0' (00, 10), Đuôi '1' (chỉ ghép được sau con 0: 01) 3 xâu.

Tư duy tịnh tiến:

Muốn tạo xâu dài ô mà đuôi là '0': Cứ lấy xâu ô chắp thêm '0' vào sau.

Muốn tạo xâu dài ô mà đuôi là '1': Bắt buộc đằng trước nó phải là '0'. Tức là lấy xâu ô, chắp thêm cụm '01' vào sau.

Số xâu dài = (Số xâu dài ) + (Số xâu dài ).

Cứ thế cộng dồn: .