算法设计（第n个卡塔兰数算法实现）

本文概述

C ++
Java
python
C#
的PHP
C ++
Java
python
C#
的PHP
C ++
Java
Python3
C#
的PHP
C ++
Java

卡塔兰数是一个自然数序列，出现在许多有趣的计数问题中，如下列。
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)

// 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

时间复杂度上述实现的等价于第n个卡塔兰数。

文章图片
【算法设计（第n个卡塔兰数算法实现）】第n个卡塔兰数的值是指数的, 这使得时间复杂度是指数的。
动态编程解决方案：我们可以看到上面的递归实现做了很多重复的工作(我们可以通过绘制递归树来实现)。由于存在重叠的子问题, 我们可以为此使用动态编程。以下是基于动态编程的实现。
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

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

时间复杂度：上述实现的时间复杂度为O(n^2)
使用二项式系数
我们还可以使用以下公式在O(n)时间中找到第n个卡塔兰数字。

文章图片
我们已经讨论了O(n)方法求二项式系数nCr.
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# 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

时间复杂度：
上述实现的时间复杂度为O(n)。
我们还可以使用以下公式在O(n)时间中找到第n个卡塔兰数。

文章图片
使用多精度库：在这种方法中, 我们使用了boost多精度库, 其使用的动机只是在找到大型CATALAN数的同时, 还具有精确性, 并且使用了for循环的通用技术来计算卡塔兰数。

例如：N = 5最初设置cat_ = 1然后打印cat_, 然后对于i = 1从i = 1迭代到i < 5； cat_ = cat_ *(4 * 1-2)= 1 * 2 = 2 cat_ = cat_ /(i + 1)= 2/2 = 1对于i = 2; cat_ = cat_ *(4 * 2-2)= 1 * 6 = 6 cat_ = cat_ /(i + 1)= 6/3 = 2对于i = 3：-cat_ = cat_ *(4 * 3-2)= 2 * 10 = 20 cat_ = cat_ /(i + 1)= 20/4 = 5对于i = 4：-cat_ = cat_ *(4 * 4-2)= 5 * 14 = 70 cat_ = cat_ /(i + 1)= 70/5 = 14

伪代码：

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

时间复杂度：O(n)
辅助空间：O(1)
在Java中使用BigInteger的另一种解决方案：

即使在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

输出如下