Problem 2 - Project Euler

Project Euler の2問目は

フィボナッチ数列の項が400万を超えない範囲で、偶数の項の総和を求める

という問題です。

フィボナッチ数列の一般項

フィボナッチ数列の一般項は以下の通りです。

Fn=\frac{1}{\sqrt{5}}\{\(\frac{1+\sqrt{5}}{2}\)^{n}-\(\frac{1+\sqrt{5}}{2}\)^{n}\}

別に数学が得意というわけではないんですが、ちょうど数学ガールを読んでてコレが出てきたのでせっかくだからこれを使用してみようと思います。

mathモジュール

Python平方根を使用するためにはmathモジュールのsqrt関数を使用します。mathモジュールには他にも高度な計算のための関数が色々用意されてるので、今後も何かとお世話になりそうです。

解いてみたものの…

一応は解けましたが、なんかもっと簡潔に書けそうな気がしなくもないですね。

#-*- coding: utf-8 -*-
import math

# 変数r5に5の平方根を代入
r5 = math.sqrt(5)

def fib(m, n=0, ans=0):
    # フィボナッチ数の一般項を求める
    term = int((1 / r5) * ((((1 + r5) / 2) ** n) - (((1 - r5) / 2) ** n)))
    # m未満かつ偶数の場合
    if term < m and term % 2 == 0:
        ans += term
        fib(m, n+1, ans)
    # m未満かつ奇数の場合
    elif term <m:
        fib(m, n+1, ans)
    # termがm以上になったらansを表示
    else:
        print ans

>>> fib(4000000)
4613732

Pythonとは思えないくらいカッコだらけですね。