project euler 25 fibonacci

2016-05-05 来源: zhourong1104 发布在  http://www.cnblogs.com/zhourong1104/p/5461880.html

数学方法:

Saying that a number contains 1000 digits is the same as
saying that it's greater than 10**999.

The nth Fibonacci number is [phi**n / sqrt(5)], where the
brackets denote "nearest integer".

So we need phi**n/sqrt(5) > 10**999

n * log(phi) - log(5)/2 > 999 * log(10)

n * log(phi) > 999 * log(10) + log(5)/2
n > (999 * log(10) + log(5) / 2) / log(phi)

A handheld calculator shows the right hand side to be
4781.8593, so 4782 is the first integer n with the
desired property.

Why bother with a computer on this one?

暴力:

import time
start = time.time()
sed_2 = 1
sed_1 = 1
for i in range(3,1000000):
    sed = sed_1 + sed_2
  #  print(sed)
    if  len(str(sed)) == 1000:
        res = i
        break
    sed_1,sed_2 = sed,sed_1

print(i)
print(time.time()- start)

>>>
4782
0.15599989891052246
>>> 

相关文章