题目描述

设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
     
      using namespace std;int n,k;int jihe(int n,int k){    if(k==0||n
      
       >n>>k;    printf("%d",jihe(n,k));}