斐波那契程序在第 40 个任期后挂起

Question

我正在尝试解决这个问题

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Link: https://projecteuler.net/problem=2

下面是我必须计算斐波那契数的代码：

# fibonacci series
def fib(x):
    if x==0 or x==1:
        return 1                         
    else:
        return fib(x-1) + fib(x-2)

def test_fib(n):
    for i in range (n+1):
        print 'fib of', i, ' = ' , fib(i)

test_fib(41)

但是，程序在第 40 个学期后挂起。这段代码有什么问题，如何解决第 40 学期及以后的这个问题？

Answer 1

斐波那契算法的简单递归实现会很快变慢。有两种方法可以解决此问题：

a) 切换到迭代版本

def fib(x):
    if x==0 or x==1:
        return 1                         
    a = b = 1
    for _ in range(x-1):
        a, b = b, a+b
    return b

这不如递归解决方案优雅，但具有线性时间复杂度。

b) 使用记忆：

from functools import lru_cache

@lru_cache()
def fib(x):
    if x==0 or x==1:
        return 1                         
    else:
        return fib(x-1) + fib (x-2)

这是递归的解决方案，但带有 "memory"。如果您必须多次调用该函数，它还有一个比迭代版本更快的额外好处。

在 Python 的旧版本（例如 2.7）中，lru_cache 还不存在，但是您实现了一个足够我们使用的廉价副本：

def lru_cache():
    # second-order decorator to be a drop-in replacement
    def decorator(fn):
        cache = {}
        def wrapped(*args, **kwargs):
            if args in cache:
                return cache[args]
            val = fn(*args)
            cache[args] = val
            return val
        return wrapped
    return decorator

Answer 2

首先这是一个有效的斐波那契数生成器：

a,b = 0,1
print(a,b)
for x in range(0, 100):
    a,b = b, a + b
    print(b)

接下来您要做的就是：

a,b = 0,1
print(a,b)
for x in range(0, 100):
    a,b = b, a + b
    c = 0
    if b % 2 == 0:
        c = c + b
        print(c)

c 的最终迭代就是你的答案。

Answer 3

这将添加您的条款，直到 a 大于 400 万：

def fibo(n):
    i = 0
    a = 1
    b = 1
    sumEven= 0
    while i<n and a < 4000000:
        print ("fib of ", i, " = ", a)
        if(a % 2==0):
            sumEven+=a
        a,b = b, b+a
        i+=1
    print("sum of even: ", sumEven)

fibo(50)

Answer 4

considering the terms in the Fibonacci sequence whose values do not exceed four million

第34期超过400万，超过40期就不用了。问题已解决。

A naive recursive implementation of the fibonacci algorithm will get slow really fast. There's two ways you can resolve this:

第三种方法是使用非朴素的递归解决方案。你原来的一个问题是它是双重递归的：

return fib(x-1) + fib(x-2)

让我们将其简化为单个递归：

def fib(n, res=0, nxt=1):
    if n == 0:
        return res
    return fib(n - 1, nxt, res + nxt)

这让你过了第 40 个学期，在第 997 个递归方面触底。如果您需要更进一步，请考虑@L3viathan 的迭代或记忆解决方案，它们都非常出色。

斐波那契程序在第 40 个任期后挂起

fibonacci program hangs after 40th term

python

recursion

fibonacci