寻找大数的斐波那契数

本文介绍了寻找大数的斐波那契数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我编写了以下程序来查找大斐波那契数的模数.这可以解决大量问题，但在 fibo_dynamic(509618737,460201239,229176339)这样的情况下无法计算，其中 a = 509618737 ， b = 460201239 和 N = 229176339 .请帮助我完成这项工作.

I wrote the following program for finding the modulus of large Fibonacci's number. This can solve large numbers but fails to compute in cases like fibo_dynamic(509618737,460201239,229176339) where a = 509618737, b = 460201239 and N = 229176339. Please help me to make this work.

long long fibo_dynamic(long long x,long long y,long long n, long long a[]){ if(a[n]!=-1){ return a[n]; }else{ if(n==0){ a[n]=x; return x; }else if(n==1){ a[n]=y; return y; }else { a[n]=fibo_dynamic(x,y,n-1,a)+fibo_dynamic(x,y,n-2,a); return a[n]; } } }

推荐答案

值将溢出，因为斐波那契数迅速增加.即使对于原始的斐波那契数列( f(0)= 0 和 f(1)= 1 )， f(90)的长度超过20位，并且不能以C ++的任何原始数据类型存储.您可能应该使用模运算符(因为您在问题中提到了它)将值保持在这样的范围内:

The values will overflow because Fibonacci numbers increase very rapidly. Even for the original fibonacci series (where f(0) = 0 and f(1) = 1), the value of f(90) is more than 20 digits long which cannot be stored in any primitive data type in C++. You should probably use modulus operator (since you mentioned it in your question) to keep values within range like this:

a[n] = (fibo_dynamic(x,y,n-1,a) + fibo_dynamic(x,y,n-2,a)) % MOD;

在每个阶段进行 mod 值都是安全的，因为 mod 运算符具有以下规则:

It is safe to mod the value at every stage because mod operator has the following rule:

if a = b + c, then: a % n = ((b % n) + (c % n)) % n

此外，您已经使用了递归版本来计算斐波那契数(尽管您已经记下了较小的子问题的结果).这意味着将有很多递归调用，这增加了额外的开销.如果可能的话，最好使用迭代版本.

Also, you have employed the recursive version to calculate fibonacci numbers (though you have memoized the results of smaller sub-problems). This means there will be lots of recursive calls which adds extra overhead. Better to employ an iterative version if possible.

接下来，您要使用变量 n 为数组建立索引.因此，我假设数组 a 的大小至少为 n .问题中提到的 n 的值非常大.您可能无法在本地计算机上声明这么大的数组(考虑整数为 4个字节的大小，数组 a 的大小大约为874 MB ).

Next, you are indexing the array with variable n. So, I am assuming that the size of array a is atleast n. The value of n that is mentioned in the question is very large. You probably cannot declare an array of such large size in a local machine (considering an integer to be of size 4 bytes, the size of array a will be approximately 874 MB).

最后，您程序的复杂度为 O(n).有一种技术可以在 O(log(n))时间中计算第n个斐波那契数.它是使用矩阵幂求解递归关系".斐波那契数遵循以下线性递归关系:

Finally, the complexity of your program is O(n). There is a technique to calculate n_th fibonacci number in O(log(n)) time. It is "Solving Recurrence relations using Matrix Exponentiation." Fibonacci numbers follow the following linear recurrence relation:

f(n) = f(n-1) + f(n-2) for n >= 2

阅读此以了解该技术.