アルゴリズム強化したいなと思っていたところ本屋で見かけたので買いました。
この本はアルゴリズム的なパズルを集めた本です。アルゴリズム的なパズルというのは、問題を解くためのはっきりと定義された手順を(明示的あるいは暗黙に)扱うパズルです。
150問載っているので今日からちまちま解いていこうと思います。
狼と山羊とキャベツ(A wolf, a Goat, and a Cabbage)
記念すべき1問目
・ある男が狼1頭、山羊1頭、キャベツ一玉と一緒に川岸にいる
・男はそれらすべてを川の反対側に運ばなければならない
・舟には自分以外にどれか一頭または一玉しか乗せられない
・男がいないと狼は山羊を、山羊はキャベツを食べてしまう
・どうすれば男はすべての「乗客」を川の反対側に運べるか
これは似たような問題を見たことがある気がする。
解答としては以下のような感じでしょうか。
- 山羊を向こう岸に運ぶ
- 戻る
- 狼を向こう岸に運ぶ
- 山羊を連れて戻る
- キャベツを向こう岸に運ぶ
- 戻る
- 山羊を向こう岸に運ぶ
うん、正解でした。手順3と5は逆でも問題ないですね。そこ以外は他に選択肢が無く解説にもこんな簡単なパズルは中々ないと書かれていました。
思ったより短く終わったので目次を眺めていたところ42問目に「もう1つの狼と山羊とキャベツのパズル」というのがありました。こういうの熱いですね、燃えです。問題を見たい衝動に駆られましたが今日はこれでおしまいです。