C program for the nth Catalan number

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, …

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 <= 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

Example

的中文翻译为：

示例

#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

The above is the detailed content of C program for the nth Catalan number. For more information, please follow other related articles on the PHP Chinese website!