java - 动态编程中的第n个斐波那契数

每个人都知道斐波那契级数的逻辑

Fib0 = 0
Fib1 = 1
Fibn = Fibn-1 + Fibn-2 , n > 1

我的问题是我必须计算fib(n)%(100000000+7)并且输出应该根据n
喜欢for n=0 output 1
for n=5 output 5
for n=10 output 55
for n=100 output 24278230
我成功地用tail recursion在scala中编码了它。

def fi( n : Int) : Long = {
  def fib_tail( n: Int, a:Int, b:Int): Int = n match {
    case 0 => a
    case _ => fib_tail( n-1, b, (a+b))
  }
  return fib_tail( n, 0, 1)
}


   l.map(x=> println(fi(x)%((math.pow(10, 8)).toInt +7  )))

对于0,1,5,10，它工作正常，但是对于100，它给出了错误的输出，对于24278230
任何人都能给我点主意

最佳答案

我的答案是对linear recurrence sequences的一个一般性解决方案。你需要一些基本的代数知识才能完全理解它。
让我们有一个向量
我们把它和矩阵相乘
我们将收到：
因此，当我们将向量与这个矩阵相乘时，我们得到下一个斐波那契数但是如果我们把向量乘以T2会发生什么呢？
这样，我们在下一个数（n+3）之后构造了fibonacci数。如果我们从向量的前两个fibonacci数开始，乘以Tn-1，会得到什么？
所以通过将向量与矩阵T相乘，提升到（n-1）次方，我们可以得到n次斐波纳契数我们可以通过exponentiation by squaring计算时间o（log n）中的tn-1。当然，我们应该按照108+7的模来计算。
这里是我的实现的一个链接（在Java中）：http://pastie.org/8519742
该算法对于n的所有正值（最大值2108）都应该运行良好且快速。
方法的样本运行时间（使用与Peter Lawrey的answer中相同的时间测量）：

fib(1,000,000,000,000,000,000) is 8,465,404 took us 1022.8 to calculate
fib(100,000,000,000,000,000) is 60,687,801 took us 325.7 to calculate
fib(10,000,000,000,000,000) is 9,115,009 took us 247.2 to calculate
fib(1,000,000,000,000,000) is 8,361,917 took us 233.3 to calculate
fib(100,000,000,000,000) is 11,279,600 took us 218.3 to calculate
fib(10,000,000,000,000) is 72,758,000 took us 6027.7 to calculate
fib(1,000,000,000,000) is 82,461,898 took us 184.2 to calculate
fib(100,000,000,000) is 60,584,292 took us 180.4 to calculate
fib(10,000,000,000) is 68,453,509 took us 162.0 to calculate
fib(1,000,000,000) is 90,703,191 took us 145.4 to calculate
fib(100,000,000) is 21 took us 131.3 to calculate
fib(10,000,000) is 60,722,758 took us 112.0 to calculate
fib(1,000,000) is 72,117,251 took us 99.8 to calculate
fib(100,000) is 33,178,829 took us 92.3 to calculate
fib(10,000) is 49,520,320 took us 70.8 to calculate
fib(1,000) is 95,802,669 took us 60.1 to calculate
fib(100) is 24,278,230 took us 39.3 to calculate
fib(10) is 55 took us 27.0 to calculate
fib(1) is 1 took us 16.3 to calculate

然而，尽管如此，这并不是解决问题的最快算法众所周知，fibonacci数在某些模下有周期剩余引用斐波那契数：the wikipedia entry：
可以看出，如果Fibonacci序列的成员取模n，则得到的序列必须是周期性的，周期至多为n2-1。
换句话说，如果你发现这个周期（例如，tortoise and hare algorithm线性复杂度），你也可以找到每个斐波那契数108 + 7的结果。

关于java - 动态编程中的第n个斐波那契数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20300537/