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

    hienha

    hienha
    Chuyên viên
    Chuyên viên
    Bài 5 trang 37: Một lưới ô vuông nxm (số hàng m< n số cột). Một con kiến cần leo từ điểm A lên điểm B. Mỗi lần leo chỉ bò dọc theo các cạnh của ô: lên đúng một bậc hoặc sang phải (có thể nhiều ô). Hỏi có bao nhiêu đường có thể xảy ra?
    Giải:
    Con kiến cần leo đúng m bậc lên và sang phải n bậc để đi từ điểm A đến điểm B. Vì mỗi lần nó chỉ lên đúng một bậc hoặc sang phải (có thể nhiều ô) nên sau mỗi lần lên phải có ít nhất một lần sang phải → Coi một lần lên tương ứng với một lần sang phải thì số lần lên là m, số lần sang phải còn lại là n - m (vì đã gắn m bước sang phải với m bước lên). ta đưa về bài toán 5. Số đường đi có thể xảy ra là số cách chọn m vị trí trong m + (n - m) = n vị trí, không tính đến thứ tự, không lặp. Hay đó chính là Cmn.
    TH2: lần cuối cùng chỉ có lên mà không có sang phải. ta còn m -1 lần sang lên phải kèm lần sang phải. tương tự như trên ta có số cách là Cm-1n
    Vậy tổng số cách có thể là:
    Cmn + Cm-1n = Cmn+1

    hungbeo_fm2008

    hungbeo_fm2008
    Chuyên viên
    Chuyên viên
    hienha đã viết:Bài 5 trang 37: Một lưới ô vuông nxm (số hàng m< n số cột). Một con kiến cần leo từ điểm A lên điểm B. Mỗi lần leo chỉ bò dọc theo các cạnh của ô: lên đúng một bậc hoặc sang phải (có thể nhiều ô). Hỏi có bao nhiêu đường có thể xảy ra?
    giải:
    Con kiến cần leo đúng m bậc lên và sang phải n bậc để đi từ điểm A đến điểm B. Vì mỗi lần nó chỉ lên đúng một bậc hoặc sang phải (có thể nhiều ô) nên sau mỗi lần lên phải có ít nhất một lần sang phải → Coi một lần lên tương ứng với một lần sang phải thì số lần lên là m, số lần sang phải còn lại là n-m (vì đã gắn m bước sang phải với m bước lên). ta đưa về bài toán 5. Số đường đi có thể xảy ra là số cách chọn m vị trí trong m + (n-m) =n vị trí, không tính đến thứ tự, không lặp. Hay đó chính là Cmn

    Đ/a: Cmn+1 với m<= n+1

    hienha

    hienha
    Chuyên viên
    Chuyên viên
    Anh Hưng à, bài này đáp án phải là Cmn (với m< n như đầu bài đã cho), sao lại là Cmn+1 được?

    LeVanDat

    avatar
    Chuyên viên
    Chuyên viên
    Bài tập ô lưới m * n với m < n
    con kiến leo từ A đến B tương ứng với cách đi đường thẳng với m bước lên trên và n bước sang phải. tất cả có m + n bước. Vì trong m bước lên trên không có bước nào đứng gần nhau nên ta xếp n bước sang phải thành một hàng và cách nhau một vị trí. Số cách con kiến leo từ A đến B tương đương với số sắp xếp m bước lên trên vào n + 1 vị trí xen kẽ của n bước sang phải. Vậy số cách mà kiến leo lên được là C(m, n + 1) cách.
    Lấy ví dụ m = 2, n = 3 vẽ ô ra tính được là 6 cách
    m = 3, n = 4 vẽ ô ra tính được là 10 cách.
    Lê Văn Đạt

    5[Lời giải]Bài con kiến leo lưới hình chữ nhật n x m Empty Bài này em Hiền xem lại nhé Wed Jun 01, 2011 12:50 am

    mrP

    mrP
    Thành viên cao cấp
    Thành viên cao cấp
    - em Hiền xét còn chưa tính đến trường hợp bước cuối cùng là bước đi lên, nên kết quả chưa chính xác.
    - Cách giải của đồng chí Đạt là đúng.
    [You must be registered and logged in to see this image.]

    hoangtinh

    hoangtinh
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Bài này giải như anh Đạt là đúng rùi!

    daotrang

    daotrang
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Hì, đọc con kiến với leo sang trái sang phải leo lên leo xuống có vẻ khó theo dõi và rối đầu.
    Em cứ tư duy củ chuối thế này cho đơn giản: việc con kiến leo từ A đến B cần đi hết m+n bước (m lên và n sang phải)coi như là xâu nhị phân độ dài m+n.
    Coi mỗi bước lên là một bít 1, mỗi bước sang phải là một bít O.
    Việc giải bài toán con kiến giờ trở thành: tìm số xâu nhị phân độ dài m+n có đúng m bít 1 và không có 2 bít 1 nào đứng cạnh nhau.
    Xếp n bít 0 trước.
    Có n+1 ô trống giữa các bit 0 có thể sắp m bít 1 vào đó
    Thế là có C(m,n+1) xâu nhị phân thỏa mãn bài toán tương đương với bằng đấy cách để con kiến leo lên đích!

    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 https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất