Đo một lít bằng hai bình và nguồn nước vô tận trong C++

Trong bài toán này, chúng ta được cho hai bình với dung tích x và y và một nguồn nước vô tận. Nhiệm vụ là tạo một chương trình có thể đo chính xác 1 lít nước trong một bình. Điều kiện là x và y là hai số nguyên tố cùng nhau. Nguyên tố cùng nhau còn được gọi là nguyên tố tương đối, nguyên tố lẫn nhau là hai số có ước chung lớn nhất là 1.

Giả sử chúng ta có hai bình V1 với dung tích x và V2 với dung tích y. Để đo 1 lít bằng hai bình này, chúng ta sẽ đổ đầy bình đầu tiên từ nguồn nước rồi đổ vào bình thứ hai. Lặp lại quá trình này cho đến khi bình V1 chứa 1 lít nước.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào –

V1 = 5, V2 = 8
V1 = 5 ; V2 = 0 -> đổ nước từ V1 sang V2 và đổ đầy lại V1.
V1 = 5 ; V2 = 5 -> đổ nước từ V1 sang V2 và đổ đầy lại V1.
V1 = 2 ; V2 = 0 -> đổ nước từ V1 sang V2. Bây giờ V2 đầy, làm rỗng nó.
V1 = 5 ; V2 = 2 -> đổ nước từ V1 sang V2 và đổ đầy lại V1.
V1 = 5 ; V2 = 7 -> đổ nước từ V1 sang V2 và đổ đầy lại V1.
V1 = 4 ; V2 = 0 -> đổ nước từ V1 sang V2. Bây giờ V2 đầy, làm rỗng nó.
V1 = 1 ; V2 = 0 -> đổ nước từ V1 sang V2 và đổ đầy lại V1. Ở đây, V1 đo được 1 lít nước.

Ví dụ

Chương trình minh họa giải pháp:

#include <iostream>
using namespace std;
int x, y, V1, V2 = 0;
int transferWater(int amt1, int amt2) {
    if (amt1 + amt2 < y){
        V2 += V1;
        return V1;
    }
    int transferred = y - V2;
    V2 = 0;
    return transferred;
}
void measure1Litre() {
    while(V1 != 1){
        if (V1 == 0)
            V1 = x;
        cout<<"Bình 1: "<<V1<<" | Bình 2: "<<V2<<endl;
        V1 = V1 - transferWater(V1, V2);
    }
    cout<<"Bình 1: "<<V1<<" | Bình 2: "<<V2<<endl;
}
int main() {
    x= 5, y = 8;
    measure1Litre();
    return 0;
}

Kết quả

Bình 1: 5 | Bình 2: 0
Bình 1: 5 | Bình 2: 5
Bình 1: 2 | Bình 2: 0
Bình 1: 5 | Bình 2: 2
Bình 1: 5 | Bình 2: 7
Bình 1: 4 | Bình 2: 0
Bình 1: 5 | Bình 2: 4
Bình 1: 1 | Bình 2: 0