n번째 카탈로니아어 수에 대한 C 프로그램

정수 n이 주어졌습니다. 임무는 n번째 위치에서 카탈로니아어 수를 찾는 것입니다. 그럼, 프로그램을 하기 전에 우리는 카탈로니아 수(Catalan Number)가 무엇인지 알아야 합니다.

카탈란 수(Catlan Number)는 자연수의 수열로, 다양한 계산 문제의 형태로 발생합니다.

카탈로니아 수 C0, C1, C2,… Cn은 공식에 의해 구동됨 −

$$c_{n}=frac{1}{n+1}binom{2n}{n} = frac{2n!}{(n+1)!n!}$$

The 모든 n = 0, 1, 2, 3, …에 대한 카탈로니아 숫자는 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

따라서 n =3을 입력하면 우리는 프로그램의 출력으로 5를 얻어야 합니다

카탈로니아 숫자의 몇 가지 응용 프로그램 중 일부 −

• n 키를 사용하여 가능한 이진 검색 트리의 수를 계산합니다.
• n 쌍의 괄호를 포함하는 표현식 수 찾기 정확하게 일치하는 것입니다. n = 3과 마찬가지로 가능한 괄호 표현은 ((())), ()(()), ()()(), (())(), (()())입니다.
• 찾는 숫자 원 분리 코드의 점을 연결하는 방법 및 기타 여러 가지 방법을 설명합니다.

检查如果n < ;= 1,则返回1

循环从i=0到i对于每个i,设置result = 결과 + (카탈로니아어(i)*카탈로니아어(n-i-1))

返回并打印结果。

算法

• Input: n = 6
  Output: 132
  Input: n = 8
  Output: 1430

Example
• 적중문翻译为：
示例

• Start
     Step 1 -> In 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++
           Set res = res + (catalan(i)*catalan(n-i-1))
        End Loop
        Return res
     Step 2 -> int main()
     Declare an input n = 6
     Print "catalan is : then call function catalan(n)
  Stop

输流

• #include <stdio.h>
  // using recursive approach to find the catalan number
  unsigned long int catalan(unsigned int n) {
     // Base case
     if (n <= 1) return 1;
     // catalan(n) is sum of catalan(i)*catalan(n-i-1)
     unsigned long int res = 0;
     for (int i=0; i<n; i++)
        res += catalan(i)*catalan(n-i-1);
     return res;
  }
  //Main function
  int main() {
     int n = 6;
     printf("catalan is :%ld</p><p>", catalan(n));
     return 0;
  }

위 내용은 n번째 카탈로니아어 수에 대한 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!