Em có bài toán như thế này mà em chưa hiểu thấu đáo những gì người giải muốn đề cập nên em đưa lên đây mong mọi người bình giảng cho em được rõ hơn ạ.Em cảm ơn mọi người. "Tính số chuỗi nhị phân độ dài n có 3 bit 0 liên tiếp:
Đặt Sn là số chuỗi nhị phân độ dài n, có 3 bit 0 liên tiếp:
Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
A1 ( A là chuỗi có độ dài n -1, A chứa 3 bit 0 liên tục) , gọi số cách là S(n-1)
B10 (B là chuỗi có độ dài n - 2, B chứa 3 bít 0 liên tục), gọi số cách là S(n-2)
C100 (C là chuỗi có độ dài n - 3, C chứa 3 bít 0 liên tục, gọi số cách là S(n-3)
D000 (D là chuỗi tùy ý dài n - 3), số cách tính được luôn là 2(n-3)

Ta có công thức truy hồi:
Sn=S(n-1) + S(n-2) + S(n-3) + 2(n-3)
Khởi tạo:
S1 = S2 = 0; S3 = 1."


Copy từ link gốc của lớp Cao học CNTT, Học viện KTQS: [You must be registered and logged in to see this link.]

Mọi người giúp em hiểu cái chỗ A1,B10,C100,D000 là những cái gì,và tại sao có những cái đó ạ.hi

binhtu đã viết:Mọi người giúp em hiểu cái chỗ A1,B10,C100,D000 là những cái gì,và tại sao có những cái đó ạ.hi

Bạn nên hiểu nôm na thế này: Giả sử chuỗi nhị phân n bit chứa 3 bit 0 liên tiếp có dạng XXX...XXX (X: là 0 hoặc 1). Xét bít cuối cùng (bit n) có thể là 0 hoặc 1: đặt chuỗi đó là A0 và A1. Xét tiếp chuỗi A0 thì bít tiếp theo từ phải qua cũng có thể là 0 hoặc 1 (đặt tiếp là B00 và B10). Tương tự xét B00 có thể là 2 chuỗi C100 và D000. Như thế số chuỗi NP có 3 bít 0 liên tiếp sẽ là tổng của các chuỗi A1+A0 = A1+(B00+B10)=A1+(B10+(C100+D000)).
Còn tại sao lại như thế thì nó là phương pháp phân tích để đưa về công thức truy hồi.

Cho em hỏi tại sao mà S₁=0,S₂=0,S₃=1 ạ.xin lỗi em ko biết gõ chỉ số dưới nên em gõ như vậy thôi ạ.hi.Cảm ơn anh chị!

Ban QT:
- Gõ chỉ số dưới: Bôi đen, nháy vào nút Others, chọn tuỳ chọn "Chỉ số dưới"
- Đó là các giá trị khởi tạo. Thông thường khi giải một bài toán người ta thường xem xét ở một giai đoạn. Bắt đầu 1 giai đoạn rồi kết thúc ở một giai đoạn. Hết giai đoạn A đến giai đoạn B. Việc đặt giá trị khởi tạo nhằm làm cho tất cả các giai đoạn đều làm việc giống nhau. Nếu không đặt giá trị khởi tạo, bạn phải xét 2 trường hợp: Trường hợp giai đoạn ban đầu (cách làm việc khác) và các trường hợp cho các giai đoạn còn lại.
- Cấm spam bằng cách lặp lại câu hỏi ở liên tiếp nhiều lần. Muốn sửa lại, chọn nút sửa. Việc spam làm cho loãng chủ đề khiến nhiều người mất thời gian không cần thiết. Ngay cả nút cám ơn để tránh trường hợp tốn nhiều trang nếu chỉ có cảm ơn, cảm ơn...

binhtu đã viết:Cho em hỏi tại sao mà S₁=0,S₂=0,S₃=1 ạ.xin lỗi em ko biết gõ chỉ số dưới nên em gõ như vậy thôi ạ.hi.Cảm ơn anh chị!

Bạn nên đọc kỹ lại đầu bài nhé! Đối với dãy này n>=3, như vậy với điều kiện đầu bài ra thì S₃=1(chính là dãy 000), 0=S₂=S₁