এই সমস্যাতে, আমাদের দুটি পাত্র দেওয়া থাকে যাদের ধারন ক্ষমতা x এবং y, এবং অসীম জল সরবরাহ আছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা ঠিক ১ লিটার জল একটি পাত্রে মাপে দিতে পারবে। শর্ত হলো x এবং y হলো সহ-মৌলিক (co-prime) সংখ্যা, অর্থাৎ তাদের গ.م.সূ (GCD) হলো ১।
পদ্ধতি
ধরুন, V1 পাত্রের ক্ষমতা x এবং V2 পাত্রের ক্ষমতা y। ১ লিটার মাপতে হলে প্রথমে V1 কে জল সরবরাহ থেকে পূর্ণ করব, তারপর সেটি V2-এ ঢেলে দিব। V2 পূর্ণ হলে সেটি খালি করব। এই প্রক্রিয়া বারবার করলে শেষে V1-এ ঠিক ১ লিটার জল থাকবে।
উদাহরণ (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-এ ঠিক ১ লিটার জল আছে
C++ প্রোগ্রাম উদাহরণ
#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
