转载请注明出处
http://blog.csdn.net/pony_maggie/article/details/37729745
作者:小马
思考下面一个问题,
给定正整数n和m，计算出n个元素的集合可以划分为多少个不同的由m(m<=n)个不同的非空子集组成的集合。
这类题可以叫做集合划分问题。面试题里经常出现。先来考虑一个问题，这个算法有实际的应用吗？可能用在类似资源分配的例子上，比如有n个资源，m个工程，把这些资源分给不同的工程，需要求出不同的分法，然后计算不同的分法将获得的利润(这个例子似乎有点牵强，谁有更好的请给我留言，谢谢)。
解题的思路，一种是分治的思想。把n个元素编号，对於最后那个n号元素，有两种情况:
一种是独立组成一个集合，另一种是和别的元素混在一起。
对於第一种情况，等价于把前n-1个元素分成m-1份，然后n号元素单独放。
对於第二种情况，等价于把前n-1个元素分成m份，然后把n号元素放入这m个集合中的一个（有m种放法）
总数就是
F(n,m) =F(n-1,m-1) + m * F(n-1,m)
先想几种极端的情况，
m=n的情况，结果很明显是1。
m=1的情况，结果也是1。
n=1的情况，m只能等于1, 结果也是1。
有了上面的思想，基本上基于递归的代码就可以出来了，如下:
~~~
//基于分治的思想，递归实现
int calculateSet(int n ,int m)
{
if ((m > n) ||(m == 0))
{
return 0;
}
else if ((m == 1)||(n==1)||(m == n))
{
return 1;
}
else
{
return (calculateSet(n-1, m-1) + m*calculateSet(n-1, m));
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int n1 = 4;
int m1= 2;
printf("%d\n", calculateSet(n1,m1));
return 0;
}
~~~
