第 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
", catalan(n));
   return 0;
}

输出

catalan is :132

更新于： 2019年11月20日

1K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告