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