集合的划分(递归)

题目描述
设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集合中的n个元素a1,a2,…,an放入k个（0 < k≤n < 30）无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1,a2,…,an放入k个无标号盒子中去的划分数s(n,k)。

输入
输入为一行：n k

输出
输出为一个整数

样例输入
4 3
样例输出
6

基本思路:

对于把n个元素放入k个集合

@1:如果a(n)是一个独立集合,那么

s(n,k)=s(n-1,k-1)

也就是和n-1元素放入k-1集合的划分数一样

 

@2:如果a(n)是附加进入其他集合,那么

s(n,k)=k*s(n-1,k)

在n-1元素放入k个集合的基础上,a(n)有k种选择,所以是k*s(n-1,k)

@3.最后注意一下当s(n,k)等于0或1的边界条件就好了

 

代码:

#include<bits/stdc++.h>
using namespace std;
int n,k;

int jihe(int n,int k)
{
    if(k==0||n<k)
    {
        return 0;
    }
    if(k==n||k==1)
    {
        return 1;
    }
    return jihe(n-1,k-1)+k*jihe(n-1,k);
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>k;
    printf("%d",jihe(n,k));
}