第n个加泰罗尼亚语编号C程序

给定整数n; 任务是在第n个位置上找到加泰罗尼亚编号。因此，在执行程序之前，我们必须知道什么是加泰罗尼亚语数字？

Catlan数是自然数的序列，以各种计数数问题的形式出现。

加泰罗尼亚语数字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一样，可能的括号表达式为（（（()）），()（()），()()()，（()）()，（()()）。

• 寻找在圆不相交的弦上连接点的方法，等等。

示例

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

我们将用来解决给定问题的方法-

• 取并输入n。

• 检查n <= 1，然后返回1

• 从i = 0循环到i <n和i ++

• 对于每个i Set结果=结果+（catalan(i)* catalan(ni-1)）

• 返回并打印结果。

算法

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>
//使用递归方法找到加泰罗尼亚数字
unsigned long int catalan(unsigned int n) {
   //基本情况
   if (n <= 1) return 1;
   //加泰罗尼亚语(n)是加泰罗尼亚语(i)*加泰罗尼亚语(ni-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 is :%ld\n", catalan(n));
   return 0;
}

输出结果

catalan is :132