Рассчитайте n-е каталонское число
Я написал код для вычисления N-го каталонского числа. Тем не менее, он не возвращает правильный результат, когда N = 20 и далее. Результаты, когда N<20 правильно, так что я не уверен, что не так.
Таким образом, когда 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;
}
Решение
Вы превышаете максимальный размер, который могут хранить эти типы переменных.
long long Тип это ваша лучшая ставка.
Здесь вы можете посмотреть, каковы максимальные значения для различных типов целых чисел: http://www.cplusplus.com/reference/climits/
Другие решения
используйте «unsigned long long» вместо «unsigned int».
#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;
}