วัด 1 ลิตรด้วยภาชนะสองใบและน้ำไม่จำกัดใน C++

ในปัญหานี้ เราได้รับภาชนะสองใบที่มีความจุ x และ y และแหล่งน้ำที่ไม่จำกัด งานของเราคือสร้างโปรแกรมที่สามารถคำนวณได้ว่าจะได้ 1 ลิตรพอดีในหนึ่งภาชนะอย่างไร กำหนดเงื่อนไขว่า x และ y เป็นจำนวนเฉพาะร่วมกัน (Co-primes) ซึ่งหมายถึงจำนวนสองจำนวนที่มีตัวหารร่วมมากที่สุด (GCD) เท่ากับ 1

สมมติว่าเรามีภาชนะ V1 ความจุ x และ V2 ความจุ y เพื่อวัด 1 ลิตรโดยใช้ภาชนะทั้งสอง เราจะเติมน้ำในภาชนะแรกจากแหล่งน้ำ แล้วเทไปยังภาชนะที่สอง ทำซ้ำกระบวนการนี้จนกว่าภาชนะ V1 จะมีน้ำ 1 ลิตรพอดี

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต -

V1 = 5, V2 = 8
V1 = 5 ; V2 = 0 -> เทน้ำจาก V1 ไป V2 และเติม V1 ใหม่
V1 = 5 ; V2 = 5 -> เทน้ำจาก V1 ไป V2 และเติม V1 ใหม่
V1 = 2 ; V2 = 0 -> เทน้ำจาก V1 ไป V2 ตอนนี้ V2 เต็ม ทิ้งน้ำออก
V1 = 5 ; V2 = 2 -> เทน้ำจาก V1 ไป V2 และเติม V1 ใหม่
V1 = 5 ; V2 = 7 -> เทน้ำจาก V1 ไป V2 และเติม V1 ใหม่
V1 = 4 ; V2 = 0 -> เทน้ำจาก V1 ไป V2 ตอนนี้ V2 เต็ม ทิ้งน้ำออก
V1 = 1 ; V2 = 0 -> เทน้ำจาก V1 ไป V2 และเติม V1 ใหม่
ที่นี่ V1 วัดได้ 1 ลิตรของน้ำ

ตัวอย่างโค้ด

โปรแกรมแสดงวิธีแก้ปัญหา:

#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<<"Vessel 1: "<<V1<<" | Vessel 2: "<<V2<<endl;
        V1 = V1 - transferWater(V1, V2);
    }
    cout<<"Vessel 1: "<<V1<<" | Vessel 2: "<<V2<<endl;
}

int main() {
    x= 5, y = 8;
    measure1Litre();
    return 0;
}

ผลลัพธ์

Vessel 1: 5 | Vessel 2: 0
Vessel 1: 5 | Vessel 2: 5
Vessel 1: 2 | Vessel 2: 0
Vessel 1: 5 | Vessel 2: 2
Vessel 1: 5 | Vessel 2: 7
Vessel 1: 4 | Vessel 2: 0
Vessel 1: 5 | Vessel 2: 4
Vessel 1: 1 | Vessel 2: 0