书海扬帆的博客

题目


给定整数n,求卡特兰数的第n项。

分析


利用杨辉三角性质打表算出组合数即可计算。

代码分享


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
//Catalan数:求C(2n,n)/n+1
long long a[100][100],n;

int main() {
scanf("%lld",&n);
a[1][1]=a[1][2]=1;
for(long long i=2;i<=2*n;i++){
for(long long j=1;j<=i+1;j++){
a[i][j]=a[i-1][j]+a[i-1][j-1];
//printf("%d ",a[i][j]);
}
//printf("\n");
}
long long ans=a[2*n][n+1]/(n+1);
printf("%lld\n",ans);
return 0;
}



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k