鍋あり谷あり

テーマを決めずに適当に書いています。

バケツ問題1

数年前に某へなちょこで出した問題。

水がいっぱい入ったバケツ一個と、空のバケツがいくつかあり、それぞれのバケツの容量は正確にわかっている。この状態から指定された容量を量りとる、最小手数の手順を求めよ。
ただし

  • バケツからバケツに水を移す操作を1手と数える。
  • バケツからバケツに水を移す際は、注がれるバケツがいっぱいになるか、注ぐバケツが空になるまで行う。
  • 従って、水は一滴も漏れない。

例えば。バケツが3つ。10リットル,8リットル,3リットル。10リットルのバケツが満タンで、あとは空っぽ。ここから4リットル量りとりたい。
最小手数の手順は

  1. 10リットルのバケツから、3リットルのバケツに注ぐ
  2. 3リットルのバケツから、8リットルのバケツに注ぐ
  3. 10リットルのバケツから、3リットルのバケツに注ぐ

の3手(要するに、10リットルから3リットルを2回減じている)となる。
表示を短くするために、バケツに順に 0, 1, 2 と番号を振ると、
0→2, 2→1, 0→2
と、表示することができる。

なお:

  • 解がない場合はその旨を表示して終了すること
  • 最小手数の解が複数ある場合はその内ひとつを出力すればよい
  • オーバーフローや不正な入力は考慮しなくてもよい
  • バケツの容量も目的の容量も正の整数とする。

#ちなみに。rubyで書いたら40行足らず

実行例を以下に示す:(最初の数が目的の容量。次が満タンのバケツ。残りが空のバケツ)


>bucks 4 10 8 3
3 手 : 0→2 2→1 0→2

>bucks 5 10 7 6 3
6 手 : 0→3 3→1 0→2 2→1 1→0 0→3

>bucks 7 10 2 1
2 手 : 0→2 0→1

>bucks 5 10 6 4
解なし

>bucks 10 12 6 3
解なし

>bucks 50 98 76 54 32 1
8 手 : 0→2 2→4 4→1 2→4 4→3 2→4 4→1 2→4

>bucks 12 20 11 18 9
12 手 : 0→2 2→1 1→3 1→0 3→2 2→1 1→3 3→2 1→0 2→1 1→3 3→2

>bucks 123 314 15 92 65 35 89
8 手 : 0→3 3→4 4→5 0→2 2→4 0→1 4→5 0→5

>bucks 1000 1234 432 987
解なし

>bucks 50 1234 321 100
418 手 : 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2

>bucks 77 500 100 50 10 5 1
9 手 : 0→1 1→4 1→3 3→2 4→5 5→3 0→5 5→1 1→3

>bucks 567 1234 321 100
解なし

>bucks 1000 1028 1 2 3 4 5 6 7
7 手 : 0→7 0→6 0→4 0→1 0→5 0→2 0→3