-
(Chú ý, chú ý...)HỔ TRỢ TRỰC TUYẾN
Quản trị: Nguyễn Thị Tố Châu(
0914.191.357
)
Chào mừng quý vị đến với Website của Trường THPT Lê Lợi Đông Hà.
Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
Nếu chưa đăng ký, hãy đăng ký thành viên tại đây hoặc xem phim hướng dẫn tại đây
Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.
Bài toán chia kẹo
- 0 / 0
-
(Tài liệu chưa được thẩm định)
Nguồn: Sưu tầm
Người gửi: Nguyễn Thị Tố Châu (trang riêng)
Ngày gửi: 07h:41' 21-04-2009
Dung lượng: 84.5 KB
Số lượt tải: 80
Nguồn: Sưu tầm
Người gửi: Nguyễn Thị Tố Châu (trang riêng)
Ngày gửi: 07h:41' 21-04-2009
Dung lượng: 84.5 KB
Số lượt tải: 80
Số lượt thích:
0 người
Bài toán chia kẹo
1
2
3
4
5
(8 votes)
Người viết: Ngô Minh Đức
23/03/2008
BÀI TÓAN CHIA KẸO
Trong số báo THNT tháng 8/2003, chuyên mục Đề ra kỳ này, có bài tóan “Chia kẹo”. Nội dung của bài tóan như sau:
Có N gói kẹo, gói thứ i có A[i] cái kẹo.
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0Dữ liệu vào:
Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được)
Dữ liệu ra:
Ghi ra file Chiakeo.out
Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần.
Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.
Dạng bài tóan này xuất hiện nhiều trong các ứng dụng về lập lịch, nó còn có tên gọi là Number Partitioning. Đây là một bài tóan thuộc lớp NP đầy đủ, không có thuật tóan tốt để giải. Bài viết này xin được trình bày một cách giải Heuristic cho ra kết qủa khá tốt.
Ta phát biểu lại bài tóan: cho n số (trong trường hợp này là số nguyên), tìm cách chia thành 2 phần sao cho độ chênh lệch tổng các số của mỗi phần là ít nhất có thể được
Trước hết chúng ta hãy xem xét một số cách giải:
1. Duyệt vét cạn
Thuật tóan vét cạn dễ hiểu nhất là xét tất cả các tập con có thể, và trả về tập con có tổng gần với một nửa tổng các số nhất. Nếu có n số, độ phức tạp của thuật tóan sẽ là O(2n) bởi vì một tập n phần tử có 2n tập con. Không gian tính tóan sẽ là O(n). Như vậy cách tiếp cận này không thực tiễn khi n lớn.
Cũng với tư tưởng duyệt vét cạn, bạn có thể cải tiến thành một thuật tóan có độ phức tạp O(2n/2) nhưng ở đây sẽ không bàn kỹ về vấn đề này.
2. Quy họach động
Thuật giải quy họach động đòi hỏi một mảng bít a[i] có kích thước là tổng các số, a[i]=1 khi và chỉ khi tồn tại tập con có tổng bằng i. Ban đầu, ta khởi tạo mảng a bằng 0, đặt a[0]=1. Sau đó với mỗi số x , quét lại mảng a, và với mỗi phần tử a[i]=1, ta đặt a[i+x]=1. Tiếp tục cho đến khi xét hết dãy số. Không gian tính tóan của thuật giải này phụ thuộc vào tổng các số. Do đó, nó chỉ thực tiễn với các số là số nhỏ, và phải là số nguyên.
3. Tham lam
Thuật giải tham lam dễ thấy nhất cho bài tóan này như sau: sắp xếp các số theo thứ tự giảm, rồi đặt số lớn nhất vào một trong hai tập. Sau đó, đặt số tiếp theo vào tập đang có tổng bé hơn, tiếp tục cho đến khi tất cả các số được xét.
Thuật giải này cài đặt rất nhanh, nhưng thường cho ra kết qủa không được tốt lắm
Phương pháp Karmarkar-Karp
Dưới đây, chúng ta xem xét một phương pháp Heuristic cho kết qủa khá tốt và cũng không khó cài đặt lắm.
Phương pháp Karmarkar-Karp (KK) đầu tiên sẽ sắp xếp các số theo thứ tự giảm dần. Tại mỗi bước, thuật tóan sẽ lấy hai số lớn nhất phân vào hai phần khác nhau ; mà chưa cần quan tâm là số nào sẽ đi vào tập nào.
Cụ thể, thuật tóan sẽ lọai bỏ hai số lớn nhất, lấy hiệu của chúng – xem đó như một số khác và chèn trở lại vào danh sách đã sắp xếp. Thuật tóan sẽ tiếp tục cho đến khi chỉ còn lại 1 số duy nhất, đó chính là giá trị chênh lệch của hai tập.
Ví dụ, ta có dãy (8; 7; 6 ; 5 ;4 )
Bước
Dãy
Hiệu của 2 số lớn nhất
0
(8; 7; 6 ; 5 ; 4)
8 – 7 = 1
1
(6; 5; 4; 1)
6 – 5 = 1
2
(4
1
2
3
4
5
(8 votes)
Người viết: Ngô Minh Đức
23/03/2008
BÀI TÓAN CHIA KẸO
Trong số báo THNT tháng 8/2003, chuyên mục Đề ra kỳ này, có bài tóan “Chia kẹo”. Nội dung của bài tóan như sau:
Có N gói kẹo, gói thứ i có A[i] cái kẹo.
Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0
Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được)
Dữ liệu ra:
Ghi ra file Chiakeo.out
Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần.
Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.
Dạng bài tóan này xuất hiện nhiều trong các ứng dụng về lập lịch, nó còn có tên gọi là Number Partitioning. Đây là một bài tóan thuộc lớp NP đầy đủ, không có thuật tóan tốt để giải. Bài viết này xin được trình bày một cách giải Heuristic cho ra kết qủa khá tốt.
Ta phát biểu lại bài tóan: cho n số (trong trường hợp này là số nguyên), tìm cách chia thành 2 phần sao cho độ chênh lệch tổng các số của mỗi phần là ít nhất có thể được
Trước hết chúng ta hãy xem xét một số cách giải:
1. Duyệt vét cạn
Thuật tóan vét cạn dễ hiểu nhất là xét tất cả các tập con có thể, và trả về tập con có tổng gần với một nửa tổng các số nhất. Nếu có n số, độ phức tạp của thuật tóan sẽ là O(2n) bởi vì một tập n phần tử có 2n tập con. Không gian tính tóan sẽ là O(n). Như vậy cách tiếp cận này không thực tiễn khi n lớn.
Cũng với tư tưởng duyệt vét cạn, bạn có thể cải tiến thành một thuật tóan có độ phức tạp O(2n/2) nhưng ở đây sẽ không bàn kỹ về vấn đề này.
2. Quy họach động
Thuật giải quy họach động đòi hỏi một mảng bít a[i] có kích thước là tổng các số, a[i]=1 khi và chỉ khi tồn tại tập con có tổng bằng i. Ban đầu, ta khởi tạo mảng a bằng 0, đặt a[0]=1. Sau đó với mỗi số x , quét lại mảng a, và với mỗi phần tử a[i]=1, ta đặt a[i+x]=1. Tiếp tục cho đến khi xét hết dãy số. Không gian tính tóan của thuật giải này phụ thuộc vào tổng các số. Do đó, nó chỉ thực tiễn với các số là số nhỏ, và phải là số nguyên.
3. Tham lam
Thuật giải tham lam dễ thấy nhất cho bài tóan này như sau: sắp xếp các số theo thứ tự giảm, rồi đặt số lớn nhất vào một trong hai tập. Sau đó, đặt số tiếp theo vào tập đang có tổng bé hơn, tiếp tục cho đến khi tất cả các số được xét.
Thuật giải này cài đặt rất nhanh, nhưng thường cho ra kết qủa không được tốt lắm
Phương pháp Karmarkar-Karp
Dưới đây, chúng ta xem xét một phương pháp Heuristic cho kết qủa khá tốt và cũng không khó cài đặt lắm.
Phương pháp Karmarkar-Karp (KK) đầu tiên sẽ sắp xếp các số theo thứ tự giảm dần. Tại mỗi bước, thuật tóan sẽ lấy hai số lớn nhất phân vào hai phần khác nhau ; mà chưa cần quan tâm là số nào sẽ đi vào tập nào.
Cụ thể, thuật tóan sẽ lọai bỏ hai số lớn nhất, lấy hiệu của chúng – xem đó như một số khác và chèn trở lại vào danh sách đã sắp xếp. Thuật tóan sẽ tiếp tục cho đến khi chỉ còn lại 1 số duy nhất, đó chính là giá trị chênh lệch của hai tập.
Ví dụ, ta có dãy (8; 7; 6 ; 5 ;4 )
Bước
Dãy
Hiệu của 2 số lớn nhất
0
(8; 7; 6 ; 5 ; 4)
8 – 7 = 1
1
(6; 5; 4; 1)
6 – 5 = 1
2
(4
Các ý kiến mới nhất