Project Euler 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なんかして計算したらもっと簡単にできるんでしょうか…
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は関係なく参照できるんですね。
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