1315：【例4.5】集合的劃分

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 11952 ??? 通過數: 5318

【題目描述】

設S是一個具有n個元素的集合，S＝?a1，a2，……，an?，現將S劃分成 k 個滿足下列條件的子集合S1，S2，……，Sk，且滿足：

1．Si≠?

2．Si∩Sj＝?? ? ? ? ? ? ( 1≤i，j≤k，i≠j )

3．S1∪S2∪S3∪…∪Sk＝S

則稱S1，S2，……，Sk是集合S的一個劃分。它相當于把S集合中的n個元素a1，a2，……，an放入k個(0＜k≤n＜30)無標號的盒子中，使得沒有一個盒子為空。請你確定n個元素a1，a2，……，an?放入k個無標號盒子中去的劃分數S(n,k)。

【輸入】

給出n和k。

【輸出】

n個元素a1，a2，……，an 放入k個無標號盒子中去的劃分數S(n,k)。

【輸入樣例】

10 6

【輸出樣例】

22827

【分析】

? ? ? ? 先舉個例子，設 S={1，2，3，4}，k=3，不難得出 S有6種不同的劃分方案，即劃分數 S（4，3）=6，具體方案為∶

? ? ? ? {1,2}U{3}U{4}? ? ? ? ? ? ? ? {1,3}U{2}U{4}? ? ? ? ? ? ?{1,4}U{2}U{3}

? ? ? ? {2,3}U{1}U{4)? ? ? ? ? ? ? ? {2,4}U{1>U{3)? ? ? ? ? ? {3,4}U{1}U{2}

? ? ? ? 考慮一般情況，對于任意的含有n個元素 al ，a2，…，an 的集合 S，放入k個無標號的盒子中去，劃分數為 S（n，k），我們很難憑直覺和經驗計算劃分數和枚舉劃分的所有方案，必須歸納出問題的本質。其實對于任一個元素 an，則必然出現以下兩種情況：

? ? ? ? 1. {an} 是k 個子集中的一個，于是我們只要把 al，a2，…，an-1 劃分為 k-1子集，便解決了本題，這種情況下的劃分數共有 S（n-1，k-1）個;

? ? ? ? 2. {an} 不是k 個子集中的一個，則 an 必與其他的元素構成一個子集。則問題相當于先把 al，a2，…，an-1劃分成 k 個子集，這種情況下劃分數共有 S（n-1，k）個；然后再把元素 an 加入到 k 個子集中的任一個中去，共有 k 種加入方式，這樣對于 an 的每一種加入方式，都可以使集合劃分為 k 個子集，因此根據乘法原理，劃分數共有k * S（n-1，k）個。

? ? ? ? 綜合上述兩種情況，應用加法原理，得出 n個元素的集合 {al，a2，…，an} 劃分為 k 個子集的劃分數為以下遞歸公式∶S（n，k）=S（n-1，k-1）＋k * S（n-1，k）（n>k，k>0）。

? ? ? ? 下面，我們來確定 S（n，k）的邊界條件，首先不能把 n 個元素不放進任何一個集合中去，即k=0 時，S（n，k）=0；也不可能在不允許空盒的情況下把n個元素放進多于n的 k 個集合中去，即k>n時，S（n，k）=0；再者，把 n個元素放進一個集合或把n個元素放進 n個集合，方案數顯然都是1，即 k=1或 k=n 時，S（n，k）=1。

? ? ? ? 因此，我們可以得出劃分數 S（n，k）的遞歸關系式為∶

? ? ? ? S(n,k)=S(n-1,k-1)+k * S(n-1,k)? ? ? ? (n>k,k>0)

? ? ? ? S(n,k)=0? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（n<k）或（k=0）

? ? ? ? S(n,k)=1? ? ? ? ? ? ? ? ? ? ? ? ? ? （k=1）或（k= n）

【參考代碼】

#include<stdio.h> long long s(int n,int k) {if(n<k || k==0)return 0;if(k==1 || k==n)return 1;elsereturn s(n-1,k-1)+k*s(n-1,k); } int main() {int k,n;scanf("%d%d",&n,&k);printf("%lld\n",s(n,k));return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1315

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1315：【例4.5】集合的划分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。