フィボナッチ！！
設問
Description:
The Fibonacci series is defined as: F(0) = 0; F(1) = 1; F(n) = F(n-1) + F(n-2) when n>1;. Given a positive integer 'n', print out the F(n).
Input sample:
The first argument will be a text file containing a positive integer, one per line. e.g.
5 12
Output sample:
Print to stdout, the fibonacci number, F(n).
e.g.
5 144
Submit your solution in a file (some file name).(py| c| cpp| rb| pl| php| tcl| clj| js| scala| cs| m) | fibonacci.java|fibonacci.scala or use the online editor.
始めは再帰で書きました
#! /usr/bin/env ruby def fib(n) (n < 2)? n : fib(n-2) + fib(n-1) end ARGF.lines do |line| puts fib(line.to_i) end
メモ化
RubyでFibonacci Seriesを解く -CodeEval - hp12c
こちらでメモ化する方法での解が書かれています。
@mem = { -2 => -1, -1 => 1 } fib = ->n{ ( @mem[n-1] ||= fib[n-1] ) + ( @mem[n-2] ||= fib[n-2] ) }
自分としては、この書き方の方が見やすく感じる。
def fib(n) @cache ||= [] @cache[n] ||= (n<2)? n : fib(n-2) + fib(n-1) end
メモ化前
inputを40ぐらいから凄い時間が掛かる。
$ time ruby fibonacci.rb input.txt 102334155 ruby fibonacci.rb input.txt 36.77s user 0.12s system 98% cpu 37.289 total
メモ化後
$ time ruby fibonacci.rb input.txt 102334155 ruby fibonacci.rb input.txt 0.01s user 0.00s system 88% cpu 0.018 total
雲泥の差。素晴らしい。
