贝尔编号-用C ++划分集合的方式数量

铃号 用于表示一组n个元素可以划分为多个非空子集（即具有至少一个元素）的方式的数量。

在此程序中，我们给了n个元素的集合，我们必须找到将集合划分为非空子集的多种方法。

示例

Input : 3 Output : 5

解释 -设三个元素{1，2，3}。

子集为{{1}，{2}，{3}}；{{1}，{2,3}};{{1，2}，{3}}；{{2}，{1，3}};{1、2、3}。

贝尔号：贝尔号bell(n)给出k的所有值（从1到n）的s(n,k)之和。s(n,k)是将n个元素划分为k个子集的数量。

公式将是-

$$bell(n)=\sum_{k=0}^nS(n,k)$$

函数s(n,k)递归为-

s（n+1，k）=k*s(n,k)+s(n,k-1)。

加工

将第（n+1）个元素添加到k个分区时，有两种可能性-

它将一个添加到现有分区的k个分区中，即s(n,k-1)。

将值添加到所有分区集，即k*s(n,k)。

前几个贝尔编号是1，1，2，2,5，15，52，205

为了找到钟声，我们有几种方法，

一种简单的方法是针对k=1到n逐个计算s(n,k)，然后将数字的所有值相加。

使用钟形三角形是使用钟形三角形，如下所示：

1 1 2 2 3 5 5 7 10 15 15 20 27 37 52

示例

#include<iostream> using namespace std; int bellNumber(int n) { int bell[n+1][n+1]; bell[0][0] = 1; for (int i=1; i<=n; i++) { bell[i][0] = bell[i-1][i-1]; for (int j=1; j<=i; j++) bell[i][j] = bell[i-1][j-1] + bell[i][j-1]; } return bell[n][0]; } int main() { for (int n=0; n<=5; n++) cout<<"Bell Number "<<n<<" is "<< bellNumber(n)<<endl; return 0; }