我编写了以下程序来查找大斐波那契数的模数.这可以解决大量问题,但在 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阅读此以了解该技术.
更多推荐
寻找大数的斐波那契数
发布评论