Đạ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]

    Admin


    Quản trị viên
    Quản trị viên
    Đề thầy cho:
    Tính số xâu nhị phân có độ dài 8 và có đúng 1 cặp 00.
    Bạn nào giải xong đưa lời giải lên nha.

    Còn [You must be registered and logged in to see this link.]


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Bài toán:
    Tìm công thức tính số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp.

    Cách giải:
    Trước hết ta tìm số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp:
    Gọi Kn là số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp. Ta có các trường hợp xảy ra:
    − Số thứ n bằng 1. Số xâu thỏa mãn là Kn-1
    − Số thứ n bằng 0. Ta xét tiếp:
    Số thứ n-1 bằng 1 thì số xâu thỏa mãn là Kn-2
    Số thứ n-1 bằng 0 thì số xâu thỏa mãn là 2n-2

    Vậy Kn = Kn-1 + Kn-2 + 2n-2
    Với điều kiện ban đầu K1 = 0; K2 = 1.
    Bằng cách chứng minh tương tự, ta có số xâu nhị phân có độ dài n chứa hai số 1 liên tiếp cũng là:

    Kn = Kn-1 + Kn-2 + 2n-2
    Với điều kiện ban đầu K1 = 0; K2 = 1.
    Bây giờ, ta gọi số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp là Sn, ta có các khả năng xảy ra:
    − Hai số cuối là 00. Số xâu nhị phân thỏa mãn chính bằng số xâu nhị phân có độ dài n-2 chứa hai số 1 liên tiếp và bằng Kn-2.
    − Hai số cuối là 11. Số xâu nhị phân thỏa mãn chính bằng số xâu nhị phân có độ dài n-2 chứa hai số 0 liên tiếp và bằng Kn-2.
    − Trường hợp còn lại. Số xâu nhị phân thỏa mãn bằng Sn-1.

    Vậy số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp cho bởi công thức:

    Sn = Sn-1 + 2Kn-2 với điều kiện ban đầu là K1 = K2 = K3 = 0.



    Được sửa bởi Admin ngày Mon Jun 27, 2011 4:58 am; sửa lần 2.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Tôi có ý tưởng như thế này.

    Xét xâu nhị phân có độ dài 7, sao cho có ít nhất 1 số 0 và không có 2 số 0 nào cạnh nhau, do đó số số không trong xâu lớn nhất sẽ là 4 (nó không được lớn hơn số số 1 cộng 1).
    - Với xâu có 1 số 0; 6 số 1: có [You must be registered and logged in to see this image.]
    - Với xâu có 2 số 0; 5 số 1: có [You must be registered and logged in to see this image.]
    - Với xâu có 3 số 0; 4 số 1: có [You must be registered and logged in to see this image.]
    - Với xâu có 4 số 0; 3 số 1: có [You must be registered and logged in to see this image.]

    Để thỏa mãn yêu cầu của bài toán, tức là chỉ có đúng một cặp 00 trong xâu nhị phân có độ dài là 8, ta chỉ cần thêm 1 số 0 vào xâu nhị phân có độ dài là 7 như trên ta đã xét, sao cho số 0 mới thêm nằm cạnh với số 0 đã có trong xâu (đặt trước hay sau thì cũng chỉ là một cách). Với xâu có bao nhiêu số 0 thì có bấy nhiêu cách để thêm sô 0.

    Vậy đáp án là:
              [You must be registered and logged in to see this image.]

    Còn công thức tổng quát với xâu có độ dài là n thì có lẽ là

              [You must be registered and logged in to see this image.]

    (bạn nào tính hộ mình nhé)


    ================
    [You must be registered and logged in to see this image.]

    Admin


    Quản trị viên
    Quản trị viên
    Tôi đang băn khoăn chỗ này là số lượng:
    - Với xâu có 2 số 0; 5 số 1: có [You must be registered and logged in to see this image.]
    - Với xâu có 3 số 0; 4 số 1: có [You must be registered and logged in to see this image.]
    - Với xâu có 4 số 0; 3 số 1: có [You must be registered and logged in to see this image.]

    Nếu nó đã thành cặp 00 rồi thì sao? Ta thêm số 0 nữa cho đủ độ dài 8, thì không thoả mãn đầu bài có đúng 1 cặp 00


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    @Cuong: Nếu nó đã thành cặp 00 rồi thì sao? Ta thêm số 0 nữa cho đủ độ dài 8, thì không thoả mãn đầu bài có đúng 1 cặp 00
    - Anh tưởng tượng như thế này nhé. Giả sử anh có một xâu thỏa mãn yêu cầu, tức là xâu có độ dài 8 chỉ có đúng 1 cặp 00. Anh xóa béng một số 0 trong cặp đó, lúc này xâu nhị phân sẽ có độ dài là 7, và không có bất cứ cặp 00 nào. Nhớ là xâu có độ dài 7 không có bất cứ cặp 00 nào nhé. Công việc của mình là làm ngược lại. Tìm tất cả các trường hợp có độ dài là 7, không có 2 số 0 đứng cạnh nhau. Sau đó thêm 1 số 0 vào cạnh số 0 trong xâu có độ dài 7.
    Ví dụ: xâu có độ dài 7: 0110101
    Như vậy ta sẽ có 3 cách thêm (tương ứng với số số 0 trong xâu, thêm trước hay sau số 0 đó đều như nhau) như sau:
    00110101 (hoặc 00110101)
    01100101 (hoặc 01100101)
    01101001 (hoặc 01101001)
    - Còn trường hợp tính : Với xâu có 2 số 0; 5 số 1; Với xâu có 3 số 0; 4 số 1; Với xâu có 4 số 0; 3 số 1. Anh hãy xem lại [You must be registered and logged in to see this link.], nó không được bò dọc liên tiếp, cũng như việc 2 số 0 không đứng cạnh nhau.



    Được sửa bởi Admin ngày Wed Jun 08, 2011 6:33 am; sửa lần 1. (Reason for editing : Đưa link liên quan vào)


    ================
    [You must be registered and logged in to see this image.]

    Admin


    Quản trị viên
    Quản trị viên
    uh. Cũng có lý đấy. Thử tính xem đáp án là bao nhiêu nhé:
    [You must be registered and logged in to see this image.]

    [You must be registered and logged in to see this image.]

    [You must be registered and logged in to see this image.]

    = 7 + 30 + 15 + 4 = 56


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    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

    Forumotion.com | © PunBB | Free forum support | Liên hệ | Report an abuse | www.sosblogs.com