資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告