数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学贝尔数 - 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) 给出了所有从 1 到 n 的 k 值的 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 , 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;
}
更新于：2019年11月22日
680 次浏览
广告