贝尔编号-用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} ^ n S(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;
}