0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Project Euler 002を解いてみる。generator関数を使ってみる。「偶数のフィボナッチ数」

Last updated at Posted at 2019-09-02

#本題:Project Euler 002
002

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

->次の問題

考え方

まず、フィボナッチ数列を作ってみます。自然数の数列なのに一般項の公式だと√5とか出てくるらしいですね。
以前に参考書でgeneratorなるものを読んだので、generatorを使ってみようと思いました。

euler002.py
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()で合計して完了です。

コード

euler002.py
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秒程度でした。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?