编程之战 第五章百万级斐波那契的详细说明
作者:程序小猿的小说      更新:2019-05-23

  文中主角在完成百万级斐波那契数列时,引用了一个两倍项公式:

  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项木有压力~