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

    tttpdl

    avatar
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Em chào mọi người !
    Em đang học môn phân tích đánh giá thuật toán của Thầy Tĩnh, thầy có giao đề tài về nhà làm, nhưng em suy nghĩ mãi mà vẫn chưa tìm ra hướng đi đúng. Anh chị có thể đọc và hướng dẫn giúp em không? Bọn em là lớp cao học không tập trung nên ít được đi học. Mong nhận được câu trả lời của anh chị! Em cảm ơn.
    Đề tài: Mỗi đoạn thẳng trên trục OX được mô tả bởi 2 giá trị [a,b]. kí hiệu S là tập hợp n đoạn thẳng S={ [ai,bi], i=1,2...n}. Xây dựng thuật toán tìm tập S* gồm các đoạn thẳng "liên thông", nghĩa là các đoạn thẳng trong S* khi đặt trên trục hoành sẽ tạo thành một đoạn thẳng mới, sao cho đoạn thẳng mới được tạo thành có độ dài lớn nhất.

    trungttnd

    trungttnd
    Thành viên cao cấp
    Thành viên cao cấp
    Bài trên có thể hiểu như sau:

    Cho trước dãy S=A={[aibi] i= 1,2,…n}.
    Xây dựng thuật toán tìm tập S* gồm các đoạn thẳng “liên thông” nghĩa là: Tìm dãy con không giảm S*=B có độ dài lớn nhất?

    Mô tả:

    Bài toán tìm dãy đơn điệu dài nhất là bài toán về thể loại xâu ký tự (Character strings). Yêu cầu của bài toán là từ một dãy ký tự cho trước ta phải tìm ra một dãy con không tăng hoặc không giảm có dộ dài lớn nhất. Đối với những loại bài toán kiểu như thế này có lẽ cách giả tốt nhất là sử dụng thuật toán quy hoạch động để giải.

    Ví dụ: cho dãy số nguyên A = ai (i<=10000, |ai|<= 10000). Tìm cách chọn ra một dãy con không giảm hoặc không tăng B của A (B A) (bao gồm một số các phần tử trong A nhưng vẫn giữ nguyên thứ tự) có độ dài lớn nhất.
    Giả sử cho dãy : A = ( 1, 2, 3, 4, 5, 9, 10, 5, 4, 6, 7, 8)
    Ta tìm được dãy con B không giảm dài nhất là B =(1,2,3,4,5,5,6,7,8)

    Bạn có thể tham khảo và nghiên cứu theo hướng trên. Chúc bạn hoàn thành tốt bài của thầy Tĩnh ^^

    tttpdl

    avatar
    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Anh ơi, e nghĩ bài này không chỉ có thế, vì nó là 1 điểm trên OX nên nó phải được biểu diễn bởi 2 giá trị (điểm đầu, điểm cuối). Em lấy 1 bộ Input, Output. anh xem ý tưởng của em đúng không nhé. ( biểu diễn các điểm trong S trên trục OX, chúng ta sẽ dễ dàng thấy được S*)
    Input: S={ [-5,-4], [3,6], [4,5], [9,10], [-2,1], [0,4], [11,15], [6,7] }
    Output: S*={ [-2,1], [0,4], [3,6], [4,5], [6,7] } ( vì các đoạn này tạo thành đoạn thẳng liên thông trên OX dài nhất là [-2,7] ).
    Nếu anh quan tâm tới bài này thì xem giúp em ý tưởng của em để em phát triển đề tài tiếp nhé. Em cảm ơn anh nhiều!!!

    hiruhd

    hiruhd
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    em mới nhận được đề tài này hôm qua. Các anh chị đã bảo vệ rồi cho em xin liên hệ để em hỏi bài với a. Em xin chân thành cảm ơn!

    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