Một số chuông được sử dụng để biểu thị số cách một tập hợp n phần tử có thể được phân chia thành các tập hợp con không trống (nghĩa là có ít nhất một phần tử).
Trong chương trình này, chúng ta được cung cấp một tập hợp n phần tử và chúng ta phải tìm số cách để phân chia tập hợp đó thành các tập hợp con không rỗng.
Ví dụ
Input : 3 Output : 5
Giải thích - cho tập hợp ba phần tử {1, 2, 3}.
Các tập con là {{1}, {2}, {3}}; {{1}, {2,3}}; {{1, 2}, {3}}; {{2}, {1, 3}}; {1, 2, 3}.
Số chuông:Một số chuông (n) cho giá trị tổng của s (n, k) với mọi giá trị của k trong khoảng từ 1 đến n. Ở đây s (n, k) là số phân hoạch của n phần tử thành k tập con.
Công thức sẽ là -
$$ bell (n) =\ sum_ {k =0} ^ n S (n, k) $$
Hàm s (n, k) được đệ quy là -
s (n + 1, k) =k * s (n, k) + s (n, k-1).
Đang làm việc
Khi thêm phần tử thứ (n + 1) vào k phân vùng, có hai khả năng -
-
Nó thêm một vào k phân vùng của các phân vùng hiện có, tức là s (n, k-1).
-
Thêm giá trị vào tất cả các nhóm phân vùng, tức là k * s (n, k).
Một số chuông đầu tiên là 1, 1, 2, 5, 15, 52, 205
Để tìm số Bells, chúng tôi có một số phương pháp,
-
Phương pháp đơn giản là lần lượt tính s (n, k) cho k =1 đến n và cộng tổng tất cả các giá trị của số.
-
Sử dụng tam giác chuông là sử dụng hình tam giác của chuông như được đưa ra bên dưới -
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52
Ví dụ
#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;
}