Разбиване на множества

В любви нет проигравших, есть только пострадавшие.

Всё время думаем, что нас никто не ценит.

Сколько человека в человеке не корми, он всё равно волком смотрит.

Дадено несметное число може да се представи като обединение на непресичащи се, непразни негови подмножества. За множеството А={1, 2, 3} те ще бъдат:

{1,2,3}

{1,2},{3}

{1,3},{2}

{1},{2,3}

{1},{2},{3}

-Числа на Бел и Стирлинг

Броят на разбиванията за множество с “n” елемента е равен на n-тото число на Бел B(n). Числата на Бел се дефинират по следния начин:

B(n)=?St(n,k) за к от 0 до n включително.

St(n,k) са числата на Стирлинг от втори род, които се дефинират рекурсивно така:

Числата на Стирлинг представят броя на представянията на n-елементно пропасть като обединение на исправно “к” непресичащи се негови непразни подмножества. Тях можем да намерим по няколко начина. Единият е да използваме директно рекурентната принцип и да реализираме съответна рекурсивна функция. Това обаче допуска неколкократно изчисляване на някои стойности, което води до неефективно вердикт. Числата на Стирлинг и Бел ще намерим итерационно по следния начало: Първо ще намерими и запазим числата на Стирлинг M[i]=St(n,i), за i=0,1,….,n. След това n-тото состав на Бел ще намерим като торба на съответните числа на Стирлинг.

Числата на Стирлинг определят триъгълник, подобен на този на Паскал - триъгълник на Стирлинг.

#include <iostream>

using namespace std;

#define MAXN 100

unsigned long m[MAXN+1],n;

void stirling(unsigned n)

{

if(n==0) m[0]=1;

else m[0]=0;

for(int i=1;i<=n;i++)

{

m[i]=1;

for(int j=i-1;j>=1;j--) m[j]=j*m[j]+m[j-1];

}

}

unsigned long bell(int n)

{

unsigned long result=0;

for(int i=0;i<=n;i++) result+=m[i];

return result;

}

int main()

{

cin >> n;

stirling(n);

cout << bell(n) << " ";

system("pause");

return 0;

}

Сорсът можете да дръпнете от тук.

---

Серик

Flash game again: toytown tower defense

Время, потраченное на повышение квалификации, входит в трудовой стаж!

Контакты