0
0

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 025を解いてみる。「1000桁のフィボナッチ数」

Last updated at Posted at 2019-09-23

Project Euler 025

025

フィボナッチ数列は以下の漸化式で定義される:
Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1.
最初の12項は以下である.
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
12番目の項, F12が3桁になる最初の項である.
1000桁になる最初の項の番号を答えよ.

->次の問題

考え方

シンプルにフィボナッチ数列を順番に出力し、1000桁(10999)より大きくなるポイントまでループさせました。
フィボナッチ数列を生成するgeneratorは002で作っていましたが、このときは有限なループとしていたものを無限ループするように変更しました。
フィボナッチ数列の一般項にlog10なんかして計算したらもっと簡単にできるんでしょうか…

math_functions.py
def fibonacci_generator() -> int:
    """fibonacci数列を返すgenerator
    Returns:
        int: fibonacci数列を順に返す
    """
    last_result = 0
    result = 1
    while True:
        yield result
        result, last_result = result + last_result, result

コード

for文とfibonacci_generatorで無限ループを行い、1000桁を超えたところでループを抜けるようにしました。
Javaではループ内で宣言した変数(iやfibonacci_num)はループ外から参照できなかったですが、Pythonは関係なく参照できるんですね。

euler025.py
def main():
    n = 1000  # 1000桁になるのは
    end_point = 10 ** (n - 1)  # 1000桁以上になったら終了
    # enumurateを使いループの何番目かを取得
    for i, fibonacci_num in enumerate(fibonacci_generator()):
        if fibonacci_num > end_point:
            break
    print(f'{n}桁となるのは第{i+1}')  # iは0から始まるので+1


def fibonacci_generator() -> int:
    """fibonacci数列を返すgenerator
    Returns:
        int: fibonacci数列を順に返す
    """
    last_result = 0
    result = 1
    while True:
        yield result
        result, last_result = result + last_result, result
        

if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaで実行できるようにmath_funcitonsの関数部分も1つのコードに入れました(paizaで自作の関数をimportする方法よくわからない)

paizaにて実行
結果 1000桁となるのは第4782項 0.0007300376892089844 sec

0
0
3

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
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?