กริ่ง ใช้เพื่อระบุจำนวนวิธีที่ชุดขององค์ประกอบ 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) ให้ค่าของผลรวมของ s(n,k) สำหรับค่าทั้งหมดของ k ตั้งแต่ 1 ถึง n โดยที่ 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)th ให้กับพาร์ติชั่น k มีความเป็นไปได้สองอย่าง -
-
มันเพิ่มหนึ่งพาร์ติชั่น k ของพาร์ติชั่นที่มีอยู่เช่น s(n,k-1)
-
การเพิ่มมูลค่าให้กับชุดพาร์ติชั่นทั้งหมด เช่น k*s(n,k)
ตัวเลขเบลล์สองสามตัวแรกคือ 1 , 1 , 2 ,5 ,15 , 52 , 205
ในการค้นหาหมายเลข Bells เรามีวิธีการสองสามวิธี
-
วิธีง่ายๆ คือการคำนวณ s(n,k) ทีละตัวสำหรับ k =1 ถึง n และเพิ่มผลรวมของค่าทั้งหมดของตัวเลข
-
การใช้รูปสามเหลี่ยมระฆัง คือการใช้รูปสามเหลี่ยมของกระดิ่งตามด้านล่าง −
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;
} 