Euler项目的非强力解决方案25

Question

项目欧拉问题25:

Fibonacci序列由递归关系定义:

F _n = F _n-1 + F _n-2,其中F _{1 = 1}且F ₂ = 1.因此前12项将是F ₁ = 1,F ₂ = 1,F ₃ = 2,F ₄ = 3 ,F ₅ = 5,F ₆ = 8,F ₇ = 13,F ₈ = 21,F ₉ = 34,F ₁₀ = 55,F ₁₁ = 89,F ₁₂ = 144

第12个学期F ₁₂是第一个包含三位数的术语.

Fibonacci序列中包含1000位数的第一项是什么？

我在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).

这是一个不会堆栈溢出并使用循环而不是递归的版本:

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)