动态编程中的第n个Fibonacci数 [英] nth Fibonacci number in dynamic programming

问题描述

每个人都知道Fibonacci系列的逻辑

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

我的问题是我必须计算 fib（n）％（100000000 +7）和输出应符合 n

喜欢用于n = 0输出1

用于n = 5输出5

n = 10输出55

对于n = 100输出24278230

我用尾递归 in 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））
} 
返回fib_tail（n，0,1）
} 
 
 
 l .map（x => println（fi（x）％（（math.pow（10,8））。toInt +7）））
  

它适用于0,1,5,10，但是它给出错误的输出100我希望 24278230 for 100

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

解决方案

我的回答是

对于n <2> ^{10 8} 的所有正值，该算法应该能够很好地快速运行。

该方法的示例运行时间（使用与Peter Lawrey的相同时间测量回答）：

  fib（1,000,000,000,000,000,000）是8,465,404，花了我们1022.8来计算
 fib（100,000,000,000,000,000,000） ）是60,687,801花了我们325.7计算
 fib（10,000,000,000,000,000）是9,115,009花了我们247.2来计算
 fib（1,000,000,000,000,000）是8,361,917花了我们233.3来计算
 fib（100,000,000,000,000）是11,279,600花了我们218.3计算
 fib（10,000,000,000,000）是72,758,000我们6027.7计算
 fib（1,000,000,000,000）是82,461,898我们184.2来计算
 fib（100,000,000,000）是60,584,292我们180.4来计算
 fib（10,000,000,000）是68,453,509，我们162.0计算
 fib（1,000,000,000）是90,703,191我们145.4计算
 fib（100,000,000）21我们131.3计算
 fib（10,000,000） ）是60,722,758我们112.0计算
 fib（1,000,000）是72,117,251花了我们99.8来计算
 fib（100,000）是33,178,829花了我们92.3来计算
 fib（10,000）是49,520,320花了我们70.8来计算
 fib（1,000）是95,802,669花了我们60.1来计算
 fib（100）是24,278,230花了我们39.3来计算
 fib（10）是55花了我们27.0来计算
 fib（ 1）是1拿我们16.3计算
  

然而，尽管如此，这是不是问题的最快算法。众所周知，斐波那契数在某些模块下具有周期性残基。在斐波纳契数字上引用维基百科条目：

可以看出，如果Fibonacci序列的成员采用mod n，则结果序列必须是周期性的，周期最多为n ² -1。 / p>

换句话说，如果你找到这个时期（例如，龟和野兔算法 - 线性复杂度），你也可以找到每个斐波那契数模10的结果 ⁸ +7。

Every one know logic of Fibonacci series

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

my question is i have to calculate fib(n)%(100000000+7) and output should be according n

like for n=0 output 1

for n=5 output 5

for n=10 output 55

for n=100 output 24278230

and i successfully coded it also with tail recursion in 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  )))

it is working right for 0,1,5,10 but it is giving wrong output for 100 i want 24278230 for 100

any one give me some idea to get this output

解决方案

My answer is a somewhat general solution for linear recurrence sequences. You would need some basic algebra knowledge in order to understand it completely.

Let we have a vector

and we multiply it with the matrix

We would receive:

Therefore, when we multiply the vector with this matrix we receive the next fibonacci number. But what would happen if we multiply the vector with T²?

In this way, we constructed the fibonacci number after the next one (the (n+3)-th one). Now what would we get if we start with the first two fibonacci numbers in this vector and multiply it with T^n-1?

So by multiplying our vector with the matrix T, raised to the (n-1)th power, we can get the n-th fibonacci number. We can compute T^n-1 in time O(log n) via exponentiation by squaring. And of course, we should do all our calculations by modulo 10⁸ + 7.

Here is a link of my implementation (in Java): http://pastie.org/8519742

This algorithm should work well and fast for all positive values of n up to 2¹⁰⁸.

Sample running time of the method (using the same time measurement as in Peter Lawrey's 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

However, with all that said, this is not the fastest algorithm for your problem. It is well known that the fibonacci numbers have periodical residues under some module. Quoting the wikipedia entry on fibonacci numbers:

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.

In other words, if you find this period (with for example, the tortoise and hare algorithm - linear complexity), you can also find the result of every fibonacci number modulo 10⁸+7.

这篇关于动态编程中的第n个Fibonacci数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！