OpenJudge

09:集合的划分

总时间限制:
1000ms
内存限制:
65536kB
描述
把一个集A(本题中的集合均不含重复元素)分成若干个非空子集,使得A中每个元素属于且仅属于一个子集,那么这些子集构成的集合称为A的一个划分。比如A={1,2,3},那么{ {1},{2 ,3} }以及{ {1},{2},{3} } 都是A的划分。现在给定一个整数n,我们希望知道包含n个元素的集合有多少不同的划分。当n=3的时候,仍然考虑集合{1,2,3},它的所有划分如下
{ {1} , {2} , {3} }
{ {1 , 2} , {3} }
{ {1 , 3} , {2} }
{ {1} , {2 , 3} }
{ {1 , 2 , 3} }
只有5种,但随n的增加,划分方法的个数会以指数速度增加。比如n=4的时候,就有15种方法,考虑集合{1,2,3,4},划分方式如下
{ {1},{2},{3},{4}}
{{1},{2},{3,4}}
{{1,2},{3},{4}}
{{1,3},{2},{4}}
{{1,4},{2},{3}}
{{1},{2,3},{4}}
{{1},{3},{2,4}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}
{{1},{2,3,4}}
{{2},{1,3,4}}
{{3},{1,2,4}}
{{4},{1,2,3}}
{{1,2,3,4}}
当n>15的时候,划分方法数将超过32位整数所能表示的范围,我们希望你的程序能计算出n<=15的时候,包含n个元素的集合的划分方法的个数
输入
一个整数n(0<=n<=15,n=0的时候认为有一种划分方法)
输出
包含n个不同元素的集合的划分方法的个数
样例输入
3
15
样例输出
5
1382958545
提示
递归公式,
设n个元素的集合可以划分为F(n,m)个不同的由m个非空子集组成的集合。
F(n,m) = 1, where n=0, n=m, n=1, or m=1
F(n,m) = 0, where n<m
否则
F(n,m)=F(n-1,m-1)+m*F(n-1,m)

例如:
考虑3个元素的集合,可划分为
① 1个子集的集合:{{1,2,3}}
② 2个子集的集合:{{1,2},{3}},{{1,3},{2}},{{2,3},{1}}
③ 3个子集的集合:{{1},{2},{3}}
∴F(3,1)=1;F(3,2)=3;F(3,3)=1;

如果要求F(4,2)该怎么办呢?

A.往①里添一个元素{4},得到{{1,2,3},{4}}

B.往②里的任意一个子集添一个4,得到
{{1,2,4},{3}},{{1,2},{3,4}},
{{1,3,4},{2}},{{1,3},{2,4}},
{{2,3,4},{1}},{{2,3},{1,4}}

∴F(4,2)=F(3,1)+2*F(3,2)=1+2*3=7
来源
cs10107 C++ Final Exam
全局题号
2254
添加于
2016-11-26
提交次数
101
尝试人数
28
通过人数
18