벨 번호 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).
작업
k개의 파티션에 (n+1)번째 요소를 추가할 때 두 가지 가능성이 있습니다 -
-
기존 파티션, 즉 s(n,k-1)의 k 파티션에 1을 추가합니다.
-
모든 파티션 세트에 값 추가, 즉 k*s(n,k).
처음 몇 개의 벨 번호는 1 , 1 , 2 ,5 ,15 , 52 , 205입니다.
Bells 번호를 찾는 데는 몇 가지 방법이 있습니다.
-
간단한 방법 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;
}