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

Đề tài: Giải thuật vét cạn sắp xếp các truyện ngắn sao cho tổng số truyện bắt đầu từ trang lẻ là lớn nhất

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

    Mặc định Giải thuật vét cạn sắp xếp các truyện ngắn sao cho tổng số truyện bắt đầu từ trang lẻ là lớn nhất

    Một quyển sách truyện có n truyện ngắn. Mỗi truyện ngắn chiếm lần lượt a1,a2, ....an trang giấy. Các truyện được in từ trang 1, mỗi truyện mới được in từ đầu trang tiếp theo. Hãy sắp xếp các truyện sao cho số lượng các truyện bắt đầu từ trang lẻ là:
    a) Lớn nhất.
    b) Nhỏ nhất.

    Mình đang làm đồ án CTDL với đề như trên.
    Thuật toán thì mình dùng backtrack để liệt kê các cấu hình thỏa mãn yêu cầu đề bài với:
    K + (n-k)/2 nếu n-k là chẵn
    MAX(x)=
    K + (n-k+1)/2 nếu n-k là lẻ
    Với k:tổng số truyện có số trang chẵn
    Công thức trên là do mình suy luận ra nhưng chưa chứng minh được, pro nào biết cách CM hoặc có giải thuật nào khác thì chỉ cho mình với.
    Thanks
    Đã được chỉnh sửa lần cuối bởi GeoHot : 18-10-2011 lúc 08:13 PM.

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Mình có cùng tư tưởng với bạn .
    Mới đầu chọn ngay vị trí trang 1. Đặt liên tiếp toàn bộ số truyện chẵn trang vào . Nếu gọi k là số truyện chẵn trang thì k sẽ dc sử dụng hết sau khi làm việc này.
    Kết thúc việc này thì trang tiép theo để bắt đầu dán truyện vào sẽ là trang LẺ

    Sau đó chỉ còn lại (n-k) số truyện là lẻ trang.
    Truyện bắt đầu từ lẻ(chẵn), lại lẻ trang thì trang tiếp theo để in truyện khác lại là chẵn(lẻ).
    Do đó số truyện dc bắt đầu ở trang lẻ trong số (n-k) còn lại này chỉ còn 1/2 (hoặc 1/2 + 1) .
    Nếu suy nghĩ theo phương thức này thì lý giải như thế.
    Vấn đề ở đây là ko biết cách này có cho ra kết quả Max ko thôi :P ^^
    Giải quyết = việc trả lời câu hỏi : Có cách nào đặt truyện chẵn trang và truyện lẻ trang theo 1 quy luật nào đó (Có thể là xen kẽ) để sao cho tận dụng dc (n-k) số truyện còn lại với 1 khả năng > (lớn hơn) 1/2 như cách trên

    Bấc giác nghĩ đến vét cạn kiểu cùi bắp vơi tư duy của lý thuyết phép đếm : Mình cho ra thuật toán vét cạn với độ phức tạp n! , thấy khủng khiếp quá nên thôi


    //----------

    Mình chứng minh như sau :
    Gọi L là tổng truyện lẻ trang, C là tổng số truyện chẵn trang
    1)Nếu dùng phép đặt các truyện lẻ trang và chẵn trang xen kẽ nhau trên khoảng nào đó . Kể cả trong 2 trường hợp là truyện lẻ trang đặt trước vào vị trí trang lẻ, hoặc đặt trước vào trang chẵn thì.
    Nếu gọi T=L'+C' là tổng số truyện đã đặt lên đoạn đó, L' (C') là tổng truyện lẻ(chẵn) trang đã dc đặt lên. thì kết quả số truyện dc đặt vào trang lẻ tối đa là (L'+C')/2 . hoặc (L'+C'+1)/2
    Vậy hiệu suất của phép này là 50% đối với L và 50% với C.
    2)Nếu dùng phương pháp đặt liên tiếp số truyện chẵn trang(chỉ tính phần của số truyện chẵn trang này thôi,số truyện lẻ trang còn lại chưa bàn) , bắt đầu từ trang lẻ .
    Hiệu suất là 100% C .
    Nếu bắt đầu từ trang chẵn, hiệu suất là 0% C
    3)Nếu dùng phương pháp đặt liên tiếp số truyện lẻ trang(số truyện chẵn trang chưa bàn), bất kể bắt đầu từ chẵn hay lẻ đều cho hiệu suất 50% L.

    --
    Trong việc xắp xếp với 2 loại phần tử này chỉ có 2 kiểu: 1 là liên tiếp , 2 là xen kẽ.
    Bằng quy nạp ta sẽ chứng minh dc nếu càng đặt xen kẽ bao nhiêu thì hiệu suất sẽ giảm bấy nhiêu so với đặt liên tiếp(trường hợp vấn đề 2)

    Vì thế cách đặt liên tiếp cho ra kết quả với hiệu suất cao nhất
    -----------------------
    Đôi lời ngu ý của mình thế :(
    Đã được chỉnh sửa lần cuối bởi beautifulsoul84hung : 19-10-2011 lúc 06:15 AM. Lý do: làm liền 2 bài viết

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    4

    Cảm ơn bạn đã bỏ thời gian suy nghĩ
    Theo mình,
    Có nhiều cách đế sắp xếp thỏa yêu cầu đề bài chứ ko phải 2 kiểu như bạn nói.
    Cách sắp k truyện chẵn đầu tiên rồi đến n-k truyện lẻ chỉ là 1 cách sắp xếp thỏa. Từ đó để mình suy ra CT như trên.
    Cách CM của bạn bằng quy nap bạn có thể nói rõ hơn dc ko, mình chưa hiểu rõ cách suy luận của bạn

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Trích dẫn Nguyên bản được gửi bởi GeoHot Xem bài viết
    Cảm ơn bạn đã bỏ thời gian suy nghĩ
    Theo mình,
    Có nhiều cách đế sắp xếp thỏa yêu cầu đề bài chứ ko phải 2 kiểu như bạn nói.
    Cách sắp k truyện chẵn đầu tiên rồi đến n-k truyện lẻ chỉ là 1 cách sắp xếp thỏa. Từ đó để mình suy ra CT như trên.
    Cách CM của bạn bằng quy nap bạn có thể nói rõ hơn dc ko, mình chưa hiểu rõ cách suy luận của bạn
    Không . 2 cách trên tức là xếp liên tiếp hoặc xen kẻ với 2 loại truyện lẻ trang và chẵn trang là mnhf đang nói ở trường hợp nguyên tử. Tức là chỉ có 2 truyện đang dc sắp xếp. . Và nếu tổng quát 2 cách trên thì dc hiệu suất như mình đã nói
    Trong 1 dãy n truyện cần sắp thì cách sắp như nào chưa cần biết, nhưng cách nào rồi cũng luôn luôn phải dc cấu thành từ 2 phép sắp xếp nguyên tử này.
    Ví dụ phép sắp : Lẻ - Chẵn - Lẻ- lẻ-Chẵn-Chẵn -chẵn-chẵn
    Thì phép sắp này dc cấu thành từ 3 phép sắp nguyen tử xen kẽ , 1 phép sắp nguyên tử liên tiếp lẻ và 3 phép sắp nguyên tử liên tiếp chẵn

    Bạn tìm dc vấn đề nguyên tử trong bài toán thì bạn có thể dùng quy nạp để chứng minh dc rùi .
    Còn ko thì chứng minh theo lối đệ quy, từ không gian lớn n , bạn chứng minh đệ quy dần xuống chỉ còn 2.
    Đã được chỉnh sửa lần cuối bởi clchicken : 19-10-2011 lúc 12:32 AM.

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

  1. Trả lời: 1
    Bài viết cuối: 19-02-2013, 06:21 PM
  2. Trả lời: 11
    Bài viết cuối: 30-11-2012, 09:22 PM
  3. truyện tình yêu hay nhất của vali du lịch thời trang cao cấp
    Gửi bởi lovewinter_1211 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 27-03-2012, 11:25 AM
  4. áp dụng giải thuật di truyền vào bài toán người du lịch. Cần làm gì?
    Gửi bởi princehai trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 06-10-2011, 08:38 AM
  5. 2 đường truyền ngắn nhất trong đồ thị
    Gửi bởi nguyen991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 07-11-2010, 10:19 AM

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