Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Xây dựng thuật toán tìm tập S* sao cho các đoạn thẳng trong S* đôi một không có điểm chung mà có tổng độ dài các đoạ

  1. #1
    Ngày gia nhập
    10 2008
    Nơi ở
    Hà Nội
    Bài viết
    37

    Mặc định Xây dựng thuật toán tìm tập S* sao cho các đoạn thẳng trong S* đôi một không có điểm chung mà có tổng độ dài các đoạ

    Em được giao một bài tập lớn như sau :

    Mỗi đoạn thẳng trên trục Ox được mô tả bởi hai 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* sao cho các đoạn thẳng trong
    S* đôi một không có điểm chung mà có tổng độ dài các đoạn thẳng là lớn nhất.

    Em chưa nghĩ ra hướng đi của bài toán. Mọi người có ý tưởng gì gọi ý giúp em
    >>> Hãy gõ tiếng Việt có dấu rõ ràng khi bạn gửi bài viết

  2. #2
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    bước 1: nếu giới hạn a, b lớn thì bạn rời rạc hóa để chuyển các tọa độ a[i], b[i] về giới hạn nhỏ, cỡ 2*n.

    bước 2: sort lại các đoạn thẳng theo a, nếu a bằng nhau thì sort tăng theo b

    bước 3: sau đó xử lý bằng Quy hoạch động như sau: gọi f[x] là tổng độ dài lớn nhất của các đoạn thẳng không giao nhau, và đoạn thẳng cuối cùng có b = x. Với mỗi đoạn thẳng i có cận dưới là ai, bạn duyệt tìm xem từ f[0] tới f[ai-1] xem cái nào lớn nhất, sau đó cập nhật f[bi] = (f max tìm được) + (độ dài đoạn i)

    Tùy vào cách tìm đoạn f max lớn nhất mà thuật toán của bạn sẽ có độ phức tạp là n^2 hoặc n*logn. Kết quả bài toán là max của các f[bi]
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

  3. #3
    Ngày gia nhập
    10 2008
    Nơi ở
    Hà Nội
    Bài viết
    37

    Trích dẫn Nguyên bản được gửi bởi tiendaotd Xem bài viết
    bước 1: nếu giới hạn a, b lớn thì bạn rời rạc hóa để chuyển các tọa độ a[i], b[i] về giới hạn nhỏ, cỡ 2*n.

    bước 2: sort lại các đoạn thẳng theo a, nếu a bằng nhau thì sort tăng theo b

    bước 3: sau đó xử lý bằng Quy hoạch động như sau: gọi f[x] là tổng độ dài lớn nhất của các đoạn thẳng không giao nhau, và đoạn thẳng cuối cùng có b = x. Với mỗi đoạn thẳng i có cận dưới là ai, bạn duyệt tìm xem từ f[0] tới f[ai-1] xem cái nào lớn nhất, sau đó cập nhật f[bi] = (f max tìm được) + (độ dài đoạn i)

    Tùy vào cách tìm đoạn f max lớn nhất mà thuật toán của bạn sẽ có độ phức tạp là n^2 hoặc n*logn. Kết quả bài toán là max của các f[bi]
    Cảm ơn bác, em hiểu cách làm rồi .

    Em đã làm xong bài này. Post lên cho mọi người tham khảo
    Attached Files Attached Files
    >>> Hãy gõ tiếng Việt có dấu rõ ràng khi bạn gửi bài viết

  4. #4
    Ngày gia nhập
    06 2017
    Bài viết
    1

    b ơi mình chạy code báo k tìm thấy file text

  5. #5
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    306

    Trích dẫn Nguyên bản được gửi bởi tiendaotd Xem bài viết
    bước 1: nếu giới hạn a, b lớn thì bạn rời rạc hóa để chuyển các tọa độ a[i], b[i] về giới hạn nhỏ, cỡ 2*n.

    bước 2: sort lại các đoạn thẳng theo a, nếu a bằng nhau thì sort tăng theo b

    bước 3: sau đó xử lý bằng Quy hoạch động như sau: gọi f[x] là tổng độ dài lớn nhất của các đoạn thẳng không giao nhau, và đoạn thẳng cuối cùng có b = x. Với mỗi đoạn thẳng i có cận dưới là ai, bạn duyệt tìm xem từ f[0] tới f[ai-1] xem cái nào lớn nhất, sau đó cập nhật f[bi] = (f max tìm được) + (độ dài đoạn i)

    Tùy vào cách tìm đoạn f max lớn nhất mà thuật toán của bạn sẽ có độ phức tạp là n^2 hoặc n*logn. Kết quả bài toán là max của các f[bi]
    Nếu có hơn 1 đoạn có cận trên bi=x thì lấy cái ai nào nhỉ?

Các đề tài tương tự

  1. Kỹ thuật C Thuật toán DDA vẽ đường thẳng trong C++?
    Gửi bởi knightherotam trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 20-09-2012, 10:10 PM
  2. Help! Lập trình đồ họa! Vẽ đường thẳng bằng thuật toán midpoint
    Gửi bởi kuhoang0512 trong diễn đàn Nhập môn lập trình Java
    Trả lời: 0
    Bài viết cuối: 21-04-2012, 11:39 PM
  3. Trả lời: 0
    Bài viết cuối: 28-02-2012, 09:41 PM
  4. Thuật toán vẽ đường thẳng Bresenham
    Gửi bởi trungtin1710 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 08-06-2010, 10:52 PM
  5. Tính P trong giải thuật vẽ đường thẳng Bresenham!
    Gửi bởi alias_va trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 08-01-2008, 10:50 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn