第 n 个 Catalan 数的 C 程序
cserver side programmingprogramming
给定一个整数 n；任务是找到第 n 个位置上的 Catalan 数。因此，在执行程序之前，我们必须知道什么是 Catalan 数?
Catlan 数是自然数序列，以各种计数问题的形式出现。
Catalan 数 C0、C1、C2、…Cn 由公式 − 驱动
$$c_{n}=\frac{1}{n+1}\binom{2n}{n} = \frac{2n!}{(n+1)!n!}$$
每个 n = 0、1、2、3、…的几个 Catalan 数是 1、1、2、5、14、42、132、429、1430、4862，…
因此，如果我们输入 n =3，程序应该会输出 5
加泰罗尼亚数字的一些应用 −
- 计算具有 n 个键的可能二叉搜索树的数量。
- 查找包含 n 对括号的表达式的数量，这些表达式正确匹配。例如，对于 n = 3，可能的括号表达式将是 ((())), ()(()), ()()(), (())(), (()())。
- 寻找连接圆上不相交弦点的方法数量，等等。
示例
输入:n = 6 输出:132 输入:n = 8 输出:1430
我们将使用的方法来解决给定的问题 −
- 取并输入 n。
- 检查如果 n <= 1，则返回 1
- 从 i=0 循环到 i<n 并 i++
- 对于每个 i，设置 result = result + (catalan(i)*catalan(n-i-1))
- 返回并打印结果。
算法
Start 步骤 1 -> 在函数 unsigned long int catalan(unsigned int n) 中 如果 n <= 1，则 返回 1 End if 声明一个 unsigned long 变量 res = 0 循环 For i=0 and i<n and i++ 设置 res = res + (catalan(i)*catalan(n-i-1)) 结束循环 返回 res 步骤 2 -> int main() 声明输入 n = 6 打印 "catalan is : 然后调用函数 catalan(n) 停止
示例
#include <stdio.h>
// 使用递归方法查找 catalan 数字
unsigned long int catalan(unsigned int n) {
// 基本情况
if (n <= 1) return 1;
// catalan(n) 是 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
", catalan(n));
return 0;
}
输出
catalan is :132
