[Python][Julia]Project euler2 (プロジェクトオイラー2)

Project euler Ploblem 2 (プロジェクトオイラー2)

Even Fibonacci Numbers

備忘のために残しておく。

問題文

フィボナッチ数列において、新しい項は前2項を足したもので生成される。
1と2から始めた場合、最初の10項は以下の通りである。
1,2,3,5,8,13,21,34,55,89,...
400万を超えない値のフィボナッチ数列の項を考えたとき、値が偶数の項の合計を求めよ。

(原文)

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.

答え

4613732

解答の方針

問題文の通り、フィボナッチ数列を作り、偶数の値の項を足していく。

Pythonのコード

Python(Ploblem2)

# フィボナッチ数列を作る
def fibonacci(n: int) -> int:
    if n == 1: return 1
    elif n == 2: return 2
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# 偶数の値の項のみ足す
def even_fibonacci_sum(limit: int) -> int:
    sum: int = 0
    n: int = 1
    while fibonacci(n) < limit:
        if fibonacci(n) % 2 == 0:
            sum += fibonacci(n)
        n += 1
    return sum

print(even_fibonacci_sum(4000000))

Juliaのコード

Julia(Ploblem2)

# フィボナッチ数列を作る
function fibonacci(n::Int64)::Int64
    if n == 1 
        return 1
    elseif n == 2
        return 2
    else
        return fibonacci(n-1) + fibonacci(n-2)
    end
end

# 偶数の値の項のみ足す
function even_fibonacci_sum(limit::Int64)::Int64
    sum::Int64 = 0
    n::Int64 = 1
    while fibonacci(n) < limit
        if fibonacci(n) % 2 == 0
            sum += fibonacci(n)
        end
        n += 1
    end
    return sum
end

println(even_fibonacci_sum(4000000))

追記

再帰関数をメモ化した例

参考：Pythonによるフィボナッチ数列の色々な求め方(一般項、反復法、再帰法)

Python 追記分

def fibonacci_memo(n: int, memo={}):
    if n == 1: return 0
    elif n == 2: return 1
    elif n in memo: return memo[n]
    else:
        memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
        return memo[n]
    
def even_fibonacci_sum_memo(limit: int) -> int:
    sum: int = 0
    n: int = 1
    while fibonacci_memo(n) < limit:
        if fibonacci_memo(n) % 2 == 0:
            sum += fibonacci_memo(n)
        n += 1
    return sum

print(even_fibonacci_sum_memo(4000000))

###　追記2 
ジェネレータ関数を用いた場合
(コメントいただきありがとうございます)

```Python: Python
from collections.abc import Iterator

def fibonacci(n: int) -> Iterator[int]:
    """フィボナッチ数列をイテレートする"""
    a, b = 1, 2
    while a < n:
        yield a
        a, b = b, a + b

def even_fibonacci_sum(limit: int) -> int:
    """偶数の値のフィボナッチ数のみ合計する"""
    return sum(n for n in fibonacci(limit) if n % 2 == 0)

print(even_fibonacci_sum(4000000))