查找大数的斐波纳契数

我写了下面的程序来查找大斐波纳契数的模数。这可以解决大数目，但无法计算如fibo_dynamic(509618737,4602,229176339)，其中a = 509618737，b = 4602和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]; 
     } 
    } 
}

来源

2016-07-24 user2631013

请检查“long long”的容量或范围，看看是否溢出。如果您的编译器支持，您可以使用'unsigned long long'扩展范围。 –

还要检查编译器或平台的堆栈容量。每个递归都将数据存储在堆栈上。 –

您需要验证您是否未超出阵列的边界。您需要传递数组的容量，以便进行比较。 –

这些值将溢出，因为斐波那契数增加得非常快。即使对于原始斐波那契数列（其中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个斐波纳契数。它是“使用矩阵求幂来解决复发关系”。斐波那契数遵循以下线性递推关系：

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

阅读this了解技术。

来源

2016-07-24 19:45:26 Shubham

查找大数的斐波纳契数

回答

相关问题