# Fibonacci Series

CodeEval

フィボナッチ！！

#### 設問

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```