Giải bài toán chia kẹo trong Scratch – Làm quen với quy hoạch động

Like Tweet Pin it Share Share Email

Các bạn nào đang bồi dưỡng Pascal hoặc C++ (THCS) thì hẳn không thể nào không biết đến bài toán chia kẹo đúng không nào, đây là bài toán mà các giáo viên hay dùng để minh họa khi dạy “quy hoạch động”

Bây giờ ta thử đưa bài toán này cho các bạn học sinh tiểu học giải quyết coi thế nào.

Bài toán chia kẹo cho các bạn HS tiểu học

Có 8 gói kẹo, mỗi gói có từ 10 đến 20 cái kẹo. Người ta muốn chia 8 gói kẹo này thành 2 phần quà sao cho số kẹo ở hai phần quà chênh lệch nhau ít nhất (Không bóc bất kì gói kẹo nào). Em hãy lập trình để thực hiện điều đó.

Yêu cầu cụ thể:

Dữ liệu vào: Tạo một danh sách có 8 phần tử, mỗi phần tử chứa một số ngẫu nhiên từ 10 đến 20

Dữ liệu ra: 2 danh sách chứa các phần tử tương ứng của hai nhóm và một nhân vật nói ra số kẹo chênh lệch của 2 phần quà.

Gợi ý giải bài toán chia kẹo trong Scratch

Có 8 gói kẹo mỗi gói không quá 20 cái kẹo vậy tối đa có 160 cái kẹo. Vì vậy ta tạo mảng D có 160 phần tử.

Đầu tiên cho 160 phần tử của mảng D này đều bằng 0. Mỗi lần thêm 1 gói kẹo vào thì đánh dấu vào D.

VD: có 1 gói kẹo có 15 cái kẹo được thêm vào thì ta sẽ cho phần tử thứ 15 của D bằng 1. Đồng thời duyệt hết mảng D xem đã có những phần tử khác nào được đánh dấu. Giả sử có phần tử 10, 12 đã đánh dấu khi đó ta sẽ đánh dấu các phần tử 10 + 15 = 25 và 12 + 15 = 27 bằng 1. Để làm được điều này ta dùng một mảng TG luôn “theo sau” mảng D.

Như vậy kĩ thuật này giúp ta tìm được tất cả các cách để kết hợp các gói kẹo. Từ đó có thể giải quyết được bài toán.

Tiếp theo còn phải truy vết để tìm các xem gói nào vào phần 1 và phần 2 nữa.

Để cho dễ hiểu ta minh họa hình sau:

Mảng “vết” giúp truy vết xem đã có số nào được cộng vào để cho kết quả là chỉ số.

VD:

Hình trên 12 có được là do thêm 5 vào. Lấy 12 – 5 = 7.

7 có được do thêm 3 vào 7-3=4

phần tử thứ 4 có giá trị là 0

vậy 12 sinh ra bởi: 12 = 5+3+4

Có mảng vết này mình sẽ lần ra được phương án tối ưu.

Đây chính là dạng “quy hoạch động” mình rảnh sẽ ra video để chia sẻ cùng các bạn

 

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *