java - 动态规划中的第 n 个斐波那契数

Question

斐波那契数列的逻辑大家都懂

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

我的问题是我必须计算fib(n)%(100000000+7) 并且output 应该根据n

比如 for n=0 output 1

对于 n=5 输出 5

对于 n=10 输出 55​​

对于 n=100 输出 24278230

而且我还在 scala 中使用 tail recursion 成功编码了它

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 为 100

任何人给我一些想法来获得这个输出

Answer 1

我的回答是对 linear recurrence sequences 的一个比较通用的解决方案.您需要一些基本的代数知识才能完全理解它。

让我们有一个 vector

然后我们将它与矩阵相乘

我们会收到:

因此，当我们将 vector 与该矩阵相乘时，我们会得到下一个斐波那契数。但是，如果我们将 vector 与 T² 相乘会发生什么？

这样，我们构造了下一个(第(n+3)个)之后的斐波那契数列。现在，如果我们从该 vector 中的前两个斐波那契数开始并将其与 T^n-1 相乘，我们会得到什么？

因此，通过将我们的 vector 与矩阵 T 相乘，提高到 (n-1) 次方，我们可以获得第 n 个斐波那契数。我们可以通过 exponentiation by squaring 在时间 O(log n) 中计算 T^n-1 .当然，我们应该通过模 10⁸ + 7 进行所有计算。

这是我的实现的链接(用 Java):http://pastie.org/8519742

对于 n 到 2¹⁰⁸ 的所有正值，此算法应该可以很好且快速地工作。

该方法的示例运行时间(使用与 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

但是，尽管如此，这不是解决您的问题的最快算法。众所周知，斐波那契数列在某些模数下具有周期性残差。引用 the wikipedia entry关于斐波那契数列:

It may be seen that if the members of the Fibonacci sequence are taken mod n, the resulting sequence must be periodic with period at most n²−1.

换句话说，如果您找到这个周期(例如，tortoise and hare algorithm - 线性复杂度)，您还可以找到每个 斐波那契数模 10⁸+7.