第n个卡塔兰数的C程序

Given an interger n; the task is to find the Catalan Number on that nth position. So, before doing the program we must know what is a Catalan Number?

Catlan numbers are the sequence of natural numbers, which occurs in the form of various counting number problems.

Catalan numbers C0, C1, C2,… Cn are driven by formula −

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

The few Catalan numbers for every n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

MiniMax开放平台

MiniMax-与用户共创智能，新一代通用大模型

下载

So if we entered n =3 we should get 5 as an output from the program

Some of few applications of Catalan numbers −

• Counting the number of possible binary search trees with n keys.
• Finding the number of expressions containing n pair of parenthesis which are correctly matched. Like for n = 3 the possible parenthesis expression would be ((())), ()(()), ()()(), (())(), (()()).
• Finding number of ways to connect point on circle disjoint chords, and many more.

Example

示例

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

解决给定问题的方法 −

• 输入n。
• 检查如果n
• 循环从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 int main()
   Declare an input n = 6
   Print "catalan is : then call function catalan(n)
Stop

Example

示例

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

输出

catalan is :132