n번째 카탈루냐어 번호 C 프로그램

정수 n이 주어졌을 때; n번째 위치에서 카탈루냐 번호를 찾는 작업입니다. 따라서, 프로그램을 실행하기 전에 무엇이 카탈루냐어 숫자인지 알아야 합니다?

카탈루냐 수는 자연수의 시퀀스로, 여러 가지 세계수 문제의 형태로 나타납니다.

카탈루냐어 숫자 C0, C1… C2… Cn은 공식에 의해 이끌려-

$$c_ {n} = \frac {1} {n + 1} \binom {2n} {n} = \frac {2n！} {（n + 1）！n！} $$

매 n = 0、1、2、3…의 카탈루냐어 숫자는1、1、2、5、14、42、132、429、1430、4862 ...

따라서, 우리가 입력하면 n = 3우리는 프로그램에서 얻어야 합니다5출력으로 사용됩니다

카탈루냐 수의 일부 응용-

• n개의 키를 사용하여 가능한 이진 탐색 트리의 수를 계산합니다.

• n쌍의 올바른 괄호가 일치하는 표현식의 수를 찾습니다. 예를 들어 n = 3그런 다음, 가능한 괄호 표현식은 ((), ()(), ()(), ()(), ()()())입니다.

• 원형에서 교차하지 않는 장선에 연결점을 찾는 방법 등을 찾습니다.

예제

입력: n =　6
출력:　132
입력: n =　8
출력:　1430

해결할 문제를 위해 사용할 메서드-

• n을 입력받습니다.

• n <= 1을 돌면서, 그런 다음 반환1

• i = 0에서 시작하여 i < n과 i ++

• 각 i에 대해 결과=결과 설정+（catalan(i)* catalan(n-1)）

• 결과를 출력하고 반환합니다.

알고리즘

시작
　　　단계　1　-> function unsigned long int catalan(unsigned int n)
　　　　　　If n <=　1　then,
　　　　　　　　　Return　1
　　　　　　End if
　　　　　　Declare an unsigned long variable res = 0
　　　　　　Loop For i=0 and i<n and i++
　　　　　　　　　res = res　+　(catalan(i)*catalan(n-i-1))
　　　　　　반복 종료
　　　　　　return res
　　　단계　2　-> int main() Declare an input n =　6
　　　"catalan은 다음과 같습니다: " 출력한 후 function catalan(n) 호출
정지

예제

#include <stdio.h>
//카탈루냐 수를 찾기 위한 재귀 메서드를 사용합니다
unsigned long int catalan(unsigned int n) {
　　　//기본적인 상황
　　　if (n <=　1) return　1;
　　　//카탈루냐어(n)은 카탈루냐어(i)*카탈루냐어(n)-1)의 합
　　　unsigned long int res = 0;
　　　for (int i = 0; i < n; i++)
　　　　　　res　+= catalan(i)*catalan(n-i-1);
　　　return res;
}
//주요 기능
int main() {
　　　int n =　6;
　　　printf("catalan은 다음과 같습니다:%ld\n", catalan(n));
　　　return 0;
}

출력 결과

catalan은 다음과 같습니다:132