高效地计算斐波那契数列

Question

高效地计算斐波那契数列

69

我正在解决一个Project Euler问题：求偶斐波那契数列的总和。

我的代码：

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]

通过打印sum（list2），可以轻松找到问题的解决方案。然而，我猜想生成list2需要很长时间。有没有办法使这个过程更快？或者这样做也可以吗...

(问题：通过考虑斐波那契数列中不超过四百万的值，找出偶数值项的总和。)

- user65165

P.S. 我是通过尝试找到不超过400万的值的。 - user65165

提示：尝试阅读维基页面... - Mitch Wheat

不，Fibonacci数列的维基页面... - Mitch Wheat

1

简单递归仅以 O(phi^n) 运行。 - recursion.ninja

你可以在 O(log n) 的时间复杂度内计算它。请参阅子线性时间内的第n个斐波那契数。 - jfs

1

Project Euler的Even Fibonacci numbers问题是关于“偶数值项”，而不是“具有偶数序号/对于偶数参数/在偶数索引处的值”。如果您可以找到小于边界（“Problem 2”中的“四百万”）的最大项的序号，您可以在一次斐波那契函数的计算中找到该总和。 - greybeard

34个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vishwaraj · Answer 1

这里有一个使用字典优化的解决方案

def Fibonacci(n):
    if n<2 : return n
    elif not n in fib_dict :
            fib_dict[n]= Fibonacci(n-1) + Fibonacci(n-2)
    return fib_dict[n]

#dictionary which store Fibonacci values with the Key
fib_dict = {}
print(Fibonacci(440))

- ranjith chilupuri · Answer 2

Project Euler 是一个练习编程的好地方。

回到您的问题...

斐波那契数列; 将倒数第二个数字与最后一个数字相加，得到的和就是数列中的新数字。

虽然您已经定义了一个函数，但最好使用 while 循环。

i = 0
x = [0,1,2]
y =[]
n = int(input('upper limit of fibonacci number is '))
while i< n:
    z= x[-1]+x[-2]
    x.append(z)
    if z%2 == 0:
        y.append(z)
    i = x[-1]
    print(i)
print('The sum of even fibbunacci num in given fibonacci number is ',sum(y)+2)

- Prokhozhii · Answer 3

这比上面所有的都要快得多

from sympy import fibonacci
%timeit fibonacci(10000)

262 ns ± 10.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

- Manoj Nawathale · Answer 4

int count=0;
void fibbo(int,int);

void main()

{

fibbo(0,1);

    getch();
}

void fibbo(int a,int b)

{

 count++;

 printf(" %d ",a);

if(count<=10)

     fibbo(b,a+b);

else

      return;

}