logo标签列表

高效地计算斐波那契数列

pythonperformancealgorithmfibonacci
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需要很长时间。有没有办法使这个过程更快？或者这样做也可以吗...

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

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个回答
151

是的，原始递归解决方法需要很长时间。这是因为对于每个计算的数字，它都需要多次计算之前的所有数字。看一下以下图片。

表示斐波那契数列计算的树形图

它表示使用您的函数计算Fibonacci(5)。正如您所看到的，它计算了Fibonacci(2)的值三次，以及Fibonacci(1)的值五次。随着您要计算的数字越来越高，这种情况只会变得更糟。

让它变得更加糟糕的是，在计算列表中的每个斐波那契数时，您不使用已经知道的先前数字来加速计算-每个数字都是“从头开始”计算的。

有几种方式可以使此过程更快：

1. 从下到上创建列表

最简单的方法就是创建一个斐波那契数列表，直到您想要的数字为止。如果这样做，您就可以“从下到上”或者说另一种说法是“自底向上”构建，可以重复使用先前的数字来创建下一个数字。如果您有一个斐波那契数列表[0, 1, 1, 2, 3]，您可以使用该列表中的最后两个数字来创建下一个数字。

这种方法看起来会像这样：

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

然后你可以通过执行以下操作获得前20个斐波那契数：

>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

或者您可以通过以下方法从前40个斐波那契数列中获取第17个数字：

>>> fib_to(40)[17]
1597

2. 记忆化（相对高级的技术）

另一个加速算法的选择是使用记忆化，不过它比较复杂。由于你已经计算过的值再次出现时需要重新计算，因此你可以把这些已经计算的值保存在字典中，在重新计算之前首先尝试从字典中获取这些值。这就是所谓的“记忆化”。代码可能类似于：

>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]

这使你能够轻松地计算大的斐波那契数：

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

事实上，这是一种非常常见的技术，Python 3 包含一个装饰器可以为你执行该操作。我向你展示自动缓存！

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

这个函数与先前的函数做的事情基本相同，但所有computed相关的东西都由lru_cache修饰器处理。

3.仅仅是简单地计数（一个朴素的迭代解决方案）

第三种方法是Mitch建议的，只需计算而不保存列表中的中间值。你可以想象进行如下操作

>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a
我不建议使用这最后两种方法，如果你的目标是创建一个斐波那契数列。使用 fib_to(100) 比 [fib(n) for n in range(101)] 要快得多，因为后者仍然需要从头开始计算列表中的每个数字。
1
@will 那不就成了第一个函数吗？（除了你只能从中取一次值，而且你不能对其进行索引。） - kqr
非常好的全面回答。使用可变默认参数作为备忘录是我最喜欢的 Python 技巧之一。您还可以提到斐波那契数的 闭合形式 表达式。 - wim
这份全面的答案中缺少一个使用生成器计算前n个偶斐波那契数的解决方案。但是，您可以在我的下面的答案中找到一种实现方式。@kqr：为什么LRU缓存装饰器比手动制作的记忆化解决方案慢得多？ - CodeManX
@CoDEmanX 无聊的答案：手工制作的缓存是专门为任务设计的，因此通过能够完全忽略很多边缘情况来实现更好的性能。修饰符应该对任何带有任何一组参数的函数调用进行正确处理，这会消耗很多计算周期。有趣的答案：尽情发挥吧：https://fossies.org/dox/Python-3.4.3/functools_8py_source.html#l00438 - kqr
3
记忆化将返回大型集合。在斐波那契函数中， 计算过的 [n] 会被赋值为 fib(n-1, computed) + fib(n-2, computed)。 这一行代码会重复出现995次。 递归错误：超过了最大递归深度。 - Alexandros Spyropoulos
显示剩余11条评论
79

这是一个非常快速的算法，可以比其他答案中介绍的简单迭代方法更快地找到第n个斐波那契数，虽然它相当先进：

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

你可以在这里阅读更多有关涉及数学的内容。

我在哪里可以找到第一种方法的数学解释来源？ - previous_developer
2
你可以在这里阅读有关数学的详细信息：http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form。我的算法使用快速幂将矩阵提高到n次方。 - Piotr Dabkowski
5
太晦涩难懂了。我不建议新手使用这个解决方案。 - Ali Arda Orhan
它比简单的闭合形式更快吗？https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding - leitasat
4
@leitasat 可能是这样，但对于较大的 n 值也会不正确，因为 Python 的 float 是有限精度的，不像 int。 - Hubert Kario
显示剩余2条评论
16

Python不会优化尾递归，因此在这里呈现的大多数解决方案如果n太大（当我说太大时，我是指1000），将会出现“Error: maximum recursion depth exceeded in comparison”的错误。

递归限制可以增加，但这将导致Python在操作系统中栈溢出而崩溃。

请注意，fib_memo/fib_local和fib_lru/fib_local_exc之间的性能差异：LRU缓存要慢得多，甚至对于n = ~500也无法完成，因为它已经产生了运行时错误：

import functools
from time import clock
#import sys
#sys.setrecursionlimit()

@functools.lru_cache(None)
def fib_lru(n):
    if n < 2:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

def fib_memo(n, computed = {0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
    return computed[n]

def fib_local(n):
    computed = {0: 0, 1: 1}
    def fib_inner(n):
        if n not in computed:
            computed[n] = fib_inner(n-1) + fib_inner(n-2)
        return computed[n]
    return fib_inner(n)

def fib_local_exc(n):
    computed = {0: 0, 1: 1}
    def fib_inner_x(n):
        try:
            computed[n]
        except KeyError:
            computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
        return computed[n]

    return fib_inner_x(n)

def fib_iter(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def benchmark(n, *args):
    print("-" * 80)
    for func in args:
        print(func.__name__)
        start = clock()
        try:
            ret = func(n)
            #print("Result:", ret)
        except RuntimeError as e:
            print("Error:", e)
        print("Time:", "{:.8f}".format(clock() - start))
        print()

benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)

结果：

fib_iter
Time: 0.00008168

fib_memo
Time: 0.00048622

fib_local
Time: 0.00044645

fib_local_exc
Time: 0.00146036

fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552

迭代解法是最快的方法，即使对于 n=100k 也不会导致堆栈损坏（0.162秒）。 它确实不返回中间的斐波那契数。

如果要计算第 n 个偶数斐波那契数，可以像这样调整迭代方法：

def fib_even_iter(n):
    a, b = 0, 1
    c = 1
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            c += 1
    return a

如果你对途中的每个偶数都感兴趣，可以使用一个生成器：

def fib_even_gen(n):
    a, b = 0, 1
    c = 1
    yield a
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            yield a
            c += 1
    return a

for i, f in enumerate(fib_even_gen(100), 1):
    print("{:3d}.  {:d}".format(i, f))

结果：

  1.  0
  2.  2
  3.  8
  4.  34
  5.  144
  6.  610
  7.  2584
  8.  10946
  9.  46368
 10.  196418
 11.  832040
 12.  3524578
 13.  14930352
 14.  63245986
 15.  267914296
 16.  1134903170
 17.  4807526976
 18.  20365011074
 19.  86267571272
 20.  365435296162
 21.  1548008755920
 22.  6557470319842
 23.  27777890035288
 24.  117669030460994
 25.  498454011879264
 26.  2111485077978050
 27.  8944394323791464
 28.  37889062373143906
 29.  160500643816367088
 30.  679891637638612258
 31.  2880067194370816120
 32.  12200160415121876738
 33.  51680708854858323072
 34.  218922995834555169026
 35.  927372692193078999176
 36.  3928413764606871165730
 37.  16641027750620563662096
 38.  70492524767089125814114
 39.  298611126818977066918552
 40.  1264937032042997393488322
 41.  5358359254990966640871840
 42.  22698374052006863956975682
 43.  96151855463018422468774568
 44.  407305795904080553832073954
 45.  1725375039079340637797070384
 46.  7308805952221443105020355490
 47.  30960598847965113057878492344
 48.  131151201344081895336534324866
 49.  555565404224292694404015791808
 50.  2353412818241252672952597492098
 51.  9969216677189303386214405760200
 52.  42230279526998466217810220532898
 53.  178890334785183168257455287891792
 54.  757791618667731139247631372100066
 55.  3210056809456107725247980776292056
 56.  13598018856492162040239554477268290
 57.  57602132235424755886206198685365216
 58.  244006547798191185585064349218729154
 59.  1033628323428189498226463595560281832
 60.  4378519841510949178490918731459856482
 61.  18547707689471986212190138521399707760
 62.  78569350599398894027251472817058687522
 63.  332825110087067562321196029789634457848
 64.  1409869790947669143312035591975596518914
 65.  5972304273877744135569338397692020533504
 66.  25299086886458645685589389182743678652930
 67.  107168651819712326877926895128666735145224
 68.  453973694165307953197296969697410619233826
 69.  1923063428480944139667114773918309212080528
 70.  8146227408089084511865756065370647467555938
 71.  34507973060837282187130139035400899082304280
 72.  146178119651438213260386312206974243796773058
 73.  619220451666590135228675387863297874269396512
 74.  2623059926317798754175087863660165740874359106
 75.  11111460156937785151929026842503960837766832936
 76.  47068900554068939361891195233676009091941690850
 77.  199387062373213542599493807777207997205533596336
 78.  844617150046923109759866426342507997914076076194
 79.  3577855662560905981638959513147239988861837901112
 80.  15156039800290547036315704478931467953361427680642
 81.  64202014863723094126901777428873111802307548623680
 82.  271964099255182923543922814194423915162591622175362
 83.  1152058411884454788302593034206568772452674037325128
 84.  4880197746793002076754294951020699004973287771475874
 85.  20672849399056463095319772838289364792345825123228624
 86.  87571595343018854458033386304178158174356588264390370
 87.  370959230771131880927453318055001997489772178180790104
 88.  1571408518427546378167846658524186148133445300987550786
 89.  6656593304481317393598839952151746590023553382130993248
 90.  28197781736352815952563206467131172508227658829511523778
 91.  119447720249892581203851665820676436622934188700177088360
 92.  505988662735923140767969869749836918999964413630219877218
 93.  2143402371193585144275731144820024112622791843221056597232
 94.  9079598147510263717870894449029933369491131786514446266146
 95.  38461794961234640015759308940939757590587318989278841661816
 96.  162926777992448823780908130212788963731840407743629812913410
 97.  690168906931029935139391829792095612517948949963798093315456
 98.  2923602405716568564338475449381171413803636207598822186175234
 99.  12384578529797304192493293627316781267732493780359086838016392
100.  52461916524905785334311649958648296484733611329035169538240802

Time: 0.00698620

这是前100个偶数斐波那契数列的结果，用时约7毫秒，包括在终端打印的开销（在Windows上很容易低估）。

2
+1 是因为在这个问题中介绍了[生成器]。 （您可以使用a，b = 0，2和a，b = b，a + 4 * b直接生成偶数项。） - greybeard
我用Ruby制作了一个简单的示例，代码如下：(n - 1).times.reduce([0, 1]) { |array| [array[1], array[0] + array[1]] }.last - Victor Castro
@greybeard：谢谢，这对于 n = 100k (在禁用控制台输出的情况下，时间从12.5秒缩短到了0.6秒)确实有很大的影响。 - CodeManX
7

基于 fib(n) = fib(n-1)+fib(n-2) 这个事实，直接的解决方案是

def fib(n):
    if (n <=1):
        return(1)
    else:
        return(fib(n-1)+fib(n-2))

然而，这里的问题在于某些值被计算了多次，因此效率非常低下。原因可以从这个草图中看出：

Fibonacci

基本上，每个对fib函数的递归调用都必须计算其自身使用的所有以前的斐波那契数。因此，最常计算的值将是fib(1)，因为它必须出现在由@kqr的答案显示的树的所有叶节点中。该算法的复杂度是树的节点数，即$O(2^n)$。
现在，更好的方法是跟踪两个数字，当前值和上一个值，这样每次调用就不必计算所有先前的值。这是草图中的第二种算法，可以按以下方式实现。
def fib(n):
   if (n==0):
       return(0,1)
   elif (n==1):
       return(1,1)
   else:
       a,b = fib(n-1)
       return(b,a+b)

这个算法的复杂度是线性的 $O(n)$，以下是一些例子：

>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)
4

我知道这个问题是8年前提出的，而且已经得到了充分的回答...很抱歉让它重新浮现。但总有更多需要说的。我在搜索中发现了这个问题，以改进自己的算法，我想分享一下。

我想提供自己的看法，因为我看到这个问题并没有被真正提起。我认为我的算法在贡献者中是独特的。我利用众所周知的斐波那契数列方程（维基百科）来缩小指数。其中一两个人简要介绍了基本版本，但我更进一步。

这是一个递归算法，但我能够在0.15秒内计算Fib（200万），在不到2秒的时间内计算Fib（1000万），在75秒内计算Fib（1亿）。所有这些都没有错误。我会说，它不是最快的计算连续斐波那契数列的整个列表的方法；这对于挑选非常大的单个数字最好。

到目前为止提到的大多数算法 - 无论它们有多快 - 都难以在没有递归深度问题的情况下超过Fib（100）。一些贡献者已经提到了我的算法的某些部分，尽管它们有一些不足之处，而我的算法则没有。我并不是说我的算法是最好的或任何东西，但我认为它非常快，并且可以计算非常大的Fibs。我认为把它加入讨论是值得的。
最重要的是，我不使用任何内存。没有任何类型的列表、字典或数组。没有缓存或备忘录。甚至没有一个持久的保存常量。没有导入特殊包。只有基本的、简单的Python和基本的整数类型。我还将函数扩展到计算负Fib，对运行时间的影响可以忽略不计。
我应该警告一下......我是一名数学家，而不是程序员。我毫不怀疑这可以进一步改进。而且我不知道 Big O 是什么。
def fib(n):
      if n<0: return int(pow(-1, (n&1)+1))*fib(-n)
      if n == 0: return 0
      if n==1 or n==2: return 1
      if n==3: return 2
      
      # n is multiple of 3
      if n%3 == 0:
            third = n//3
            fibthird = fib(third)
            return 5*pow(fibthird,3) + 3*pow(-1, third)*fibthird
            
      # even n
      if n&1==0:
            return pow(fib((n>>1) + 1),2) - pow(fib((n>>1) - 1), 2)

      # for odd n
      return ( pow(fib((n>>1)+1),2) + pow(fib(n>>1),2) )

运行代码，告诉我你的想法。我很想听听社区的意见。就我个人而言，我对它印象深刻，并且已经运行了一段时间。但是在我的有限（编程）知识中，找不到改进它的方法。尝试添加列表、记忆化、缓存等都无法改善任何东西，或者使运行时间更长。在我发现可以改善运行时间的罕见情况下，运行时间的好处微不足道，而内存成本却很高，我认为这不是一个公平的交易。

素数测试

为了增加乐趣，我在下面包含了一个基本的概率性is_prime测试，与斐波那契数列有关：

def is_prime_fib(n):
      # Fibonacci Probabilistic is_prime test. Compositeness deterministic.
      if n==1: return False
      if n==5: return True
      if n%5 in [1,4] and fib(n-1) % n == 0: return True
      if n%5 in [2,3] and fib(n+1) % n == 0: return True
      return False

我只是为了好玩而包含这个内容，尽管它与主题无关。这是一个使用斐波那契数列进行的著名素性测试，但不幸的是，它往往被忽略，因为大多数斐波那契计算算法都很慢，会导致递归错误或产生不准确结果，从而使测试不可靠，我们自然而然地转向其他算法。不过我认为这个游戏可以稍微改变一下。

就其本身而言，斐波那契素性测试是概率性的。n=1和n=5的情况是失败的特例，但它们太明显了，不值得担心。除此之外，False在合成性方面是确定性的，True在素性方面是概率性的。通过与其他概率性测试相结合，我们可以实现新兴的确定性。

这将为“减半/加倍”方法增加一个侧步，我猜计算一个较小的值并采取更大的步骤只需要大约三倍的速度。 - greybeard
我希望你能把素数测试留出来 - 我建议你发布一个单独的（交叉链接的）自问自答问题（我不喜欢寻找答案的问题，也不喜欢急需解决方案的问题）。 - greybeard
我包含了素性检测，因为它是一个常见的问题，而大的质数需要大的斐波那契数列，这个算法能够生成。它是一个附注，无可厚非。但除此之外，有什么别的理由会让任何人生成这么大的斐波那契数列吗？ 至于批评者只看到语法或其他表面上的更改，显然你没有运行代码或观察性能，并且你显然不关心我的声明是否足够有效以进行测试。你真的不认为一个能够生成fib(100 million)的算法在这个领域有竞争力吗？ - CogitoErgoCogitoSum
好的...所以你不相信创新是一件事情，是吗？好吧。我从来没有声称自己是算法的发明者。实际上，在我的第二段中，我明确表示我是从维基百科上得到的。你有读过我写的任何东西吗？我得到的荣誉是成为这个页面上第一个贡献这个算法的人，以便其他人可以从中学习。你真的需要一个社区驱动的维基百科来为你设定标准吗？还有什么反对意见吗？为什么SO上的每一个问题或答案都必须被辩护呢？https://www.youtube.com/watch?v=IbDAmvUwo5c - CogitoErgoCogitoSum
相反，我坚信发现和创新，就像我坚信撇号一样。当斐波那契写下那个序列时，它是一个事情，如果在几百年前完成了，那也是一个事情。哪里有什么否定呢？我是那个点赞的人-看看我对其他问题和答案的评论吧。当然，还有帖子本身：点赞你认为有用的内容（超出当前投票范围）；考虑将你认为有害的内容进行踩票。（这不是对话/线程-这既不是usenet也不是聊天室）。 - greybeard
显示剩余5条评论
4
这是一个简单的解决方案，不涉及递归和O(n)时间复杂度。
def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
1
这个回答回答了什么问题？ - greybeard
1
@老程序员 "有没有什么方法可以让这个更快？" - dan-klasson
4

一个O(1)解决方案

事实证明，有一个漂亮的递归公式可以计算偶斐波那契数之和。在偶数斐波那契数之和序列中的第n个项为 S_{n} = 4*S_{n-1} + S_{n-2} + 2。留给读者证明的是：1）偶数Fibo数是每三个数中的一个；2）使用Fibo数的定义进行归纳证明上述公式。使用这里的逻辑，我们可以通过一些努力推导出一个闭合形式的公式：

S_{n} = -1/2 + (1/4 + 3*sqrt(5)/20)*(2+sqrt(5))**n + (1/4 - 3*sqrt(5)/20)*(2-sqrt(5))**n

尽管存在sqrt，但对于整数n而言，它是整数，因此可以使用我之前回答中提到的便捷函数或使用诸如sympy之类的包来精确处理根。

import sympy as sp
one = sp.sympify(1) #to force casting to sympy types
k1 = -one/2
k2 = one/4 + 3*sp.sqrt(5)/20
k3 = one/4 - 3*sp.sqrt(5)/20
r1 = one
r2 = 2 + sp.sqrt(5)
r3 = 2 - sp.sqrt(5)
def even_sum_fibo(n):
  #get the nth number in the sequence of even sums of Fibonacci numbers.  If you want the sum of Fibos up to some number m, use n = m/3 (integer division)
  return sp.simplify(k1*r1**n + k2*r2**n + k3*r3**n)
5的平方根是一个无理数，计算它有限制。虽然这是O(1)，但在计算大量斐波那契数时不够精确。因此，矩阵指数是更好的选择。 - revo
@revo 这并不是真正计算sqrt(5)。它只是代数上的存在。最后，所有的sqrt(5)都会相互抵消或相乘成精确的5。 - Him
@revo，要明确的是，这个解决方案根本不涉及任何浮点运算。 - Him
此外，该解决方案中的操作数量是恒定的，但数字的长度与 $n$ 成线性关系，因此一旦超过处理器寄存器的大小，就没有亚线性算法。 - Him
这个在技术上不是O(n)或O(log n)吗？你需要计算ri**n，这在朴素方法中需要n次操作，或者使用快速幂运算等方法时需要log n次操作。 - undefined
在其他评论中，有人提到斐波那契数列呈指数增长，仅仅列出数字的行为就是O(n)。当时我懒得更新我的答案，哈哈。现在我会更新的。@Thomas - undefined
3
我基于维基百科上的斐波那契数列文章进行了翻译。这个想法是避免循环和递归，只需根据需要计算值。
我不是一个数学高手，所以选择了其中一个公式，并将其转化为代码，并对其进行了微调，直到值出现正确。
import cmath

def getFib(n):
    #Given which fibonacci number we want, calculate its value
    lsa = (1 / cmath.sqrt(5)) * pow(((1 + cmath.sqrt(5)) / 2), n)
    rsa = (1 / cmath.sqrt(5)) * pow(((1 - cmath.sqrt(5)) / 2), n)
    fib = lsa-rsa
    #coerce to real so we can round the complex result
    fn = round(fib.real) 
    return fn 

#Demo using the function
s = ''
for m in range(0,30):
    s = s + '(' + str(m) + ')' + str(getFib(m)) + ' '

print(s)
这怎么样才能快速实现 [找到] 不超过四百万的偶数项之和？ - greybeard
1
getFib(10000)溢出错误：复数指数 - Prokhozhii
3
import time


def calculate_fibonacci_1(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return calculate_fibonacci_1(n - 1) + calculate_fibonacci_1(n - 2)


def calculate_fibonacci_2(n):
    fib = [0] * n
    fib[0] = 1
    fib[1] = 1
    for i in range(2, n):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n-1]


def calculate_fibonacci_3(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def calculate_fibonacci_4(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec == '1':
            v1, v2, v3 = v1+v2, v1, v2
    return v2


def calculate_fibonacci_5(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = calculate_fibonacci_5(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

    n = 30

    start = time.time()
    calculate_fibonacci_1(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_2(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_3(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_4(n)
    end = time.time()
    print(end - start)

    start = time.time()
    calculate_fibonacci_5(n)
    end = time.time()
    print(end - start)

当 n=30 时：

0.264876127243
6.19888305664e-06
8.10623168945e-06
7.15255737305e-06
4.05311584473e-06

当 n=300 时：

>10s
3.19480895996e-05
1.78813934326e-05
7.15255737305e-06
6.19888305664e-06

对于 n=3000：

>10s
0.000766038894653
0.000277996063232
1.78813934326e-05
1.28746032715e-05

对于 n=30000：

>10s
0.0550990104675
0.0153529644012
0.000290870666504
0.000216007232666

当 n=300000 时：

>10s
3.35211610794
0.979753017426
0.012097120285
0.00845909118652

当 n=3000000 时：

>10s
>10s
>10s
0.466345071793
0.355515003204

对于 n=30000000 ：
>100s
>100s
>100s
16.4943139553
12.6505448818

声明: 第4和第5个函数的代码并不是由我编写的

这个回答解决了什么问题？我没有看到快速地解决欧拉计划第二题。 - greybeard
3

如果你还没有自己尝试过欧拉计划问题2，请勿阅读此内容。

除了基于闭式级数求和的方法，这种方法似乎比我看到的大多数/全部方法都更有效率，因为它只需要一个相当廉价的循环迭代来处理每个偶数的斐波那契数，所以只需要12次迭代就可以得到400万。

def sumOfEvenFibonacciNumbersUpTo(inclusiveLimit):
    even = 0
    next = 1
    sum  = 0
    while even<=inclusiveLimit:
        sum  += even
        even += next<<1
        next  = (even<<1)-next
    return sum
你可以自己检查一下，我猜。 - Prokhozhii
让我们澄清sumOfEvenFibonacciNumbersUpTo函数的意图。斐波那契数列是0、1、1、2、3、5、8等。该函数旨在返回（例如）从0到10的inclusiveLimit输入，即0、0、2、2、2、2、2、2、10、10、10，它做了它所说的事情。特别地，它不像大多数答案一样打印斐波那契数列。它直接执行OP要求的操作，即计算小于或等于限制参数的序列的偶数元素之和。需要一些数学知识来证明它的有效性。 - egyik
我很难过，有人给这个答案点了踩。这让我开始怀疑自己是否还有兴趣在这里分享信息。 - egyik
如果有人想要观看这个程序的工作过程，可以在循环中添加 print(even, next, sum)。 - greybeard
（如果您解释了这个代码的工作原理，有人可能会授予奖励。） - greybeard
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接