CodeIQ「ディビジョン・ナイン」問題を解いてみた。スマートフォン用の表示で見るいものやま。雑多な知識の寄せ集め2016-04-16CodeIQ「ディビジョン・ナイン」問題を解いてみた。RubyCodeIQで出題された「ディビジョン・ナイン」問題。https://codeiq.jp/q/2561Rubyで解いてみたので、コードを公開してみる。このとき、9の倍数となるものを考えましょう。あれば、234、333、441、などが9の倍数です。1から4の全ての数字を使う必要はありません。なることが確かめられます。値を出力するプログラムを書いてください。自分の解答9の倍数の判定は簡単で、各桁の数字を足して9で割り切れれば、9の倍数。対して、9で割り切れる数が何個あるかを返すもの。あれば、111x(xは1〜4の数字)という数のうち9で割り切れるものの個数が返ってくる。1の場合は、使うことにした数字を全て足して9で割った余りが5〜8の間に入っていれば、9で割り切れる数を作ることができる。割った余りが5になっていれば、最後の1つの数字として4を使えば、9で割り切れる数になる。いう場合には1を、そうでない場合には0を返している。2以上の場合は、使う数字を1つ固定して再帰呼び出しすれば、1〜4を使った場合のそれぞれの9で割り切れる数の個数が分かるので、それを合計して返せばいい。いうことで、論理的にはこれでOKなんだけど、実際に実行すると、めちゃくちゃ時間がかかる(^^;そこで、もうちょっと高速化を。とき)に足し算を行っているけど、実際に必要なのは、各桁で使うことにした数字の合計を9で割った余りだけ。0)は各桁で使うことにした数字の合計を9で割った余り。足して9で割った余りを渡すようにしている。これで配列を生成するコストは減ったけど、まだまだ遅い。あることを考えると、同じ引数での関数呼び出しが何度も行われている可能性が高い。なれば、キャッシュを使ってやればかなり高速化するはず。各引数に対するキャッシュを用意して、まだ求まっていないところにはnilを入れてある。値は分かってるので、最初から入れてある。1かそうでないかの判定は不要になり、キャッシュに値があればその値を返し、そうでなければ値を求めてキャッシュに値を保存し、その値を返せばいいだけになる。これで十分に速くなったので、用意されたテストケースもちゃんと時間内に解けるようになった。ちなみに、これは動的計画法になってるみたい。確かに、1つの桁の数字を決めてより小さい問題を解いていて(分割統治法)、また、より小さい問題のそれぞれの結果をキャッシュしてる(メモ化)。動的計画法という名前自体は(ナップザック問題などで)知っていたけど、具体的なアルゴリズムのイメージは掴めてなかったので、自分の書いたコードが振り返ってみれば動的計画法になっていたというのは、ちょっと変な感じ。強化学習の動的計画法とは、かなり違うしね。補足しておくと、強化学習の動的計画法の方は、状態関数の値を他の状態関数の値を使って求めていて(ブートストラップ)、各状態関数の値を保存している(メモ化)という意味では、(定義次第では)動的計画法の条件を満たしていると言えなくもない。関数の各値の関係を有向グラフにしたときにループが存在することがあるので、再帰で解くことが出来るとは限らない。(つまり、厳密に言うと、より小さい部分問題に分割出来るとは限らない)そこで、(ループしていない場合も)再帰を使って解くのではなく、ヤコビ法で反復を使って問題を解いている。ナップザック問題を解く動的計画法と、強化学習の動的計画法だと、かなりイメージが違う感じ。20:00CodeIQ「ディビジョン・ナイン」問題を解いてみた。Language」を翻訳してみた。