アルゴリズムパズル 6-7 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の6, 7番目の問題「行と列の入れ替え」の実装例です．

2. 解

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

2.1. 問題6 指数え

本の解説のとおりなのでまぁ実装する必要はない

2.2. 問題7 真夜中の橋渡り

1分の男を何回も酷使すればいけるのではと思ったら駄目だったので少し考えることになった問題．良問だと思うが一般的に解く方法は全探索しか思いつかない．
解説にあるが「橋とトーチ問題」という有名な問題でそこそこ研究されてるらしいが特に調べてないのでわからない．
なお今回のような「歩くのが遅いやつ二人をどこかで一緒に連れてく」という方法では最適解を得られない場合もある(例：5分 6分 6分 7分のひとがいる条件では一番渡るのが早いやつが懐中電灯を持ってひたすら往復するのが一番早い)

3. 所感

難易度はまだ低いがまぁよい．
プログラミングの能力というのはぶっちゃけアルゴリズムを考える能力や数学力によって上限が決まってしまうので，それをどう上げるかが大事だと思ってるのだけれど，それが上がってないのはよく感じる．
そう考えるといちいち実装する必要はないので，頭で解けば良い問題は頭で解いて，実装が楽しそうな問題だけ実装することにした．
ただし今後も1日～2日に1回はブログを更新するつもり．