首页 > 文章列表 > 第n个卡塔兰数的C/C++程序是什么?

第n个卡塔兰数的C/C++程序是什么?

C/C程序 卡塔兰数
261 2023-09-18

卡塔兰数是一系列数字。卡塔兰数是一系列自然数,在各种计数问题中出现,通常涉及递归定义的对象。

第n个卡塔兰数的C/C++程序是什么?第n个卡塔兰数的C/C++程序是什么?

  • Cn是长度为2n的Dyck词的数量。Dyck词是由n个X和n个Y组成的字符串,使得字符串的任何初始片段中Y的数量不超过X的数量。例如,以下是长度为6的Dyck词:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
  • 将符号X重新解释为开括号,将Y解释为闭括号,Cn计算包含n对正确匹配的括号的表达式的数量

((())) ()(()) ()()() (())() (()())
  • Cn 是 n + 1 个因子可以完全括起来的不同方式的数量(或者关联二进制的 n 个应用程序的方式数量)操作员)。例如,对于 n = 3,我们有以下四个因子的五个不同括号:

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
  • 连续应用二元运算符可以用完全二叉树表示。(如果每个顶点要么有两个子节点,要么没有子节点,则称为根二叉树是完全的。)由此可知,Cn是具有n + 1个叶子的完全二叉树的数量:

示例

输入 - 6

输出 - 1 1 2 5 14 42

解释

当n = 0, 1, 2, 3,4,5,6,7,8,9,10, ...时,前n个卡塔兰数为

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,

例子

#include<iostream>
using namespace std;
long int catalan( int n) {
   if (n <= 1){
      return 1;
   }
   long int result = 0;
   for (int i=0; i<n; i++){
      result += catalan(i)*catalan(n-i-1);
   }
   return result;
}
int main(){
   for (int i=0; i<6; i++)
   cout << catalan(i) << " ";
   return 0;
}

输出

1 1 2 5 14 42