集合划分问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,集合划分问题,题目,分析,当n为大于等于0的整数时，n个元素的集合1,2,.,n可以划分若干个非空子集的个数称为贝尔数。,即该问题是bell数的求解。,B(n)是包含n个元素的集合的划分方法的数目。,B(0)=1,B(1)=1,B(2)=2,B(3)=5,B(4)=15,B(5)=52,B(6)=203,.,递推公式为，,B(0)=1,B(n+1)=Sum(0,n)C(n,k)B(k).n=1,2,.,其中，Sum(0,n)表示对k从0到n求和，C(n,k)=n!/k!(n-k)!,代码,该函数是用来计算组合函数的即 n!/(m!*(n-m)!),unsigned _int64 c(int n,int m),if(mn/2)m=n-m;,int i;,unsigned _int64 a=1,b=1;,标题六,for(i=n;in-m;i-),a*=i;,for(i=2;i=m;i+),b*=i;,return a/b;,计算,Sum(0,n)C(n,m,)B(,m,),unsigned _int64 bell(int n),unsigned _int64 t=0;,int i;,if(n=0)return 1;,else,for(i=0;i=n-1;i+),t+=c(n-1,i)*bell(i);,return t;,int main(),int n;,while(scanf(%d,&n)!=EOF),printf(%I64u/n,bell(n);,return 0;,谢谢！,