Bài toán tìm dãy con có tổng chia hết cho k

Bài toán tìm dãy con có tổng chia hết cho k

Phiên bản: 1.0.0.0

1. Giới thiệu

Phát triển và minh họa cho bài toán kinh điển: Bài toán tìm dãy con dài nhất có tổng chia hết cho k.

Nội dung: Cho 1 dãy A gồm n số nguyên dương a[1..n] và số nguyên dương k. Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho k.

Ứng dụng thực tế: 1 cửa hàng nhân dịp khuyến mãi tổ chức sự kiện “mua 1 món hàng tặng 1 phiếu cào” và phần thưởng của phiếu cào đó thật sự rất hấp dẫn. 1 nhóm bạn đã quyết định gom tiền mỗi bạn trong nhóm lại để mua các món hàng. Nhưng mỗi bạn phải gom 1 khoản tiền như nhau để công bằng. Bạn hãy đóng vai nhóm trưởng quyết định mua các món hàng nào để được nhiều phiếu cào nhất nhưng phải đảm bảo tính công bằng phía trên. Giả sử có danh sách các món hàng kèm mệnh giá tương ứng, mỗi món chỉ có số lượng là 1 cái.

2. Hướng dẫn sử dụng:

Giao diện:

clip_image002

Giao diện tạo mới:

clip_image003

Giao diện sau khi đã tạo mới:

clip_image005

Chọn 1 item trong ListBox tương đương với thao tác chọn 1 món hàng vào danh sách mua.

Trạng thái tổng số món hàng (chính là tổng số phiếu cào) được hiển thị kế label: Tổng số món đồ và tổng mệnh giá được hiển thị kế label: Tổng giá trị

Khi tổng giá trị chia hết cho số người thì StatusBar bên dưới cùng sẽ hiển thị là Chia hết và nút Hoàn tất cũng sẽ sáng lên. Muốn kết thúc chỉ việc nhấn Hoàn tất để có kết quả lưu dưới listbox phía dưới.

Giải thuật tìm đáp án lần này vẫn là dùng quy hoạch động (cách làm mình sẽ up sau).

Lần này mình thiết kế đơn giản nên để time chạy thoải mái, và chưa có nút restart 😀

clip_image007

3. Download tại:

http://www.mediafire.com/?l84ymfhtbzj49i1

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s