Catalan Number in Java

2025年5月8日 | 阅读6分钟

在本节中，我们将学习什么是卡塔兰数，并创建Java 程序来检查给定的数字是否为卡塔兰数。卡塔兰数程序经常在 Java 编码面试和学术中被问到。

有许多有趣的问题可以用卡塔兰数来解决。在数学上，卡塔兰数定义为：

查找卡塔兰数的步骤

步骤 1：为变量 n 赋一个非负整数。

步骤 2：求 ²ⁿC_n 的值，其中 n 是在步骤 1 中确定的。

步骤 3：将步骤 2 中得到的值除以 n+1。得到的结果就是一个卡塔兰数。

卡塔兰数示例

下图显示了从 0 到 3 的数字的卡塔兰数。

卡塔兰数 Java 程序

以下程序基于上面定义的步骤。

文件名： CatalanNumberExample.java

// A Java program to calculate the Catalan numbers
public class CatalanNumberExample 
{

// a method that finds the factorial of a number 
public long findFactorial(int no)
{
long res = 1;

// calculating the factorial
for(int i = 1; i <= no; i++)
{
res = res * i;
}

return res;
}

// A method that finds the Catalan number corresponding to 
// the number no
public long findCatalan(int no)
{

// for no = 0 & 1, the catalan number is 1
if(no <= 1) { return 1; }

// calculating 2n!
long fact = findFactorial(2 * no);

// calculating 2nCn
fact = fact / findFactorial(no);
fact = fact / findFactorial(no);

// caculating ((1 / (n + 1))* 2nCn)
fact = fact / (no + 1);

// returning the calculated Catalan number
return fact;
}

// main method
public static void main(String[] argvs)
{
// Creating an object of the class CatalanNumberExample
CatalanNumberExample obj = new CatalanNumberExample();

// Calculating catalan numbers from 0 to 10
for (int i = 0; i <= 10; i++) 
{
long catalanNo = obj.findCatalan(i);
System.out.println("For n = " + i + ", Catalan number is " + catalanNo);
}
}
}

输出

For n = 0, Catalan number is 1
For n = 1, Catalan number is 1
For n = 2, Catalan number is 2
For n = 3, Catalan number is 5
For n = 4, Catalan number is 14
For n = 5, Catalan number is 42
For n = 6, Catalan number is 132
For n = 7, Catalan number is 429
For n = 8, Catalan number is 1430
For n = 9, Catalan number is 4862
For n = 10, Catalan number is 16796

使用递归方法的卡塔兰数

我们也可以使用递归方法找到卡塔兰数。它可以定义如下。

同样，我们也可以找到其他值。请注意，在查找下一个项的卡塔兰数时，请使用前一项的值。例如，C(4) 的值取决于 C(0)、C(1)、C(2) 和 C(3)。

让我们在 Java 程序中实现递归方法。

文件名： CatalanNumberExample1.java

// A Java program to calculate the Catalan numbers from 0 to 10
public class CatalanNumberExample1 
{
 
// A method that returns the Catalan number for the number no  
int findCatalanNo(int no)
{
    // base case
    if(no <= 1)
    {
        return 1;
    }
    
    // for storing the catalan number
    int res = 0;
    for (int j = 0; j < no; j++)
    {
        // recursively find the catalan number
        res = res + findCatalanNo(j) * findCatalanNo(no - j - 1);
    }
    
    return res;
}

// main method
public static void main(String argvs[])
{
// creating an object of the class CatalanNumberExample1
CatalanNumberExample1 obj = new CatalanNumberExample1();

for(int i = 0; i <= 10; i++)
{
// find Catalan number for each value of i
int no = obj.findCatalanNo(i);

System.out.println("For number = " + i + ", the Catalan number is " + no);
}
}
}

输出

For number = 0, the Catalan number is 1
For number = 1, the Catalan number is 1
For number = 2, the Catalan number is 2
For number = 3, the Catalan number is 5
For number = 4, the Catalan number is 14
For number = 5, the Catalan number is 42
For number = 6, the Catalan number is 132
For number = 7, the Catalan number is 429
For number = 8, the Catalan number is 1430
For number = 9, the Catalan number is 4862
For number = 10, the Catalan number is 16796

使用动态规划

上面编写的递归程序需要花费很长时间来查找卡塔兰数。这是因为我们在 Java for 循环中使用递归。因此，我们需要找到另一种比上述方法花费时间更少的方法。

通过使用动态规划，我们可以减少时间。在这种方法中，我们将从递归转向迭代方法，因为迭代方法速度更快。观察下面相同的程序。

文件名： CatalanNumberExample2.java

// A Java program to calculate the Catalan numbers from 1 to 10
public class CatalanNumberExample2
{
// an integer array for storing the Catalan numbers
int arr[];
// constructor of the class
CatalanNumberExample1(int n)
{
// we have to store Catalan numbers from 0 to n; hence, n + 1
arr = new int[n + 1];
}
// A method that returns the Catalan number for the number no  
int findCatalanNo(int no)
{
     // for no = 0 & 1, Catalan number is 1
    arr[0] = 1;
    arr[1] = 1;
    // base case
    if(no <= 1)
    {
        return arr[no];
    }    
    // for storing the Catalan number
    int res = 0;
    for (int i = 1; i <= no; i++)
    {
        res = res + arr[i - 1] * arr[no - i];
    }
    
    // updating the array    
    arr[no] = res;
    
    // returning the calculated Catalan number
    return res;
}

// main method
public static void main(String argvs[])
{
// creating an object of the class CatalanNumberExample1
// to find the Catalan numbers from 0 to 10
CatalanNumberExample2 obj = new CatalanNumberExample2(10);
for(int i = 0; i <= 10; i++)
{
// find Catalan number for each value of i
int no = obj.findCatalanNo(i);
System.out.println("For number = " + i + ", the Catalan number is " + no);
}
}
}

输出

For number = 0, the Catalan number is 1
For number = 1, the Catalan number is 1
For number = 2, the Catalan number is 2
For number = 3, the Catalan number is 5
For number = 4, the Catalan number is 14
For number = 5, the Catalan number is 42
For number = 6, the Catalan number is 132
For number = 7, the Catalan number is 429
For number = 8, the Catalan number is 1430
For number = 9, the Catalan number is 4862
For number = 10, the Catalan number is 16796

解释：递归方法的问题在于它一遍又一遍地计算相同的子问题。这会导致更多的时间消耗。因此，我们使用一个数组 arr 来存储子问题的解决方案。因此，每当需要子问题的解决方案时，我们都可以从数组 arr 中使用它。因此，我们节省了重复子问题的计算时间。

卡塔兰数的应用

如上所述，可以使用卡塔兰数解决许多有趣的问题，其中一些问题如下。

1) 对于n > 0，唯一二叉搜索树的数量等于卡塔兰数 C(n)，其中 n 是二叉搜索树中存在的节点数。

2) 对于 n > 0，正确匹配的 n 对括号的总数等于卡塔兰数 C(n)。

3) 在圆上使用 2 × n 个点绘制的弦的总数，使得任意两条弦都不相交或接触，由卡塔兰数 C(n) 给出。

下一主题Java-program-to-tile-a-page-content-in-a-pdf

Catalan Number in Java

查找卡塔兰数的步骤

卡塔兰数示例

卡塔兰数 Java 程序

使用递归方法的卡塔兰数

使用动态规划

卡塔兰数的应用

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Catalan Number in Java

查找卡塔兰数的步骤

卡塔兰数示例

卡塔兰数 Java 程序

使用递归方法的卡塔兰数

使用动态规划

卡塔兰数的应用

相关帖子

Java 函数

Java 中复选框和单选按钮的区别

Package java.time Does Not Exist

ConcurrentModificationException

Java Servlets 和 CGI 的区别

在 Java 中获取本地 IP 地址

Java 中多线程的缺点

Java 中的组合设计模式

Java 中使用多线程进行归并排序

How to Sort HashMap by Value

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器