寻找大数的斐波那契数 [英] Finding the fibonacci number of large number

问题描述

我编写了以下程序来查找大斐波那契数的模数.这可以解决大量问题，但在 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

阅读此以了解该技术.

这篇关于寻找大数的斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！