Project Euler with Ruby on WSL [Problem 2]
例によって
ネタばれあり
問題
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.
私訳
1, 2 から始めるフィボナッチ数列の 400万 を超えない項について、偶数となる項の和を求めよ
解答方針
偶数が 3 つ周期、 (添え字 0 始まりとして) 3i + 1
番目に現れることはすぐわかる。
偶数+奇数 = 奇数, 奇数 + 奇数 = 偶数 だからだ
当初、フィボナッチ数列の一般項を使って、 等比数列の和の公式から計算しようかと思ったのだが、 逆に面倒(特に「400万を超えない」が)になってきて、 愚直に計算することにした。
# Project Euler # problem 2 def fib_array(upper) list = [1,2] while list.last < upper list.push(list[-1]+list[-2]) end # always list.last >= upper list.pop return list end arr = fib_array(4*1000*1000) sum = 0 for i in 0..((arr.length-1)/3) sum += arr[3*i+1] end puts sum