卡特兰数(Catalan)

卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。个人觉得和斐波那契数列差不多，卡特兰数的地推公式为：pre(n) = pre(0) * pre(n-1) pre(1) * pre(n-2)   ... pre(n-1) * pre(0) (n>=2)，pre[0] = pre[1] = 1;

以下公式摘自百度百科：

另类递推式：

pre[n] = pre[n-1] * (4 * n - 2) / (n 1);

递推关系的解为：

pre[n] = C(2n,n) / (n 1) (n=0,1,2,3...)

递推关系的另类解为：

pre[n] = C(2n,b) - C(2n,n-1) (n=0,1,2,3...)

下面的代码中用了递推式和另类递推式，用递推式可以输出前35个卡特兰数，另类递推式只能到33就爆了

代码语言：javascript复制

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
ll pre[36];

void Catalan(){
  pre[0] = 1;
  pre[1] = 1;
  for(ll i=2;i<=36;i  ){          // pre(n)=pre(n-1)*(4*n-2)/(n 1);
    pre[i] = pre[i-1] * (4 * i - 2) / (i   1);
  }
}

ll Catalan1(int n){
      if(n <= 1)return 1;
      pre[0] = pre[1] = 1;
      for(int i = 2; i <= n; i  ){
          pre[i] = 0;
          for(int j = 0; j < i; j  )   // pre(n)= pre(0)*pre(n-1) pre(1)*pre(n-2)   ...   pre(n-1)*pre(0)
              pre[i]  = (pre[j] * pre[i-1-j]);
      }
      return pre[n];
}

int main()
{
  Catalan();
  int n;
  cin>>n;
  cout<<pre[n]<<endl;
  cout<<Catalan1(n)<<endl;
  return 0;
}

百度 数学

0 人点赞