我正在尝试编写一个程序，以查找 1 < n < 10^19 的第n个斐波那契数。
以下是使用动态规划的代码。
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 2:
f = 1
else:
f = fib(n-1) + fib(n-2)
memo[n]=f
return f
print fib(input()) % 1000000007
在哪里
请这样想：
您有一个将向量A转换为B的矩阵：
x**100 == x**90 * x**10
x**2 和 x*x 一样困难 - 它们需要相同的时间。但是，x*x*x*x 给出与 (x**2)**2 相同的答案，同时需要额外进行一次乘法。随着幂次数的增加，收益会更多。因此，如果将指数拆分为2的幂（任何幂都可以，但这是最简单的情况），X**100 == X**64 * X**32 * X**4
即
X**100 == (((((X**2)**2)**2)**2)**2)**2 + ...
fib_matrix = [[1,1],
[1,0]]
def matrix_square(A, mod):
return mat_mult(A,A,mod)
def mat_mult(A,B, mod):
if mod is not None:
return [[(A[0][0]*B[0][0] + A[0][1]*B[1][0])%mod, (A[0][0]*B[0][1] + A[0][1]*B[1][1])%mod],
[(A[1][0]*B[0][0] + A[1][1]*B[1][0])%mod, (A[1][0]*B[0][1] + A[1][1]*B[1][1])%mod]]
def matrix_pow(M, power, mod):
#Special definition for power=0:
if power <= 0:
return M
powers = list(reversed([True if i=="1" else False for i in bin(power)[2:]])) #Order is 1,2,4,8,16,...
matrices = [None for _ in powers]
matrices[0] = M
for i in range(1,len(powers)):
matrices[i] = matrix_square(matrices[i-1], mod)
result = None
for matrix, power in zip(matrices, powers):
if power:
if result is None:
result = matrix
else:
result = mat_mult(result, matrix, mod)
return result
print matrix_pow(fib_matrix, 10**19, 1000000007)[0][1]
然后是从一个数字集合到另一个数字集合的关系：
我们可以在这里链式进行矩阵乘法：
如果没有任何限制，我们可以一直回溯到第一个斐波那契数。
其中U是包含Q的特征值的酉矩阵，Λ是相应特征值的矩阵。这些特征值和特征向量为：
然后，您可以利用这种分解风格的标准优势之一，将其提升到幂次方时，相邻的U矩阵及其逆矩阵组合在一起形成幺正矩阵，留下单个U及其逆矩阵在两端，并在中间形成一系列对角矩阵，对这些矩阵进行乘方运算非常容易：
现在，我们已经拥有所有需要的内容来仅通过一个公式写出第 n 个斐波那契数，无需使用递归。不过我会在明天/本周晚些时候完成它...
在O(n)的效率下，你永远无法达到目标。虽然这不是特定的与代码相关，但Dijkstra's note "In honor of Fibonacci"描述了一种以O(log(n))的效率找到F(n)的方法。
F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1)+F(n))*F(n)
你不仅可以实现这个方法，而且还可以通过递归来实现。
n达到10^19的F(n)仍然是无望的。（在这里没有任何公式可以奏效：结果太大而无法存储。）但与模1000000007的约简相结合，这将奏效。 - Mark DickinsonF(n)对1000000007取模后的结果，而不是F(n)本身。（听起来像是一个典型的Project-Euler风格的挑战问题，而不是现实世界中的计算。） - Mark DickinsonPython默认的递归限制是1000（通常情况下）。要查找您系统上的确切限制，请执行以下操作：
>>> import sys
>>> sys.getrecursionlimit()
首先，如果你想要递归编写代码，并且你使用的是Python 3.2及以上版本（从你的print语句来看，好像不是），那么你可以这样使用@functools.lru_cache(maxsize=128, typed=False)：
import functools
@functools.lru_cache()
def fib(n):
if n <= 2:
return 1
else:
return fib(n-1) + fib(n-2)
尽管如此，对于大数字来说这仍然不够快。更好的方法是编写迭代解决方案，并且你只需要在任何时候“记忆化”最后2个数字。
当然，你可以使用矩阵形式以获得更好的性能。
最终，对于n达到10**19这么大的数字，你很难在Python中编写任何运行而不会导致OverflowError的代码。
我认为你无法使用这种方法达到1E19，但是以下是避免双重溢出和递归深度限制的方法：
import decimal
import operator
def decimal_range(start, stop, step=1):
"""Provides an alternative to `xrange` for very high numbers."""
proceed = operator.lt
while proceed(start, stop):
yield start
start += step
def fib(n):
"""
Computes Fibonacci numbers using decimal.Decimal for high
precision and without recursion
"""
a, b = decimal.Decimal(0), decimal.Decimal(1)
for i in decimal_range(0, n):
a, b = b, a + b
return a
在我的电脑上，计算1E6需要26.5秒，但我不能保证结果的准确性:
In [26]: %time f2(n)
CPU times: user 26.4 s, sys: 130 ms, total: 26.5 s
Wall time: 26.5 s
Out[26]: Decimal('1.953282128707757731632014830E+208987')
1000000007，而不是实际的斐波那契数。你还可以研究Fib(2n)和Fib(2n+1)的公式，这些公式用Fib(n)和Fib(n+1)表示（例如）。 - Mark Dickinson