文中主角在完成百万级斐波那契数列时,引用了一个两倍项公式:
f(2n)=f(n+1)f(n)+f(n)f(n-1)
这个公式可以变换为:
f(2n)=f(n+1)f(n)+f(n)(f(n+1)-f(n))
还有一个公式:
f(2n+1)=f(n+1)f(n+1)+f(n)f(n)
所以,如果已知f(n)和f(n+1),可以得到f(2n)和f(2n+1)。
具体上,可以使用递归,但是得加上缓存。
我用java测了下,这个算法求第120w项木有压力~
()