C++で2つの容器と無限の給水源を使って1リットルを正確に測る方法

この問題では、容量がそれぞれ x と y の2つの容器と、無限に供給される水が与えられます。求められているのは、どちらか一方の容器の中でちょうど1リットルの水を測り出すことのできるプログラムを作成することです。ただし、x と y は互いに素（coprime）であるという条件が付いています。

互いに素（「相対的に素」「相互に素」とも呼ばれます）とは、2つの整数の間に共通する約数が 1 のみしか存在しない関係のことです。言い換えると、両者の最大公約数（gcd：greatest common divisor）が 1 であることを意味します。この性質があるため、容器を満たしたり注ぎ足したりする操作の繰り返しによって、必ず1リットルを生み出せるのです。

解法のアプローチ

ここでは、容量 x の容器 V1 と容量 y の容器 V2 の2つがあると仮定します。1リットルを測る手順は以下の通りです。

まず V1 を給水源から満杯にし、その水を V2 へ注ぎ込みます。V2 が満杯になった場合は空にします。この「満たす → 注ぐ → 必要なら空にする」という一連の操作を、V1 内の水量がちょうど1リットルになるまで繰り返します。x と y が互いに素である限り、この操作は必ず終了することが数学的に保証されています。

具体例で理解する

V1 の容量が 5、V2 の容量が 8 の場合を考えてみましょう。

入力：

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 がちょうど1リットルの水を保持している。

最終的に容器 V1 に1リットルの水が残り、目的を達成できました。

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

このように、各ステップでの容器の状態を出力すると、最後の行で V1 が 1 となっていることが確認できます。この手法は「水差しパズル（Water Jug Problem）」として知られる古典的な問題であり、ユークリッドの互除法の原理（最大公約数の性質）と密接に関連しています。