动态编程中的第n个Fibonacci数
每个人都知道斐波那契系列的逻辑
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
我在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
任何人都给我一些想法来获得这个输出
我的答案是线性递归序列的一种通用解决方案。 您需要一些基本的代数知识才能完全理解它。
我们有一个向量
然后我们将它与矩阵相乘
我们会收到：
因此，当我们将向量与此矩阵相乘时，我们会收到下一个斐波纳契数。 但是如果我们将矢量乘以T 2会发生什么？
通过这种方式，我们在下一个（第（n + 3）个）之后构造了斐波那契数。 现在，如果我们从这个向量中的前两个斐波那契数开始并将其与T n-1相乘，我们会得到什么？
因此，通过将我们的向量与矩阵T相乘，提高到第（n-1）次幂，我们可以得到第n个斐波纳契数。 我们可以通过求平方来计算时间O（log n）中的T n-1 。 当然，我们应该以模数10 8 + 7进行所有计算。
这是我的实现链接（用Java）： http ： //pastie.org/8519742
对于n最高为2 10 8的所有正值，该算法应该能够很好地运行。
该方法的运行时间示例（使用与Peter Lawrey的答案相同的时间测量）：
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序列的成员采用mod n，则所得序列必须是周期性的，周期最多为n 2 -1。
换句话说，如果你找到这个时期（例如， 乌龟和野兔算法 – 线性复杂度），你也可以找到模数为10 8 +7的每个斐波纳契数的结果。
这是我所知道的用于计算fib％mod的最快方法，但你只看到大约1000+的差异
public static void main(String[] args) { long mod = 100_000_007; for (int i = 100_000_000; i > 0; i /= 10) { long start = System.nanoTime(); final long l = fibMod3(i, mod); long time = System.nanoTime() - start; System.out.printf("fib(%,d) %% %,d is %,d took %.1f us to calculate%n", i, mod, l, time / 1e3); } } // use a simple loop and % each time. public static long fibMod(int n, long mod) { long a = 1, b = 1; if (n <= 2) return 1; while (n-- > 2) { long c = a + b; a = b; b = c % mod; } return b; } // mod is very expensive so only do this on every third iteration. public static long fibMod3(int n, long mod) { long a = 1, b = 1; if (n <= 2) return 1; while (n > 5) { long c = a + b; a = b + c; b = (c + a) % mod; n -= 3; } while (n > 2) { long c = a + b; a = b; b = c; n--; } return b % mod; }
版画
fib(100,000,000) % 100,000,007 is 21 took 546460.1 us to calculate fib(10,000,000) % 100,000,007 is 60,722,758 took 54079.6 us to calculate fib(1,000,000) % 100,000,007 is 72,117,251 took 5274.9 us to calculate fib(100,000) % 100,000,007 is 33,178,829 took 506.0 us to calculate fib(10,000) % 100,000,007 is 49,520,320 took 50.8 us to calculate fib(1,000) % 100,000,007 is 95,802,669 took 5.2 us to calculate fib(100) % 100,000,007 is 24,278,230 took 0.7 us to calculate fib(10) % 100,000,007 is 55 took 0.3 us to calculate fib(1) % 100,000,007 is 1 took 0.3 us to calculate
当代码已经预热时，fib（100）需要0.7微秒。 如果你循环增加大小，它甚至不编译，大约需要3微秒。
我用C ++编写了它，它运行良好。
LL fi(int n, LL a, LL b) { if (n == 0) { return a; } else { return fi(n-1, b, (a+b) % 100000007); } }
你应该在这里修改：fib_tail（n-1，b，（a + b）％MOD），否则结果将超出Long的范围。