ProjectEuler 002 フィボナッチ数列の和

早速だけど問題文

フィボナッチ数列の項は前の2つの項の和である。 最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万を超えない範囲で、偶数値の項の総和を求めよ。

Note:この問題は最近更新されました。お使いのパラメータが正しいかどうか確認してください。

フィボナッチ数列といえば数学ガールですよね。
え？わからない？これだからもう┐(´-｀)┌

定義としては

自分自身とその前の数を足したものが次の数になる(初期値は実は0,1)

ですね。問題文では1からスタートしてますが。

ということで一発目の解

def sum_of_even_fib (max)
  return (0..1/0.0).inject([1, 2]){|fib, i|
    fib[i] + fib[i + 1] < max ? fib << fib[i] + fib[i + 1] : (break fib) # break文の次に返却する値をつけて括弧で囲む必要あり
  }.select{|n|n % 2 == 0}.inject(&:+)
end
p sum_of_even_fib(10) # => 10
p sum_of_even_fib(4_000_000)

とりあえず問題文を再現するのが自分の癖。
検証する際はpryが便利です。

pry(main)> (0..10).inject([1, 2]){|fib, i| fib << fib[i] + fib[i + 1]}
=> [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

フィボナッチ数列はinjectととても相性がいいですね。
ただ問題文ではフィボナッチ数列を求める上限あるのでなんとかしないといけません。

ということでプログラムの解説。

最初の1/0.0は

pry(main)> 1/0.0
=> Infinity

そう、無限大です。injectに与えるレシーバーが(0..1/0.0)ということは0～無限大までinjectの処理を行うということです。
いわゆる無限ループならぬ、無限畳込み。

そのままだと終わらないで条件をつけてbreak（ループからの脱出を）させます。
injectでもちゃんとブレイクできる方法を試行錯誤して見つけました。

injectは最後に評価された値を次のループで引き継ぐ性質を持っているので、それさえ気をつければ安全です。
今回は三項演算子を使っています。
三項演算子は

条件文 ? 真の時に実行する処理 : 偽の時に実行する処理

を表す構文です。
injectの場合は最後に処理される値が重要だと書きましたが、breakするときも最後に評価される値をつける必要があります。
なんかreturnみたいな書き方になってますね。

これはもちろんif文を使って書くこともできます。

def sum_of_even_fib (max)
  return (0..1/0.0).inject([1, 2]){|fib, i|
    if fib[i] + fib[i + 1] < max
        fib << fib[i] + fib[i + 1]
    else
        break fib
    end
  }.select{|n|n % 2 == 0}.inject(&:+)
end
p sum_of_even_fib(10) # => 10
p sum_of_even_fib(4_000_000)

問題より400万未満の数までのフィボナッチ数列を求めればいいとわかるので上のようなif文になります。

inject文終了時にはfibというフィボナッチ数列が詰まった配列が返されるのでそこから偶数のものだけ"select"します。
selectはフィルタリングに便利ですね。

で、最後にinject(&:+)で加算処理。

一年前くらいのRubyの勉強を全然してないときにinject文をみたときは「Rubyなのに激キモ！」って思いましたが今でもその気持ちは変わってないですｗ

いや、むしろ最近は「PerlよりもRubyの方が気持ち悪く書ける」と思っているほどです。
上記のinject(:+)はほんの一例ですが。

ちなみにこの解答は以下のようにシンプルにも書けます。

MAX = 400_0000
sum = 0
a,  b = 1,  1
while a < MAX
  sum = sum + a if a.even?
  a,  b = a + b,  a
end
puts sum

Rubyっぽさは全くありませんが、どの言語のプログラマーでも読める綺麗なコードですよね。そしてこっちの方が高速です。

Rubyに慣れていればinjectやeachやselectなどのメソッドを使っている方が（たぶん）読み下しやすくなるのですが、遅くなってしまうケースが多いです。

パフォーマンスを気にする場合はwhileで逐次処理させる方が無難なときも。
正直ちゃんと速い関数を使えばPerlなどとも全然遜色ないパフォーマンスを引き出すので是非試してみて下さい。

今度はちゃんとベンチして見ようかな。

ということで今回はこれで終了。

ではでは