查找大數的斐波納契數

我寫了下面的程序來查找大斐波納契數的模數。這可以解決大數目，但無法計算如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

查找大數的斐波納契數

回答

相關問題