Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    binhtu


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    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.]

    binhtu


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    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

    trungttnd


    Thành viên cao cấp
    Thành viên cao cấp
    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.

    binhtu


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Cho em hỏi tại sao mà S1=0,S2=0,S3=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...



    Được sửa bởi binhtu ngày Sun Dec 25, 2011 6:02 am; sửa lần 1.

    mr.quoctri


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    binhtu đã viết:Cho em hỏi tại sao mà S1=0,S2=0,S3=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ì S3=1(chính là dãy 000), 0=S2=S1

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create your own blog