基本情報技術者試験の矢沢久雄さんのテキストの中にアルゴリズム問題の例示として次の３Lと5Lのバケツを使って、4Lの水を計…

Question

基本情報技術者試験の矢沢久雄さんのテキストの中にアルゴリズム問題の例示として次の３Lと5Lのバケツを使って、4Lの水を計りなさい、という問題がありました。水の入れ替えなどには回数の制限はないということです。
ITエンジニアさんならば、こういう種類の問題は朝飯前なのでしょうか？
作業手順を考えることがプログラミングだということの説明の例としてあげられていました。
簡単に分かるものですか？

Answer 1

それはアルゴリズムではありません。アルゴリズムは「答え」ではなく「答えを出す手順」です。答えが出たならば、それはアルゴリズムではないのです。それはパズルです。

そしてこのパズルは、隠されたルールを暴く遊びです。隠されたルールとは即ち「二つのバケツを使って差の量の水を量ることが可能」というルールです。
このルールが無い限り解くことは不可能なので、このルールに気付くことを楽しむ遊びです。隠されたルールを見付けなければ解けないならば「アルゴリズム」ではあり得ません。

・Ｎ個のバケツがあり、それぞれは容量を持っている。
・バケツはその容量以下の水を保持することができる。
・バケツを満杯にすることで、そのバケツの容量の水を量ることができる。
・水は無限に使用出来る。
・バケツに保持されている水は捨てることができる。
・バケツＡとバケツＢとがある時、バケツＡに保持されている水をバケツＢへ移すことができる。この時、バケツＡにバケツＢ（に既に水が入っていた場合にはその分を差し引いた残り）の容量より多くの水が入っていたならば、バケツＢの水が一杯になる分の容量だけしかバケツＡの水は減らない。

この最後のルールが発見されない限りこのパズルは解けず、この最後のルールが発見された後はアルゴリズムを構築可能になります。

これを解くアルゴリズムは総当たりですね。いえ、A*探索アルゴリズムじゃないと拙いですね。ヒューリスティック関数が効率悪そうですが、（目的の水量マイナス全バケツの水の総量）の絶対値、とかならば機能するでしょうかね。あー、それでも無限ループが発生しますね。全バケツの保持水量でメモ化が必要ですね。

状態としては、Ｎ個のバケツ（容量と保持している水量）ですね。余談ながら、全部のバケツの最大公約数が水量の最小単位になります。
状態遷移は、バケツの水を満杯にする（Ｎ手）、バケツの水を捨てる（Ｎ手）、バケツの水を移動する（Ｎ*(N-1)手）の合計 N*(N+1) 通りですね。一手番で、この中のどれかを選ぶことになります。当然、満杯のバケツに水を入れたり空のバケツの水を捨てるのは無駄な行為ですので無条件で枝刈りするとして。
バケツがどれか一つでも目的の水量になったら終了。

これがアルゴリズムです。この手順を、バケツの個数と容量が明らかになった「パズル」に対して適用して計算します、計算機が。人間は計算しません。それがプログラムです。

Answer 2

あまりいい例えとは思いませんね。
問題の答えは、
1)5Lのバケツをいっぱいにして
2)その水を3Lのバケツがいっぱいになるよう移し、
3)3Lのバケツの水を一旦棄てて
4)5Lのバケツに残った2L相当の水を3Lのバケツに移し、
5)その後、5Lのバケツを満杯にして、
6)3Lのバケツの余っている部分に入れる
だと思いますが、これアルゴリズムですかね。むしろ人間向きのパズルだと思うのですが。

アルゴリズムというのは、例えば、「数字の10000から20000の間にある素数を抽出しなさい」といった、やろうと思えばできなくはないが、膨大な単純作業が発生するため、人力で行うのが現実的でないものを機械に行わせる場合の計算手順だと思うのですが違いますかね。

Answer 3

そういう「変な」制限下での手順を考える事は実際のプログラミングではあまりないですが、そういうパズル問題を苦にしないという意味では、適性を計れると思います。

Answer 4

>３Lと5Lのバケツを使って、4Lの水を計りなさい
こういう論理パズルが得意な人は適性があるというだけなので、あまり深く考えなくてもよいです。