n番目のカタロニア語番号のC/C++プログラムは何ですか?

カタロニア語の数字は一連の数字です。カタロニア数は、さまざまな計数問題に現れる一連の自然数であり、多くの場合、再帰的に定義されたオブジェクトが関係します。

• C_n は、長さ 2n の Dyck ワードの数です。 Dyck ワードは、文字列の最初のフラグメント内で Y の数が X の数を超えないように、n 個の X と n 個の Y で構成される文字列です。たとえば、次は長さ 6 の Dyck ワードです。

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

• は、記号 X を左括弧、Y を閉じ括弧として再解釈します (C_{)。 n} 正しく一致する括弧の n 組を含む式の数を計算します。

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

• C_n は、完全に一致する n 1 個の因子です。囲み 結合するさまざまな方法の数 (または、二項演算子の 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、...の場合、最初のn個のカタルーニャ数字は

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

以上がn番目のカタロニア語番号のC/C++プログラムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。