はじめに
今日からオライリーから出てるアルゴリズムパズルを解いていきます。
毎日何問解きます！この日までに全て解き終わります！などという高尚な目標はなく、しかもプログラムに活かせるだろうということも特に考えてはいないです。
そうただただパズルを解きたいからパズルを解くのです。
ということでこの文ではじめには終わりになるので今から初級パズルを順に解いていきたいと思います。
だいたい1記事で2~3問くらい解きたい。
(本当に今から解くので何時間いや何日空いてこの後の文が書き進められていくかは神の味噌汁である)
1. 狼とヤギとキャベツ
【問題内容】
- 1人の男、1匹の狼、1匹のヤギ、1玉のキャベツがある。
- 船で川の反対側に運ぶ
- 船には男とどれか一つしか乗せられない
- 男がいないと狼はヤギをヤギはキャベツを食べてしまう
【考察】
- 初手は条件よりヤギを運ぶしかない
- 2手目は当然男が帰ってくる
- 3手目はどちらを運んでも条件に引っかかるため4手目はヤギを戻すことが確定している
- ということは3手目はどっちでもいい
- 5手目は3手目で運んだ方と別の方を運ぶ(この時点で向こう岸に狼とキャベツが揃う)
- 6手目で男が帰って来て7手目でヤギを運べば終わり
【解答】
- 男,ヤギ→
- ←男
- 男,キャベツor狼→
- ←男,ヤギ
- 男,狼orキャベツ(3手目と別の方)→
- ←男
- 男,ヤギ→
よってしっかり運べる
【感想】
3手目以外は一意に決まるので難しくはない。ただ1問目にふさわしいThePazzleという問題だったと思います。
2. 手袋選び
【問題内容】
- 黒5,茶3,灰2の10組20個の手袋がある
- 暗闇で手袋を選ぶ,確認は選んだ後のみ
- (a)少なくとも1組の色が揃う
- (b)それぞれの色を少なくとも1組
- (a)(b)を保証するには最低いくつ手袋を選べばいいか
【考察】
- 最悪のパターンを考える問題
- 手袋なので右手と左手が揃わないと1組にならない
- 同じ側の手袋を引いている限りは絶対に揃わないのでまずそこを数える
- 黒5茶3灰2の右手だけまず引き続けたと仮定して10回,これが両条件の最低回数としてかかってくる
- (a)の場合,上の10回から何引いても揃う
- (b)の場合,上の10回から数の多い色より順に全部引き切れば最後まで灰色が揃わない
【解答】
(a)片方の手だけ引き続けて10回,そこから何引いても揃うので11回
(b)黒と茶色を全部引いて16回,灰色の片方の手だけを引いて18回,残りの２つはどちらを引いても揃うので19回
【感想】
高校生の数学の組み合わせの問題と似た雰囲気を感じました。ただ手袋が右手と左手があるというのが見落としやすいというかいやらしい。
長方形の分割
【問題内容】
- 長方形を分割して取り得る直角三角形の個数を全て求める
- アルゴリズムも示す
【考察】
- まず思いつくのは長方形を対角線で分割すると2つ直角三角形ができる
- 直角三角形は斜辺に対して逆の頂点から垂線を下ろせば2つの直角三角形に分割できる
- ちょっと表にまとめてみる(直角三角形を分割する場合)
| 分割回数 | n(直角三角形の数) |
|---|---|
| 1 | 3 |
| 2 | 4 |
| 3 | 5 |
| 4 | 6 |
| 5 | 7 |
| 6 | 8 |
| : | : |
- 最初だけ長方形を直角三角形に分割するので特殊なケースとして,その後は(n-2)回直角三角形を分割すればn個の直角三角形が得られる
【解答】
最初に長方形を分割し直角三角形を2つ作成した後は(n-2)回分割することでn個の直角三角形が得られる
【感想】
個人的にはしっくりこない感じの問題でした。ただ解答を見てもこんな感じの回答でした。解答欄にはもう１つ解答例があって少し複雑だが面白い発想だったのでそちら側の解答も思いつくようになりたいと思った。
おわりに
今日は3問解きました。最初だけあって簡単な問題が多かったです。ただパズルを考えるのは楽しいので満足しています。
こんな考え方もあるよっていう方がいましたらコメントくださると私が喜びます。
パズルを解くよりも久しぶりにQiitaを書くことに時間がかかりました。これで夜ご飯が食べられます。それでは。