怎样用Python实现斐波那契数列？

实现斐波那契数列在python中有多种方法：1.递归方法简单但效率低，时间复杂度为o(2^n)；2.动态规划优化后，时间和空间复杂度均为o(n)；3.进一步优化可将空间复杂度降至o(1)；4.生成器方法可按需生成数列，适合无限生成；5.使用decimal模块可处理大数，避免精度问题。

实现斐波那契数列在Python中简直是小菜一碟，但这不仅仅是写个函数那么简单，我们得深入探讨一下这个经典问题。

用Python实现斐波那契数列的方法有很多种，每种方法都有其独特的魅力和潜在的陷阱。让我们从最基础的递归开始，然后再看看如何优化它，最后再展示一些更酷的技巧。

递归是实现斐波那契数列最直观的方法，但它也可能是最慢的。看看这个简单的递归实现：

立即学习“Python免费学习笔记（深入）”；

def fibonacci_recursive(n):    if n <p>这个函数虽然简洁，但对于较大的n值，它的效率低得让人抓狂。<a style="color:#f60; text-decoration:underline;" title="为什么" href="https://www.php.cn/zt/92702.html" target="_blank">为什么</a>呢？因为它会重复计算很多次相同的子问题，导致时间复杂度是指数级的O(2^n)。</p><p>为了解决这个问题，我们可以使用动态规划来优化。动态规划的思想是保存已经计算过的结果，这样我们就不需要重复计算了。看看这个用动态规划实现的版本：</p><pre class="brush:python;toolbar:false;">def fibonacci_dp(n):    if n <p>这个版本的时间复杂度是O(n)，空间复杂度也是O(n)。但我们还能做得更好。使用两个变量来保存前两个数，就可以把空间复杂度降到O(1)：</p><pre class="brush:python;toolbar:false;">def fibonacci_optimized(n):    if n <p>这个版本不仅快，而且节省内存，简直是完美的解决方案。</p><p>但如果你想玩得更酷一点，可以用生成器来实现斐波那契数列。这样你就可以按需生成数列中的数，而不需要一次性计算整个数列：</p><pre class="brush:python;toolbar:false;">def fibonacci_generator():    a, b = 0, 1    while True:        yield a        a, b = b, a + b

登录后复制