Đáp án bài toán “Chia sữa” mà bất cứ lập trình viên nào cũng đã gặp

(Dân trí) - Bài toán “Chia sữa” mà bất cứ lập trình viên nào cũng đã gặp” được Dân trí đăng tải chỉ sau 1 ngày đã nhận được hàng trăm lời giải với nhiều cách khác nhau. Dưới đây là đáp án bài toán thú vị này.

 

Đề bài:

Bài toán chia sữa (Bài toán đong nước) dạng sơ khai được phát biểu như sau: "Có một người nông dân nuôi bò sữa. Một hôm, có một người khách đến, nói muốn mua 8 lít sữa, nhưng người nông dân chỉ có một xô 16 lít đựng đầy sữa, một can 7 lít và một can 3 lít, làm thế nào mà người nông dân đã lấy ra được 8 lít sữa để bán?".

Người ta truyền tai nhau rằng Blair Pascal đã làm được bài toán này từ năm ông 7 tuổi. Trong khoa học máy tính thì đây là một bài toán rất nổi tiếng mà bất cứ lập trình viên nào cũng đã gặp qua. Ngày nay, người ta đã xây dựng được thuật giải và tìm ra được điều kiện giải được cho một số trường hợp của bài toán này bằng với các điều kiện nghiêm ngặt bằng cách sử dụng các ngôn ngữ lập trình như Pacal, C++, Visual Basic…

Cùng với chủ đề này, mời các bạn cùng tham gia giải bài toán sau:

“Có 3 bình nước: Bình thứ nhất dung tích 12 lít, bình thứ hai dung tích 7 lít, bình thứ ba dung tích 5 lít. Từ bình thứ nhất chứa đầy nước, bình thứ hai và và bình thứ ba trống, không dùng thêm dụng cụ chứa nước nào khác hãy lấy ra hai phần, mỗi phần 6 lít nước”.

Đáp án:

Một sơ đồ giải bài toán được trình bày trong bảng dưới đây:

 

Bình 12 lít

Bình 7 lít

Bình 5 lít

Bắt đầu

12

0

0

Lần 1

7

0

5

Lần 2

7

5

0

Lần 3

2

5

5

Lần 4

2

7

3

Lần 5

9

0

3

Lần 6

9

3

0

Lần 7

4

3

5

Lần 8

4

7

1

Lần 9

11

0

1

Lần 10

11

1

0

Lần 11

6

1

5

Kết thúc

6

6

0

Dân trí xin chúc mừng độc giả có lời giải đúng!

Ban Giáo dục

 

Dòng sự kiện: Thử tài giải toán