Rubyのアルゴリズム練習がてらフィボナッチ数列を解いてみます。
フィボナッチ数列とは
まず最初にフィボナッチ数列について触れます。
フィボナッチ数列は
1, 1, 2, 3, 5, 8, 13, 21 ,,,
のように第n+2項が、 第n+1項と、第n項の和になるよう数列です。
事前準備
ネットで検索するとよく出てくるのが下記のようなメソッドを再帰的に呼び出す書き方です。しかし、これだと問題があります。
def fib(n) if n == 0 || n == 1 return 1 end fib(n - 2) + fib(n - 1) end
nの数が大きくなると、計算に時間がかかりすぎて終わらなくなってしまいます。（実際にirbなどで実行してみてください）
n=100の場合は、1秒間に100億回四則演算が可能なパソコンで400兆年かかってしまいます。笑
このプログラムをn=10000でも現実的な時間に処理できるよう書き換えてみましょう。
解答
def fibo(n) array_fibonatti = Array.new array_fibonatti[0] = array_fibonatti[1] = 1 for i in 2..n tmp = array_fibonatti[i - 1] + array_fibonatti[i - 2] array_fibonatti.push(tmp) end # 結果を表示 puts array_fibonatti end
この関数では、毎回計算をするのではなく、一度呼び出された結果を配列に格納しておくので、あとは同じ引数で呼び出された際にその格納された結果を返すだけ、という処理に変更しています。