问题描述
我曾经尝试尝试解决此问题的方法,但是我认为它不是非常有效,因为一旦输入太大的数字就无法使用。
def fib_even(n):
fib_even = []
a, b = 0, 1
for i in range(0,n):
c = a+b
if c%2 == 0:
fib_even.append(c)
a, b = b, a+b
return fib_even
def sum_fib_even(n):
fib_evens = fib_even(n)
s = 0
for i in fib_evens:
s = s+i
return s
n = 4000000
answer = sum_fib_even(n)
print answer
例如,这不适用于4000000,但适用于400。有没有更有效的方法?
1楼
不必计算所有斐波纳契数。
注意:我在后面使用斐波那契数列的更标准初始值F [0] = 0,F [1] = 1。 项目Euler#2从F [2] = 1,F [3] = 2,F [4] = 3,.....开始其顺序。对于此问题,两种选择的结果都是相同的。
所有斐波纳契数的总和(作为热身)
递归方程
F[n+1] = F[n] + F[n-1]
也可以读成
F[n-1] = F[n+1] - F[n]
要么
F[n] = F[n+2] - F[n+1]
将n从1到N求和(记住F [0] = 0,F [1] = 1),在左边给出斐波那契数的总和,在右边给出所有内部项都抵消的伸缩总和
sum(n=1 to N) F[n] = (F[3]-F[2]) + (F[4]-F[3]) + (F[5]-F[4])
+ ... + (F[N+2]-F[N+1])
= F[N+2] - F[2]
因此,对于使用问题的数字N = 4,000,000的总和,仅需计算
F[4,000,002] - 1
与用于计算单个斐波那契数的超快方法之一。 减半和平方,等于迭代矩阵的幂,或者基于黄金比例的指数公式(以必要的精度计算)。
由于大约每20个斐波那契数字您将获得4个额外的数字,因此最终结果将由大约800000个数字组成。 最好使用可以包含所有数据的数据类型。
偶数斐波纳契数的总和
只需检查前10或20个斐波那契数,就会发现所有偶数成员的索引均为3 * k。 通过减去两次连续递归得到
F[n+3]=2*F[n+2]-F[n]
因此F [n + 3]总是与F [n]相同。 投资更多的计算可以发现成员三个索引之间的递归
F[n+3] = 4*F[n] + F[n-3]
设置
S = sum(k=1 to K) F[3*k]
并对n = 3 * k的递归求和
F[3*K+3]+S-F[3] = 4*S + (-F[3*K]+S+F[0])
要么
4*S = (F[3*K]+F[3*K]) - (F[3]+F[0]) = 2*F[3*K+2]-2*F[2]
因此所需的总和具有公式
S = (F[3*K+2]-1)/2
用黄金配比公式快速计算得出N应该是多少,以便F [N]刚好在边界之下,因此K = N div 3应该是,
N = Floor( log( sqrt(5)*Max )/log( 0.5*(1+sqrt(5)) ) )
将欧拉问题简化为一个简单公式
在最初的问题中,人们发现N = 33,因此总和为
S = (F[35]-1)/2;
减少问题中的问题和后果
取问题中的错误表示问题,N = 4,000,000,所以K = 1,333,333,总和为
(F[1,333,335]-1)/2
仍然有约533,400位数。 是的,biginteger类型可以处理此类数字,用它们进行计算只需要时间。
如果以60行80位的格式打印,则该数字将填充112张纸,只是为了弄清楚输出是什么样子。
2楼
不必存储所有中间斐波纳契数,否则存储会导致性能问题。