第n個卡塔蘭數的C/C++程式是什麼？

卡塔蘭數是一系列數字。卡塔蘭數是一系列自然數，在各種計數問題中出現，通常涉及遞歸定義的物件。

• C_n是長度為2n的Dyck字的數量。 Dyck字是由n個X和n個Y組成的字串，使得字串的任何初始片段中Y的數量不超過X的數量。例如，以下是長度為6的Dyck字：

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

• 將符號X重新解釋為開括號，Y解釋為閉括號，C_n 計算包含n對正確匹配的括號的表達式的數量

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

• C_n 是n 1 個因子可以完全括起來的不同方式的數量（或關聯二進位的n 個應用程式的方式數量）操作員）。例如，對於 n = 3，我們有以下四個因子的五個不同括號：

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

• 連續應用二元運算子可以用完全二元樹表示。 （如果每個頂點要么有兩個子節點，要么沒有子節點，則稱為根二叉樹是完全的。）由此可知，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中文網其他相關文章！