第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 一样，可能的括号表达式将是 ((()))、()(())、()()()、(())()、(()())。
• 查找数字连接圆上不相交和弦上的点的方法，等等。

示例

的中文翻译为：

示例

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

解决给定问题的方法 −

• 输入n。
• 检查如果n < ;= 1，则返回1
• 循环从i=0到i
• 对于每个i，设置result = result + (catalan(i)*catalan(n-i-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>
// 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;
}

输出

catalan is :132

以上是第n个卡塔兰数的C程序的详细内容。更多信息请关注PHP中文网其他相关文章！