#本題:Project Euler 002
002
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
->次の問題
考え方
まず、フィボナッチ数列を作ってみます。自然数の数列なのに一般項の公式だと√5とか出てくるらしいですね。
以前に参考書でgeneratorなるものを読んだので、generatorを使ってみようと思いました。
def fibonacci_generator(max_num: int) -> int:
"""
max_num未満のフィボナッチ数列を返すgenerator。
:param max_num: int
:return: int
"""
last_result = 1
result = 1
while result < max_num:
yield result
result, last_result = result + last_result, result
generatorが呼ばれるたびに1つ前(result)と2つ前(last_result)を足してresultに代入、同時に1つ前の値(result)を2つ前(last_result)に代入しています。このあたりの変数名にセンスの無さが出ています。
while result < max_num
のところをwhile True
にして無限にフィボナッチ数列を生成するgeneratorにもできますが、なんとなく無限ループが怖かったので有限なループにしました。
あとは内包表記を使ってlistやsetを作り、sum()で合計して完了です。
コード
from stop_watch import stop_watch
@stop_watch
def main():
num_set = set(i for i in fibonacci_generator(400 * 10000) if i % 2 == 0)
print(sum(num_set))
def fibonacci_generator(max_num: int) -> int:
"""
max_num未満のフィボナッチ数列を返すgenerator。
:param max_num: int
:return: int
"""
last_result = 1
result = 1
while result < max_num:
yield result
result, last_result = result + last_result, result
if __name__ == '__main__':
main()
結果 main処理時間: 4.601478576660156e-05 sec. 処理時間は0.000046秒程度でした。