python - 欧拉计划的非蛮力解决方案 25

Question

Project Euler problem 25 :

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F_{1 = 1} and F₂ = 1. Hence the first 12 terms will be F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, F₁₁ = 89, F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

我用 Python 做了一个蛮力解决方案，但计算实际解决方案绝对需要很长时间。任何人都可以提出一个非暴力解决方案吗？

def Fibonacci(NthTerm):
    if NthTerm == 1 or NthTerm == 2:
        return 1 # Challenge defines 1st and 2nd term as == 1
    else:  # recursive definition of Fib term
        return Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)

FirstTerm = 0 # For scope to include Term in scope of print on line 13
for Term in range(1, 1000): # Arbitrary range
    FibValue = str(Fibonacci(Term)) # Convert integer to string for len()
    if len(FibValue) == 1000:
        FirstTerm = Term
        break # Stop there
    else:
        continue # Go to next number
print "The first term in the\nFibonacci sequence to\ncontain 1000 digits\nis the", FirstTerm, "term."

Answer 1

您可以编写一个以线性时间运行且内存占用量恒定的斐波那契函数，您不需要列表来保存它们。 这是一个递归版本(但是，如果 n 足够大，它将只是 stackoverflow )

def fib(a, b, n):
    if n == 1:
        return a
    else: 
        return fib(a+b, a, n-1)


print fib(1, 0, 10) # prints 55

此函数仅调用自身一次(导致大约 N 次调用参数 N)，与调用自身两次(大约 2^N 次调用参数 N)的解决方案形成对比。

这是一个永远不会出现 stackoverflow 并使用循环而不是递归的版本:

def fib(n):
    a = 1
    b = 0
    while n > 1:
        a, b = a+b, a
        n = n - 1
    return a

print fib(100000)

这已经足够快了:

$ time python fibo.py 
3364476487643178326662161200510754331030214846068006390656476...

real    0m0.869s

但是调用 fib 直到得到足够大的结果并不完美:系列的第一个数字被计算了多次。 您可以计算下一个斐波那契数并在同一循环中检查其大小:

a = 1
b = 0
n = 1
while len(str(a)) != 1000:
    a, b = a+b, a
    n = n + 1
print "%d has 1000 digits, n = %d" % (a, n)