python-3.x - 无法使用python计算斐波那契数

Question

import math

import sys

sys.setrecursionlimit(8000000)


f = {1:2,2:3,3:5}

def fib(n):

    if n in f:
        return f[n]
    if n == 1:
        return 2
    if n == 2:
        return 3
    if n == 3:
        return 5
    val = fib(n-1) + fib(n-2)
    if n not in f:
        f[n] = val
    return f[n]%1000000007

print(fib(4000))

此代码无法完成/命令提示符崩溃。我怎样才能使它变得更好？

是否需要启用任何设置才能使该程序完整？

标签： python-3.x

Answer 1

直接从数学定义实现斐波那契数列是一个说明递归解决方案问题的练习。它导致递归函数调用呈指数级增长，即使是现代计算机也无法处理。最大的问题是，对于较大的 值n，您将计算fib(1)指数次数。

这个问题有几种解决方案：

1. 使用 memoization 存储已经计算的值。然后您查找计算值并立即返回它而不进行任何进一步的计算。这是一个很好的练习来了解记忆是如何工作的。但是，它仍然是低效的，因为您仍然不必要地执行递归函数调用。

2. 实施迭代解决方案。我不打算在这里详细介绍。我建议您进行一些研究以找到将fib(n)在线性时间而不是指数时间内实现的迭代解决方案。

3. 实施封闭公式。数学家已经解决fib(n)了一个封闭的公式。无论n您使用多大的一个，此解决方案都将花费恒定的时间。