水差し問題～宜しくお願いいたします
こんにちは。初めて投稿させていただきます。
今、下記の問題に取り組んでいるのですが、1週間ほど自分なりに考えたものの、問題の意図しているところが全く分からず困り果てております。ネット上の同じ類のものを参考にしてもお手上げ状態です。
2個の容器の体積a,bと任意の水の体積cとを入力し，a,bだけを用いて体積cを量ることが可能かどうか判定し，可能ならその手順を自動生成するプログラムを作成せよ。問題を単純化するため，水を汲むのはb, 捨てる（量る）のはaの容器だけとし，
(1)a を空にする
(2)b を満杯にする
(3)b が空になるまでbからaに移す
(4)a が満杯になるまでbからaに移す
の4種類の手続きだけを用いるものとする。
ヒント: c<aかつc<b なら量り出しは不可能である。また，cがa, bの最大公約数の倍数でなければ量り出しは不可能である。それ以外なら上記1～4の手続きの組み合せで必ず量り出せる。)
私自身一度、「水が無限にありそれを２つの容器を駆使して目的の容量を測る問題」と解釈しました。しかし、その解釈の仕方だとヒントの条件が成り立ちませんでした。
例)a=5 b=3 c=1
(a,b)
(0,3)-(2)
(3,0)-(3)
(3,3)-(2)
(5,1)-(4)
(0,1)-(1)
(1,0)-(3)
c<a、c<bでも成立
そこで次に「cの水の容量がまず存在し、それをaとbの容器を駆使して測る問題」だと解釈しました。しかし、この解釈でも行き詰ってしまいました。
例)a=6,b=4,c=6
(0,4,2)-(2)
(4,0,2)-(3)
bは満杯に汲まなければいけないのでこれ以上bは汲めません
満杯に汲まずとも汲めると考えてもみましたが、
例)a=6,b=4,c=4
(0,4,0)
(4,0,0)
捨てる時に測るので、aは捨てる際満杯でなくてはならないため、これでは測れません。
完全に行き詰ってしまいました。長文になってしまいましたが、上記をご覧になって、何か良いアドバイスなどあれば、ぜひともご指導のほど宜しくお願いいたします。
お礼
なるほど。 適当に容器の大きさを決めて計算したところ、たしかに上向きの水圧で ちょうど相殺されました。 全体を見なければなりませんね。 回答ありがとうございました。