关于切蛋糕与集合

集合的划分

  【问题描述】

  设S是一个具有n个元素的集合,S={a1,a2,……,an},现将S划分成k个满足下列条件的子集合S1,S2,……,Sk ,且满足:

    1.Sn≠∅;

    2.Si∩Sj=∅;

    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)。

  代码如下:

#include<stdio.h>
int div(int n,int k);
int main()
{
	int n,k;
	int ans;
	scanf("%d%d",&n,&k);
	while(n!=0&&k!=0)
	{
		ans=div(n,k);
		printf("%d",ans);
		scanf("%d%d",&n,&k);
	}
	return 0;
}
int div(int n,int k)
{
	int ans;
	/*if(k>n)
		return -1;*/
	if(n==k||k==1)
		ans=1;
	else
		ans=div(n-1,k-1)+k*div(n-1,k);
	return ans;
}

  

原文地址:https://www.cnblogs.com/LegendLa/p/4479801.html