What is the C/C++ program for the nth Catalan number?

Catalan numbers are a series of numbers. Catalan numbers are a sequence of natural numbers that appear in a variety of counting problems, often involving recursively defined objects.

• C_n is the number of Dyck words with length 2n. A Dyck word is a string consisting of n X's and n Y's such that the number of Y's does not exceed the number of X's in any initial fragment of the string. For example, the following is a Dyck word of length 6:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

• reinterprets the symbol X as an open bracket and Y as a closing bracket, C_n Calculate the number of expressions containing n pairs of correctly matching brackets

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

• C_n is n 1 factors that can be completely enclosed The number of different ways to get together (or the number of ways to associate n applications of binary operators). For example, for n = 3, we have five different brackets for the following four factors:

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

• Successive application of binary operators can be represented by a complete binary tree. (A rooted binary tree is said to be complete if each vertex has either two child nodes or no child nodes.) It follows that C_n is the number of complete binary trees with n 1 leaves:

Example

Input - 6

Output - 1 1 2 5 14 42

Explanation

When n = 0, 1, 2, 3,4,5,6,7,8,9,10, ..., the first n Catalan numbers are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,

Example

#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;
}

Output

1 1 2 5 14 42

The above is the detailed content of What is the C/C++ program for the nth Catalan number?. For more information, please follow other related articles on the PHP Chinese website!