首页  >  文章  >  后端开发  >  第n个卡塔兰数的C程序

第n个卡塔兰数的C程序

WBOY
WBOY转载
2023-08-28 14:25:14968浏览

第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中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除