Bell Number in Java

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

在本节中，我们将学习什么是贝尔数，并创建Java 程序来检查给定的数字是否为贝尔数。贝尔数程序经常在 Java 编码面试和学术中出现。

贝尔数

贝尔数是描述一个包含 N 个元素的集合可以被划分成多少个不相交的非空子集的一系列数字。

它用来表示一个包含 n 个元素的集合（非空）可以被划分成子集的数量。它也被称为指数数。换句话说，我们可以说贝尔数是集合的划分数。

它是 OEIS 序列A000110。前几个贝尔数是 1, 1, 2, 5, 15, 52, 203, 877, 4140 等。

贝尔数示例

考虑一个字母集 {a, b, c}。该集合包含三个元素。让我们找出给定集合的子集。

{{a}, {b}, {c}}; {{a}, {b, c}}; {{a, b}, {c}}; {{b}, {a ,c}}; {{a, b, c}}

我们观察到贝尔数给出了 (n, k) 的值，对于所有 k 值。其中 k 从 1 到 n，而集合 (n, k) 是 n 个元素划分成 k 个子集的数量。

数学上，我们可以写成如下

求贝尔数的方法

有以下三种方法可以求贝尔数：

使用 Dobinski 公式
第二类斯特林数的和
使用 Peirce 或贝尔三角形

使用 Dobinski 公式

我们可以使用以下 Dobinski 公式求第 n 个贝尔数

算法

N = [The n in Bn];
sum = 0;
iterations =[ A very large number (>=10000)  ]; 
for (i = 0; i < iterations; i++)
        sum = sum + ((pow(i,N)/(i!))
print (sum/e)

第二类斯特林数的和

计算 sum(n, k)。其中，k=1 到 n，以及所有数字的和。(n, k) 是第二类斯特林数。

我们可以使用以下公式求斯特林数

如果 n==k 或 k=1，则斯特林数将为 1。

算法

N = [The n in Bn];
sum = 0;
B(N) = S(N,k) for k = 1 to N
function S(n,k)
{
    if n == 0 or k == 0 or k > n
        return 0
    else 
{
        if k == 1 or n==k
            return 1
    }
    else 
        return k*S(n-1, k) + S(n-1, k-1)
}

使用 Peirce 或贝尔三角形

使用贝尔三角形是求贝尔数的最佳方法。它是一个数字三角形，类似于帕斯卡三角形。它计算集合的划分，其中给定元素是最大的单例。它以其与贝尔数的紧密联系而得名，贝尔数出现在三角形的两侧，而贝尔数又以Eric Temple Bell 的名字命名。

以下三角形用于求贝尔数。

让我们看看它是如何计算的。

从数字 1 开始，并将其放在一行（x_0,1 = 1）中。
在新的一行中，写下上一行的最右边的元素。最右边的数字成为新行的最左边的元素。
通过将左边的数字和左边数字的上方数字（即我们正在计算的数字的左上方对角线上的数字）相加来确定不在左列的数字。
重复上述步骤，直到出现一个新行，该行的数字比前一行多一个。
行左侧的数字是该行的贝尔数。

让我们在 Java 程序中实现上述逻辑。

贝尔数 Java 程序

BellNumberExample1.java

import java.io.*;
public class GFG
{
//function that finds nth Bell Number
static int bellNumber(int n)
{
int[][] bell = new int[n+1][n+1];
bell[0][0] = 1;
for (int i=1; i<=n; i++)
{
//explicitly fill for j = 0
bell[i][0] = bell[i-1][i-1];
// Fill for remaining values of j
for (int j=1; j<=i; j++)
bell[i][j] = bell[i-1][j-1] + bell[i][j-1];
}
return bell[n][0];
}
// Driver program
public static void main (String args[])
{
for (int n=0; n<=5; n++)
System.out.println("Bell Number "+ n +" is "+bellNumber(n));
}
}

输出

BellNumberExample2.java

import java.util.ArrayList;
import java.util.List;
public class BellNumberExample2 
{
private static class BellTriangle 
{
private List<Integer> arr;
BellTriangle(int n) 
{
int length = n * (n + 1) / 2;
arr = new ArrayList<>(length);
for (int i = 0; i < length; ++i) 
{
arr.add(0);
}
set(1, 0, 1);
for (int i = 2; i <= n; ++i) 
{
set(i, 0, get(i - 1, i - 2));
for (int j = 1; j < i; ++j) 
{
int value = get(i, j - 1) + get(i - 1, j - 1);
set(i, j, value);
}
}
}
private int index(int row, int col) 
{
if (row > 0 && col >= 0 && col < row) 
{
return row * (row - 1) / 2 + col;
} 
else 
{
throw new IllegalArgumentException();
}
}
public int get(int row, int col) 
{
int i = index(row, col);
return arr.get(i);
}
public void set(int row, int col, int value) 
{
int i = index(row, col);
arr.set(i, value);
}
}
public static void main(String args[]) 
{
final int rows = 15;
BellTriangle bt = new BellTriangle(rows);
System.out.println("First fifteen Bell numbers are:");
for (int i = 0; i < rows; ++i) 
{
System.out.printf("%2d: %d\n", i + 1, bt.get(i + 1, 0));
}
for (int i = 1; i <= 10; ++i) 
{
System.out.print(bt.get(i, 0));
for (int j = 1; j < i; ++j) 
{
System.out.printf(", %d", bt.get(i, j));
}
System.out.println();
}
}
}

输出

下一主题Padovan-sequence-in-java

Bell Number in Java

贝尔数

贝尔数示例

求贝尔数的方法

使用 Dobinski 公式

算法

第二类斯特林数的和

算法

使用 Peirce 或贝尔三角形

贝尔数 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

Bell Number in Java

贝尔数

贝尔数示例

求贝尔数的方法

使用 Dobinski 公式

算法

第二类斯特林数的和

算法

使用 Peirce 或贝尔三角形

贝尔数 Java 程序

相关帖子

Java 中的 synchronized 关键字

如何在 Java 中分解日期和时间

Check if DFS Strings are Palindromes in Java

Java 中一些棘手的程序

Java 中传递和返回对象

Java Absolute Value

Java 中包的优点

Design of JDBC

Job Sequencing Problem in Java

Java 8 之后的接口 vs. 抽象类

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器