水汲み問題
rimse (2003/06/27(Fri) 17:46:19)
容量がxリットルの赤い器とyリットルの青い器があります。
これらの器を持って川に水をくみに行きました。
これらの器を利用してどちらかの器にzリットルの水を入れてください。
というような感じの定番問題があります。
・もちろんx≠yとします。
・もちろんz≦xです。（クイズになりませんがz=xの場合もあるものとします）
・x,y,zともすべて正の整数値が入るものとします。
こういう問題で、何通りの水の量を量れるか求めることができるのでしょうか？
例えばx=3,y=2の場合、
・赤い器に水を汲んで3リットルの水を取り出せる
・青い器に水を汲んで2リットルの水を取り出せる
・赤い器に水を汲んで、その水を青い器に移せるだけ移すと赤い器に1リットルの水が残る
というわけで3通りの水の量を量れます。
しかし、x=1271,y=739というような大きな値になると何通りの水を量れるかを実践しながら調べていくのはものすごく大変です。
何通りの水を量れるかを計算か何かで求めることは可能でしょうか？
arc (2003/06/27(Fri) 18:45:21)
文章題の条件は、『x＜y x,y,zは自然数のとき、xリットルの容器とyリットルの容器を使い、zリットル残す』
ということですね。
普通に分かるのが、『ax , (x-)y-ax (y＞ax , 0≦a , aは整数) 』です。
何通りかを求める式はあるのでしょうかねぇ・・・？
何リットルが可能かはあると思いますが・・。
こんなんですみません・・・
失礼します。
rimse (2003/06/27(Fri) 22:02:34)
すみません。ひとつ書き忘れていた条件がありました。
・x>yとします。
というわけで
arcさん＞
『x>y x,y,zは自然数のとき、xリットルの容器とyリットルの容器を使い、zリットル残す』ということになります。
>何リットルが可能かはあると思いますが・・。
そちらでも構わないのでわかりましたら教えていただけないでしょうか。
Ａｚａｌｅａ (2003/06/27(Fri) 22:16:15)
そんなこといっていると
プログラム組むしかありませんね
任意の数という点で・・・
あと、実際にこのプログラムはあったと思いますから
何とかして実行してみましょう（ぇ
Ｃであれば何とかする自身ならありますが
そんなの組んでる時間など・・（以下略
きろろ (2003/06/27(Fri) 22:53:01)
ｘとｙの最大公約数をｇとおくと、
０以上ｘ以下であるｇの倍数はすべて可能ではないでしょうか。
それ以外は明らかに不可能です。
極端な話、ｘとｙが互いに素なら、０以上ｘ以下の全ての整数が可能になります。
（ｘとｙが互いに素なら、ｐｘ＋ｑｙ＝１を満たす整数ｐ、ｑが存在する
という事実を使って示せます。）
arc (2003/06/27(Fri) 22:49:05)
xとyを大きな素数などの複雑な数にしたら、可能なzがふえて式が複雑になってしまいました・・・。
解答を知りたいのであれば、言っちゃなんですが、数学掲示板にでもお書きください。
サイトは特定しませんが・・・。
私の知能では求められません・・・（滅
rimse (2003/07/01(Tue) 00:39:33)
みなさん回答ありがとうございます。
みなさんの回答をもとに自分でプログラムを組もうと思いましたが
そもそも公約数の求め方すらわからないじゃないかということで
早々と断念しました。
nak (2003/07/05(Sat) 01:02:07)
グーグルで、「最大公約数」＆「プログラム」で検索
http://www.google.co.jp/search?sourceid=navclient&hl=ja&ie=UTF-8&oe=UTF-8&q=%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0+%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0
済みつけてもいいんですよね？
rimse (2003/07/05(Sat) 02:31:55)
nakさん、回答ありがとうございます。
最小公倍数の求め方はわかっても、
「何リットルが可能か調べる方法」の正確な答えが出ていなくて、
arcさんのおっしゃるとおり他の掲示板の掲示板で質問した方が回答が得られやすいようなので
この掲示板での質問はあきらめて、
あらためて「済」とさせていただきます。
※ 問題中に使用されている人名、地域名、会社名、組織名、製品名、イベントなどは架空のものであり、実在に存在するものを示すものではありません。
