計算第n個加泰羅尼亞號

我寫了一些代碼來計算第N個加泰羅尼亞數。但是，當N = 20以後，它不會返回正確的結果。 N < 20的結果是正確的，所以我不確定有什麼問題。計算第n個加泰羅尼亞號

所以，當N = 20時，它應該返回6564120420，但是它返回給我2269153124。

有人能指出我正確的方向嗎？

#include <iostream> 

using namespace std; 

unsigned long int countTree(unsigned int N) 
{ 
    //used to store catalan numbers 
    unsigned long int catalan[N+1]; 

    //N(0)=N(1)=1 
    catalan[0]=catalan[1]=1;  
    int i,j; 

    for(i=2;i<=N;i++) 
    { 
     catalan[i]=0; 
     for(j=0;j<i;j++) 
     { 
      catalan[i]+=catalan[j]*catalan[i-j-1]; 
     } 
    } 
    return catalan[N]; 
} 

int main() 
{ 
    unsigned int x; 
    cout<<"Input N:"<<endl; 
    cin>>x; 
    unsigned long int result=countTree(x); 
    cout<<result<<endl; 
    return 0; 
}

來源

2014-08-28 user2211574

您超過了這些變量類型允許存儲的最大大小。

long long類型是你最好的選擇。

你可以在這裏看看什麼對不同類型的整數的最大值是：http://www.cplusplus.com/reference/climits/

來源

2014-08-28 02:40:27 Boop

啊，媽的。錯過了。謝謝。 – user2211574 2014-08-28 02:44:13

@ user2211574如果有幫助，'long long'保證至少有64位。如果你需要比這更大的數字，你可能需要查看像GMP這樣的專業圖書館。 – IllusiveBrian 2014-08-28 02:47:57

[只有鏈接的答案是強烈不鼓勵！]（http://meta.stackexchange.com/questions/225370/your-answer-is-in-another-castle-when-is-an-answer-not-an -answer） – 2014-08-28 02:48:21

使用「無符號的長長的」到位「無符號整型」 .`

#include <iostream> 

using namespace std; 

unsigned long long countTree(unsigned int N) 
{ 
    //used to store catalan numbers 
    unsigned long long catalan[N+1]; 

    catalan[0]=catalan[1]=1;  
    int i,j; 

    for(i=2;i<=N;i++) 
    { 
     catalan[i]=0; 
     for(j=0;j<i;j++) 
      catalan[i]+=catalan[j]*catalan[i-j-1]; 
    } 
    return catalan[N]; 
} 

int main() 
{ 
    unsigned int x; 
    cout << "Input N:" << endl; 
    cin >> x; 
    cout << countTree(x) << endl; 
    return 0; 
}

來源

2014-08-29 03:31:06

計算第n個加泰羅尼亞號

回答

相關問題