桁数1000になる最小のフィボナッチ数は何番目
http://projecteuler.net/index.php?section=problems&id=25
問題。
桁数1000になる最小のフィボナッチ数は何番目。
普通に再帰だと遅かったので、辞書を使う。
# -*- coding:utf-8 -*- fib = {1:1,2:1} def Fibonacci(n): if n in fib.keys(): return fib[n] else: fib[n] = Fibonacci(n-1) + Fibonacci(n-2) return fib[n] def CountDigits(d): m = 1 while True: f = Fibonacci(m) if len(str(f)) == d: return m m += 1 print CountDigits(1000)