# 算法设计：第n个卡塔兰数算法实现

2021年3月26日17:10:40 发表评论 1,094 次浏览

## 本文概述

1. 计算包含n对正确匹配的圆括号的表达式的数量。对于n = 3,可能的表达式 ((())), ()(()), ()()(), (())(), (()()).

2. 计算可能有n个键的二叉搜索树的数量

3. 计算具有n + 1个叶子的完整二​​叉树的数目(如果每个顶点有两个子树或没有子树, 则有根的二叉树将是完整的)。

4. 给定数字n, 返回可以在2 x n点的圆中绘制n个和弦的方式数, 以使2个和弦不相交。

n = 0, 1, 2, 3，…的前几个卡塔兰数字是1,1,2,5,14,42,132,429,1430,4862，…

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

## C ++

``````#include <iostream>
using namespace std;

// A recursive function to find nth 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;
}

// Driver code
int main()
{
for ( int i = 0; i < 10; i++)
cout << catalan(i) << " " ;
return 0;
}``````

## Java

``````class CatalnNumber {

// A recursive function to find nth catalan number

int catalan( int n)
{
int res = 0 ;

// Base case
if (n <= 1 )
{
return 1 ;
}
for ( int i = 0 ; i < n; i++)
{
res += catalan(i)
* catalan(n - i - 1 );
}
return res;
}

// Driver Code
public static void main(String[] args)
{
CatalnNumber cn = new CatalnNumber();
for ( int i = 0 ; i < 10 ; i++)
{
System.out.print(cn.catalan(i) + " " );
}
}
}``````

## python

``````# A recursive function to
# find nth catalan number
def catalan(n):
# Base Case
if n < = 1 :
return 1

# Catalan(n) is the sum
# of catalan(i)*catalan(n-i-1)
res = 0
for i in range (n):
res + = catalan(i) * catalan(n - i - 1 )

return res

# Driver Code
for i in range ( 10 ):
print catalan(i), # This code is contributed by
# Nikhil Kumar Singh (nickzuck_007)``````

## C#

``````// A recursive C# program to find
// nth catalan number
using System;

class GFG {

// A recursive function to find
// nth catalan number
static int catalan( int n)
{
int res = 0;

// Base case
if (n <= 1)
{
return 1;
}
for ( int i = 0; i < n; i++)
{
res += catalan(i)
* catalan(n - i - 1);
}
return res;
}

// Driver Code
public static void Main()
{
for ( int i = 0; i < 10; i++)
Console.Write(catalan(i) + " " );
}
}

// This code is contributed by
// nitin mittal.``````

## 的PHP

``````<?php
// PHP Program for nth
// Catalan Number

// A recursive function to
// find nth catalan number
function catalan( \$n )
{

// Base case
if ( \$n <= 1)
return 1;

// catalan(n) is sum of
// catalan(i)*catalan(n-i-1)
\$res = 0;
for ( \$i = 0; \$i < \$n ; \$i ++)
\$res += catalan( \$i ) *
catalan( \$n - \$i - 1);

return \$res ;
}

// Driver Code
for ( \$i = 0; \$i < 10; \$i ++)
echo catalan( \$i ), " " ;

// This code is contributed aj_36
?>``````

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

## C ++

``````#include <iostream>
using namespace std;

// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
// Table to store results of subproblems
unsigned long int catalan[n + 1];

// Initialize first two values in table
catalan[0] = catalan[1] = 1;

// Fill entries in catalan[] using recursive formula
for ( int i = 2; i <= n; i++)
{
catalan[i] = 0;
for ( int j = 0; j < i; j++)
catalan[i] += catalan[j]
* catalan[i - j - 1];
}

// Return last entry
return catalan[n];
}

// Driver code
int main()
{
for ( int i = 0; i < 10; i++)
cout << catalanDP(i) << " " ;
return 0;
}``````

## Java

``````class GFG {

// A dynamic programming based function to find nth
// Catalan number
static int catalanDP( int n)
{
// Table to store results of subproblems
int catalan[] = new int [n + 2 ];

// Initialize first two values in table
catalan[ 0 ] = 1 ;
catalan[ 1 ] = 1 ;

// Fill entries in catalan[]
// using recursive formula
for ( int i = 2 ; i <= n; i++)
{
catalan[i] = 0 ;
for ( int j = 0 ; j < i; j++)
{
catalan[i]
+= catalan[j]
* catalan[i - j - 1 ];
}
}

// Return last entry
return catalan[n];
}

// Driver code
public static void main(String[] args)
{
for ( int i = 0 ; i < 10 ; i++) {
System.out.print(catalanDP(i) + " " );
}
}
}
// This code contributed by Rajput-Ji``````

## python

``````# A dynamic programming based function to find nth
# Catalan number

def catalan(n):
if (n = = 0 or n = = 1 ):
return 1

# Table to store results of subproblems
catalan = [ 0 for i in range (n + 1 )]

# Initialize first two values in table
catalan[ 0 ] = 1
catalan[ 1 ] = 1

# Fill entries in catalan[]
# using recursive formula
for i in range ( 2 , n + 1 ):
catalan[i] = 0
for j in range (i):
catalan[i] + = catalan[j]
catalan[i] * = catalan[i - j - 1 ]

# Return last entry
return catalan[n]

# Driver code
for i in range ( 10 ):
print (catalan(i), end = " " )
# This code is contributed by Aditi Sharma``````

## C#

``````using System;

class GFG {

// A dynamic programming based
// function to find nth
// Catalan number
static uint catalanDP( uint n)
{
// Table to store results of subproblems
uint [] catalan = new uint [n + 2];

// Initialize first two values in table
catalan[0] = catalan[1] = 1;

// Fill entries in catalan[]
// using recursive formula
for ( uint i = 2; i <= n; i++) {
catalan[i] = 0;
for ( uint j = 0; j < i; j++)
catalan[i]
+= catalan[j] * catalan[i - j - 1];
}

// Return last entry
return catalan[n];
}

// Driver code
static void Main()
{
for ( uint i = 0; i < 10; i++)
Console.Write(catalanDP(i) + " " );
}
}

// This code is contributed by Chandan_jnu``````

## 的PHP

``````<?php
// PHP program for nth Catalan Number

// A dynamic programming based function
// to find nth Catalan number
function catalanDP( \$n )
{

// Table to store results
// of subproblems
\$catalan = array ();

// Initialize first two
// values in table
\$catalan [0] = \$catalan [1] = 1;

// Fill entries in catalan[]
// using recursive formula
for ( \$i = 2; \$i <= \$n ; \$i ++)
{
\$catalan [ \$i ] = 0;
for ( \$j = 0; \$j < \$i ; \$j ++)
\$catalan [ \$i ] += \$catalan [ \$j ] *
\$catalan [ \$i - \$j - 1];
}

// Return last entry
return \$catalan [ \$n ];
}

// Driver Code
for ( \$i = 0; \$i < 10; \$i ++)
echo catalanDP( \$i ) , " " ;

// This code is contributed anuj_67.
?>``````

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

## C ++

``````// C++ program for nth Catalan Number
#include <iostream>
using namespace std;

// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n, unsigned int k)
{
unsigned long int res = 1;

// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;

// Calculate value of [n*(n-1)*---*(n-k+1)] /
// [k*(k-1)*---*1]
for ( int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}

return res;
}

// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n)
{
// Calculate value of 2nCn
unsigned long int c = binomialCoeff(2 * n, n);

// return 2nCn/(n+1)
return c / (n + 1);
}

// Driver code
int main()
{
for ( int i = 0; i < 10; i++)
cout << catalan(i) << " " ;
return 0;
}``````

## Java

``````// Java program for nth Catalan Number

class GFG {

// Returns value of Binomial Coefficient C(n, k)
static long binomialCoeff( int n, int k)
{
long res = 1 ;

// Since C(n, k) = C(n, n-k)
if (k > n - k) {
k = n - k;
}

// Calculate value of [n*(n-1)*---*(n-k+1)] /
// [k*(k-1)*---*1]
for ( int i = 0 ; i < k; ++i) {
res *= (n - i);
res /= (i + 1 );
}

return res;
}

// A Binomial coefficient based function
//  to find nth catalan number in O(n) time
static long catalan( int n)
{
// Calculate value of 2nCn
long c = binomialCoeff( 2 * n, n);

// return 2nCn/(n+1)
return c / (n + 1 );
}

// Driver code
public static void main(String[] args)
{
for ( int i = 0 ; i < 10 ; i++) {
System.out.print(catalan(i) + " " );
}
}
}``````

## Python3

``````# Python program for nth Catalan Number
# Returns value of Binomial Coefficient C(n, k)

def binomialCoefficient(n, k):

# since C(n, k) = C(n, n - k)
if (k > n - k):
k = n - k

# initialize result
res = 1

# Calculate value of [n * (n-1) *---* (n-k + 1)]
# / [k * (k-1) *----* 1]
for i in range (k):
res = res * (n - i)
res = res / (i + 1 )
return res

# A Binomial coefficient based function to
# find nth catalan number in O(n) time

def catalan(n):
c = binomialCoefficient( 2 * n, n)
return c / (n + 1 )

# Driver Code
for i in range ( 10 ):
print (catalan(i), end = " " )

# This code is contributed by Aditi Sharma``````

## C#

``````// C# program for nth Catalan Number
using System;
class GFG {

// Returns value of Binomial Coefficient C(n, k)
static long binomialCoeff( int n, int k)
{
long res = 1;

// Since C(n, k) = C(n, n-k)
if (k > n - k) {
k = n - k;
}

// Calculate value of [n*(n-1)*---*(n-k+1)] /
// [k*(k-1)*---*1]
for ( int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}

return res;
}

// A Binomial coefficient based function to find nth
// catalan number in O(n) time
static long catalan( int n)
{
// Calculate value of 2nCn
long c = binomialCoeff(2 * n, n);

// return 2nCn/(n+1)
return c / (n + 1);
}

// Driver code
public static void Main()
{
for ( int i = 0; i < 10; i++) {
Console.Write(catalan(i) + " " );
}
}
}

// This code is contributed
// by Akanksha Rai``````

## 的PHP

``````<?php
// PHP program for nth Catalan Number

// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff( \$n , \$k )
{
\$res = 1;

// Since C(n, k) = C(n, n-k)
if ( \$k > \$n - \$k )
\$k = \$n - \$k ;

// Calculate value of [n*(n-1)*---*(n-k+1)] /
//                    [k*(k-1)*---*1]
for ( \$i = 0; \$i < \$k ; ++ \$i )
{
\$res *= ( \$n - \$i );
\$res = floor ( \$res / ( \$i + 1));
}

return \$res ;
}

// A Binomial coefficient based function
// to find nth catalan number in O(n) time
function catalan( \$n )
{
// Calculate value of 2nCn
\$c = binomialCoeff(2 * ( \$n ), \$n );

// return 2nCn/(n+1)
return floor ( \$c / ( \$n + 1));
}

// Driver code
for ( \$i = 0; \$i < 10; \$i ++)
echo catalan( \$i ), " " ;

// This code is contributed by Ryuga
?>``````

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

``````a) initially set cat_=1 and print it
b) run a for loop i=1 to i<=n
cat_ *= (4*i-2)
cat_ /= (i+1)
print cat_
c) end loop and exit``````

## C ++

``````#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;

// Function to print the number
void catalan( int n)
{
cpp_int cat_ = 1;

// For the first number
cout << cat_ << " " ; // C(0)

// Iterate till N
for (cpp_int i = 1; i < n; i++)
{
// Calculate the number
// and print it
cat_ *= (4 * i - 2);
cat_ /= (i + 1);
cout << cat_ << " " ;
}
}

// Driver code
int main()
{
int n = 5;

// Function call
catalan(n);
return 0;
}``````

``1 1 2 5 14``

• 即使在Java中使用long也不可能找到N> 80的卡塔兰数字值, 因此我们使用BigInteger
• 在这里, 我们找到了使用上述二项式系数法的解决方案

## Java

``````import java.io.*;
import java.util.*;
import java.math.*;

class GFG
{
public static BigInteger findCatalan( int n)
{
// using BigInteger to calculate large factorials
BigInteger b = new BigInteger( "1" );

// calculating n!
for ( int i = 1 ; i <= n; i++) {
b = b.multiply(BigInteger.valueOf(i));
}

// calculating n! * n!
b = b.multiply(b);

BigInteger d = new BigInteger( "1" );

// calculating (2n)!
for ( int i = 1 ; i <= 2 * n; i++) {
d = d.multiply(BigInteger.valueOf(i));
}

// calculating (2n)! / (n! * n!)
BigInteger ans = d.divide(b);

// calculating (2n)! / ((n! * n!) * (n+1))
ans = ans.divide(BigInteger.valueOf(n + 1 ));
return ans;
}

// Driver Code
public static void main(String[] args)
{
int n = 5 ;
System.out.println(findCatalan(n));
}
}
// Contributed by Rohit Oberoi``````

``42``

http://en.wikipedia.org/wiki/Catalan_number