寻找大数的斐波那契数

Question

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

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];
        }
    }
}

Answer 1

因为斐波那契数的增长非常快，所以这些值会溢出。即使对于原始的斐波那契数列（其中 f(0) = 0 和 f(1) = 1），f(90) 的值也超过 20 位，不能存储在 C++ 中的任何原始数据类型中。您可能应该使用模数运算符（因为您在问题中提到了它）来将值保持在这样的范围内：

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

每个阶段的值 mod 是安全的，因为 mod 运算符有以下规则：

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

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

接下来，您将使用变量 n 对数组进行索引。因此，我假设数组 a 的大小至少为 n。题中提到的n的值很大。您可能无法在本地计算机中声明如此大的数组（考虑到整数的大小 4 bytes，数组 a 的大小将约为 874 MB）。

最后，你程序的复杂度是O(n)。有一种技术可以在 O(log(n)) 时间内计算出 n_th 斐波那契数。它是 "Solving Recurrence relations using Matrix Exponentiation." 斐波那契数遵循以下线性递归关系：

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

阅读 this 以了解技术。

寻找大数的斐波那契数

Finding the fibonacci number of large number

c++

dynamic

biginteger

fibonacci