2018年7月23日月曜日

アルゴリズムパズル 2-4 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』という本の問題を解いてる.
初級編なので無限に簡単すぎてあまり面白みを感じられてない.
プログラムも短いのでまとめて問題2-4の実装例を貼っておく.

2. 実装例

この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので,ブログにパズルの内容について書くのは引用に収まるのか?という疑問があるので問題文は書かないです.

2.1. 手袋選び

最悪のケースだけ考えれば良いということに気づかなかったのは痛いが,手袋が左右違うというのは問題文に書いておくべきではと思った.
ヒントにあるとおり(a)はたまたま同じ側の手袋が出まくるケースを,(b)はたまたまたくさんある色が出まくってて,しかも片方の方の手袋が出まくるケースを考えれば良いですね.
そうするともうただ計算式を書くだけという感じなのでプログラムを書く必要ないな……という感じです.

2.2. 長方形の分割

数字やテキストの処理で済まないのではみたいな問題だったが再帰的に直角三角形を分割するプログラムをProcessingで書いた.
まぁ無限に分割の仕方はあるので本とは異なる実装にはなった(長方形をまず直角三角形に分割して,それぞれの三角形をint(n/2)個とn-int(n/2)個の直角三角形に分割するのを繰り返してる).
見た目は本よりも良さそうではあるが初級編なので著者は再帰関数を使わない手法にしたんだろうなぁと思うなどした.
実装のための計算で,ベクトルを幾何のベクトルとして触ったの何年ぶりだよという感じだった(そしてふつうに計算ミスしたりしてた).

2.3. 兵士の輸送

1人のケースについて考えればあとはそれをn人に適用するだけなのでプログラムを書くほどでもない……

3. 所感

こうやってブログに書くことで継続的にやるモチベーションを作ってるのだけど問題が簡単すぎるとモチベダウンがすごい.上級者向けは多分僕が逆立ちしても解けないんだろうけど.