【Project EulerにRubyで挑戦シリーズ】問2:Even Fibonacci numbers

スポンサーリンク

Project Eulerとは

Project Euler(プロジェク オイラー)と読みます。
オイラー関数のオイラーさんですね。懐かしい…

その名の通り、数学的なプログラムが掲載されている問題集サイトです。
2018年9月29日時点で627問が掲載されています。
会員登録して回答を提出していくとレベルが上っていくそうです。

問題を解くために利用するプログラミング言語は何を使っても良いので
Ruby ver 2.5.1を使っていきます。

今回の問題

Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
数列の項の値が400万以下の, 偶数値の項の総和を求めよ。

書いた内容

とりあえず解いてみる

400万以下のフィボナッチ数列を配列として取り出せれば
問1の要領でselectとinjectのメソッドチェーンで偶数項の総和は出せます。
ということでフィボナッチ数列の配列を作ろうと色々実験。

fibonacci_sequence = [1, 2]
fibonacci_sequence << fibonacci_sequence[0] + fibonacci_sequence[1]
p fibonacci_sequence #=> [1, 2, 3]
fibonacci_sequence << fibonacci_sequence[1] + fibonacci_sequence[2]
p fibonacci_sequence #=> [1, 2, 3, 5]

配列に足す部分を一般化したい

フィボナッチ数列は隣接三項間漸化式なので
配列最後部の2項を足して配列に加えていけばよかった。

fibonacci_sequence = [1, 2]
fibonacci_sequence << fibonacci_sequence[-2, 2].inject(:+)
p fibonacci_sequence #=> [1, 2, 3]

ループの生成

ループを入れて400万以下のフィボナッチ数列を作成。

fibonacci_sequence = [1, 2]

loop do
  n = fibonacci_sequence[-2, 2].inject(:+)
  break if n > 4000000
  fibonacci_sequence << n
end

p fibonacci_sequence
#=> [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578]

最終型

偶数だけ抽出して足し上げるロジックは問1と同様。
求める解は 4,613,732 のようです。

fibonacci_sequence = [1, 2]

loop do
  n = fibonacci_sequence[-2, 2].inject(:+)
  break if n > 4000000
  fibonacci_sequence << n
end

puts fibonacci_sequence.select{ |n| n % 2 == 0 }.inject(:+) #=> 4613732

※Project Eulerのリポジトリ

          
    

スポンサーリンク

  
Scroll Up