在有限时间内用Python找出最大的斐波那契数

Question

我需要一段代码，能够计算第n个斐波那契数，并且告诉我计算这个数花了多少时间，使用Python语言。

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

计算这个数字的步骤必须使用某种方法。

Answer 1

这里有一个非常简单的例子，它使用了Python中的元组，而不是递归。

import time

def fib(n):
    cnt = 1
    if n == 0:
        return a
    a = 0
    b = 1
    while n > cnt:
        (a, b) = (b, b+a)
        cnt += 1
    return b

start = time.time()
result = fib(15)
runTime = time.time() - start

print result, runTime

Answer 2

这是一个经典的动态规划和递归加记忆化的问题。注意到在你的代码中，你会反复调用 fib(x-1)，这其实是非常浪费时间的：一旦你计算过一次，就应该把结果存起来，以后就不用再计算了。在Python 3中，你可以使用非常棒的 functools.lru_cache 来实现这个功能。

@lru_cache(maxsize=None)
def fib(n):
    if n < 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

不过，由于现在还没有人使用Python 3.2，你需要自己写一个。下面是一些伪代码：

cache = {0: 0, 1: 1}
def fib(n):
    if n in cache:
        return the cached value
    else:
        calculate fib(n) recursively
        store the value in the cache
        return the value

这种技术叫做带记忆化的递归。你也可以用 动态规划 的方法：从底部开始逐步计算值：

fibs = [0, 1]
for i in range(2, n):
    calculate fibs[i] using the previous values in fibs
    append the new value

---

要测试这些函数的运行时间，可以把它们放在一个模块中（也就是一个以 .py 结尾的文件），然后在命令行中使用 timeit。

(change directory to the one containing your module)
python -mtimeit "import <name of module>" "fib(3000)"

---

顺便提一下，计算第n个斐波那契数还有一个封闭形式的表达式，这可能会更快或更有用：

其中

Answer 3

使用 timeit 模块来测量函数的执行时间：

import timeit

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

print timeit.Timer('fib(5)', 'from __main__ import fib').timeit()

输出结果：

3.12172317505

直接回答标题中的问题，你可以使用 time.time() 来获取从纪元（1970年1月1日）开始到现在的秒数，然后不断计算后续的斐波那契数，直到达到时间限制。我选择了一个高效的斐波那契数计算方法，下面的例子可以更好地展示这个概念。

def fibTimeLimited(limit):
  start = time.time()
  n, f0, f1 = 1, 0, 1
  while time.time() < start + limit:
    n += 1
    f0, f1 = f1, f0+f1
  return (n, f1)

示例输出：

Calculated 1st fibonacci number as 1 in 0.000001 seconds
Calculated 31st fibonacci number as 1346269 in 0.000010 seconds
Calculated 294th fibonacci number as 12384578529797304192493293627316781267732493780359086838016392 in 0.000100 seconds