您的当前位置:首页正文

卡特兰数详解

2024-09-09 来源:汇意旅游网


关于卡特兰数:

卡特兰数是一种经典的组合数,经常出现在各种计算中,其前几项为 : 
   1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786……

计算公式

卡特兰数一般的计算公式:

一般性质

Cn的另一个表达形式为

卡塔兰数满足以下递推关系 

所有的奇卡塔兰数Cn都满足n = 2^k − 1。 
所有其他的卡塔兰数都是偶数。

代码实现:


int main()
{
    ios::sync_with_stdio(false);
    long long Catalan[100],ans;//范围自行高精度或者取模
    int n;
    Catalan[0] = 1;
    for(int i = 1;i < n;++i) Catalan[i] = Catalan[i - 1] * i;
    while(cin >> n){
        ans = Catalan[n << 1] / (Catalan[n] * Catalan[n + 1]);
        cout << ans << endl;
    }
    return 0;
}

 

因篇幅问题不能全部显示,请点此查看更多更全内容