プログラム脳を鍛える数学パズル 第四弾
どうも、小野氏です。
前回に引き続き、プログラム脳を鍛える数学パズルの問題を解いていきたいと思います。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者:増井 敏克
- 発売日: 2015/10/14
- メディア: 単行本（ソフトカバー）
今週は本書のQ11についてRubyで実装したので、そちらについて紹介いたします。
今回は、メモ化という手法について解説があったため、そちらをについても軽く触れていきたいと思います。
Q11 フィボナッチ数列
問題
フィボナッチ数列のうち、各桁の数字を足した数で割り切れる144より大きい数を、小さいほうから5個あげよ
いくらでも時間がかかっていいのであれば実装自体は難しくないのですが、何も考えずに再帰を使うと痛い目を見ます。
回答
自分で考えて実装したものが以下のものです。
やっていることは以下の通り。
- フィボナッチ数列を計算するメソッドの実装
- def Fibonacci_number(n)がそれにあたります
- 初期変数・回答を計算するための配列を宣言
- 配列の長さが9つになるまで、(フィボナッチ数列の計算結果)/(各桁の数字を足した数)の剰余が0のものを配列に追加
ちなみに二日かけても実行が終わらなかったので、途中で実行を中止しました。
(そのため、そもそも間違っている可能性も否めないです。)
解説
フィボナッチ数列の実装方法に絞って解説していきます。
フィボナッチ数列は以下の漸化式で定義することが出来ます。
そのため上述の式を愚直に実装すると、先述のコードのようになります。
ただ上述の方法で計算すると、同じ計算を複数回する必要があります。
下図は再帰でフィボナッチ数列の5番目の値を求める際の計算の流れをざっくり表したものです。
黄色の箇所について、まったく同じ計算を二度行っていることがわかると思います。
桁数が少ないときはこれでも問題がないのですが、nが大きくなると計算に時間にかかる時間が大きくなってしまいます。
そのため、同じ計算を二回行わないために、以下の二つの対策が考えられます。
それぞれの実装についてざっくり説明をしていきます。
メモ化
Wikipediaの定義は以下の通りです。
プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である
ざっくりいうと、すでに計算した値を保存しておくことを指すと理解しました。
計算値の格納先としては、可変長のものが好ましいので、リスト or ハッシュが良いかなと思います。
rubyで実装すると以下のようになります。
ボトムアップ型
再帰でフィボナッチ数列を解く場合、トップダウンでn項目の値を計算します。
具体的にいうと、5番目の項を求めるため4番目の項と3番目の項を計算していきます。
これをボトムアップで、つまり1番目の項と2番目の項を足し合わせ3番目の項を求めるという方法で、n番目の項を求めるという手法も考えられます。
こちらについてもメモ化と併用することで、回答を高速で計算できるようになります。
rubyで実装すると以下のようになります。
