n番目のカタラン数のC/C ++プログラム？

カタラン数は一連の数です。カタラン数は、さまざまなカウントの問題で発生する一連の自然数を形成します。多くの場合、再帰的に定義されたオブジェクトが関係します。

• C _n 長さ2nのディック言語の数です。ディックワードは、n個のXとn個のYで構成される文字列であり、文字列の最初のセグメントにXより多くのYが含まれることはありません。たとえば、次は長さ6のディック言語です

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

• 記号Xを開き括弧として、Yを閉じ括弧として再解釈します。C _n 正しく一致するn組の括弧を含む式の数をカウントします

((())) ()(()) ()()() (())() (()())

• C _n は、n + 1個の因子を完全に括弧で囲むことができるさまざまな方法の数（または2項演算子のn個のアプリケーションを関連付ける方法の数）です。たとえば、n =3の場合、4つの要素を次の5つの異なる括弧で囲みます。

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

• 二項演算子の連続するアプリケーションは、完全な二分木で表すことができます。 （すべての頂点に2つの子があるか、子がない場合、ルート化された二分木はいっぱいになります。）したがって、C _n n +1枚の葉を持つ完全な二分木の数です：

サンプル

入力 -6
出力 --1 1 2 5 14 42

説明

n =0、1、2、3、4、5、6、7、8、9、10、...の最初のカタラン数は
1、1、2、5、14、42、132、429、1430、4862、

例

#include<iostream>
using namespace std;
long int catalan( int n) {
   if (n <= 1){
      return 1;
   }
   long int result = 0;
   for (int i=0; i<n; i++){
      result += catalan(i)*catalan(n-i-1);
   }
   return result;
}
int main(){
   for (int i=0; i<6; i++)
   cout << catalan(i) << " ";
   return 0;
}

出力

1 1 2 5 14 42