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

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!