n번째 카탈루냐 숫자를 위한 C/C++ 프로그램?

<시간/>

카탈루냐 숫자는 일련의 숫자입니다. 카탈루냐 숫자는 다양한 계산 문제에서 발생하는 일련의 자연수를 형성하며, 종종 재귀적으로 정의된 객체를 포함합니다.

C_n 는 길이가 2n인 Dyck 워드의 수입니다. Dyck 단어는 n개의 X와 n개의 Y로 구성된 문자열로 문자열의 초기 세그먼트에는 X보다 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))

이항 연산자의 연속적인 적용은 전체 이진 트리로 나타낼 수 있습니다. (모든 정점에 두 개의 자식이 있거나 없는 경우 루트 이진 트리가 가득 찼습니다.) 다음은 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