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ế :(