给定一个整数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中文网其他相关文章!