水差し問題～宜しくお願いいたします

質問

こんにちは。初めて投稿させていただきます。
今、下記の問題に取り組んでいるのですが、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は捨てる際満杯でなくてはならないため、これでは測れません。

完全に行き詰ってしまいました。長文になってしまいましたが、上記をご覧になって、何か良いアドバイスなどあれば、ぜひともご指導のほど宜しくお願いいたします。

回答No.5

noname#30727 · ベストアンサー

#4です。訂正します。

>「問題を単純化するため」aからbに移す事ができず
「問題を単純化するため」量らずに捨てる事ができず

>「捨てる＝計る」
「捨てる＝量る」

お礼

「量らずに捨てることができない」の一文が大変参考になりました。先入観にとらわれて問題文をきちんと読めていなかったようです。お騒がせしました＾＾；この解釈の仕方なら矛盾なく、すんなりとプログラムが作れました。ご指導ありがとうございました。

回答No.6

chokuto

（inthefloiさんが既におっしゃっていることですが、）やはり、「無限の水を生む水源」があると考えるべきでしょう。ただ、はじめは「最後に容器aに残った水の量がcとなる」ように考えていたのですが、実際のところは「容器aから捨てた水の総量がcとなる」ようにするということなのだと思います。そう考えると、これまでの矛盾は解決できそうです。

お礼

「容器aから捨てた水の量がcとなる」の一文が大変参考になりました。仰る通り、この解釈で当初作っていたプログラムを少しいじると、これまでの矛盾は解決しました。ご丁寧な回等ありがとうございました。

回答No.4

noname#30727

>捨てる（量る）
「捨てる＝計る」だとすれば、「c<aかつc<b なら量り出しは不可能である」というのも成り立ちます。
もちろん、無限の水からcを取り出すのですが、「問題を単純化するため」aからbに移す事ができず、結果として量れない場合が多くなりますが、それはそれでいいのではないかと。

>2個の容器の体積a,b
出題者は「容器の体積」などと奇妙な言い方をする人ですから、こういう解釈もありかなと（笑

回答No.3

kacchann

・はじめにcには水を満杯に入れておく。
・「bでくむ」と言うのは、「どこからくんでくるのか」といえば、
「cから」くんでもいいし、
「水が無限にあるプール」からくんで(借りて)もいい。使い分ける。
---

かな？
この問題は
「まず容量のわかる容器a,bがあって、
次に『容量はわからないがa,bよりはでかい容器c』があって、
a, b,および水を自由に用いて
『c容器の容量を算出する』問題」
だと思う。(※c容器の容量と同量の水を作り出す問題ではない。
あくまでもcの容量は「わからない」)

ノーヒントで(※ヒント『(1)～(4)の手続き』が与えられてなかったとして)
はじめの問題に立ち返って考えると、
解答の方針がつかめると思う。

お礼

そういう解釈の仕方もあるんですね。一度その解釈でも考えてみます。ご丁寧な回答ありがとうございました。

回答No.2

sakyo-t

何かの課題ですかね？

一般的に水差し問題は
「水が無限にありそれを２つの容器を駆使して目的の容量を測る問題」の考え方でいいんじゃないですか？

量る(捨てる)のはAだけということなので、最終的にAにCの分だけ水が残っていれば計測完了です。

これが普通の水差し問題であれば
chokutoさんの
>これは「c>aかつc>b なら量り出しは不可能」の間違いでは？

に激しく賛成です。

お礼

長文にもかかわらず、お読みいただきありがとうございます。お察しの通り、課題です。主題者に質問することが不可能な状況にあることから、こちらに投稿させていただきました。お忙しいところ、ご回答ありがとうございました＾＾

この場をかりて失礼します。水が無限という仮定でのプログラムは一旦作りました＾＾；ヒントに関しましては、幾度も確認しましたが、「c<aかつc<b」のようです。模範解答もいくつか用意しているとのことだけに説得力があります。しかしながら、現時点では私の考える限り、上記の問題、ヒントからは解釈しようとしても様々な矛盾が出てきてしまいます。上記の問題とヒントで「こう解釈できる」というようなもので、思いつくようなことがございましたらご一報宜しくお願いいたします。

回答No.1

chokuto

アルゴリズムについてはなんともいえませんが、

> 例)a=6,b=4,c=6

については［操作(2) -> (3) -> (2) -> (4)］でいけるでしょう。
それから、

> 例)a=6,b=4,c=4
> (0,4,0)
> (4,0,0)
> 捨てる時に測るので、aは捨てる際満杯でなくてはならないため、
> これでは測れません。

捨てる際に a が満杯でなければなならないとは書かれていませんが。
あと、

> ヒント: c<aかつc<b なら量り出しは不可能である。

これは「c>aかつc>b なら量り出しは不可能」の間違いでは？

お礼

長文にもかかわらずお読みいただきありがとうございます。(2)の操作はやはりbを満杯に汲む操作なので提案していただいた(2)→(3)→(2)→(4)では不可能なようです
例)a=6,b=4,c=6
(0,4,2)-(2)
(4,0,2)-(3)
問題文にあるように二度目の(2)の際にbを「満杯に」量ることができません。私の文章が誤解を与えてしまったようです。誠に申し訳ありません。後述の部分については全くその通りです。ご指摘ありがとうございます。

ヒントに関しましては、何度も確認しましたが、「c<aかつc<b」のようです・・・
ご丁寧な回答ありがとうございました＾＾