轉載請注明出處
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;
}
~~~
