我正在尝试编写一个程序以找到1
这是我使用动态编程的代码。
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
我的代码似乎不适用于大量工作。我收到无效的响应错误。
有什么建议么？
最佳答案
如果您以幼稚的方式获得N，则在N为10 ^ 19时获得第N个斐波那契数是不可行的(至少我想这是行不通的)。
有一种更好的方法。这项技术适用于许多类似的系列。它称为Fibonacci Q Matrix。
在哪里
这样想:
您有一些矩阵将向量A转换为B:
填写这些条目很容易。特殊的部分是现在它是一个矩阵运算符，因此，如果我们想要第1000个斐波那契数，我们只需要进行矩阵乘法即可。
您可以使用循环来完成此操作，但是要花很长时间才能一直达到10 ^ 19，并且进行10 ^ 19矩阵乘法(即使它们很小)也将花费相当长的时间也。
相反，我们采取了另一个捷径。可以将x ^ N重写为幂的乘积，它们之和为N，即
x**100 == x**90 * x**10
因此，目标是在不进行大量计算的情况下获得大量索引:
x**2和x*x一样困难-它们花费相同的时间。但是x*x*x*x提供与(x**2)**2相同的答案，同时需要额外的乘法。当您使用更高的功率时， yield 会越来越大。因此，如果将指数分解为2的幂(任何幂都可以，但这是最简单的情况)，X**100 == X**64 * X**32 * X**4
IE。
X**100 == (((((X**2)**2)**2)**2)**2)**2 + ...
因此，您要做的是算出要达到的总幂中的两个幂，然后取
Q矩阵中两个幂的乘积。这似乎为我工作:
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]
然后，您可以更进一步-它只是一个2x2矩阵，因此我们可以对角化它，然后获得n个斐波那契数的公式，就像n的函数一样-无需递归。像这样:
如上所述，我们计算出将我们从一个步骤转移到下一个步骤的矩阵:
然后从一组数字到另一组数字的关系:
我们可以在其中链接这些矩阵乘法:
没有什么可以阻止我们回到第一个斐波那契数字的:
现在游戏变成“我们如何将矩阵提高到幂n”-这正是上面代码中所做的。但是有比我上面提出的解决方案更好的方法。我们可以将Q矩阵分解为特征值和向量，这样写:
其中 U 是一个单一矩阵，其中包含 Q 的特征值，而Λ是对应特征值的矩阵。这些特征值和vecor是:
然后，您可以使用这种分解方式的标准优势之一，即当将其提升为幂时，相邻的U矩阵及其逆组合会得到matrix矩阵，从而使您得到一个U并在末尾将其逆，中间有一串对角矩阵，将这些矩阵求幂是很简单的:
因此，现在我们只需要一个公式即可编写第n个斐波那契数，而无需递归。不过，我明天/本周晚些时候会完成它...