给定一个整数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 作为程序的输出
加泰罗尼亚数字的一些应用 -
Input: n = 6 Output: 132 Input: n = 8 Output: 1430
解决给定问题的方法 −
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中文网其他相关文章！
