集合划分问题(2)

集合划分问题(2)

时间: 1ms        内存:64M

描述:

n个元素的集合{1,2,……, n }可以划分为若干个非空子集。例如,当n=4 时,集合{1,2,3,4}可以划分为15 个不同的非空子集如下:

{{1},{2},{3},{4}},

{{1,2},{3},{4}},

{{1,3},{2},{4}},

{{1,4},{2},{3}},

{{2,3},{1},{4}},

{{2,4},{1},{3}},

{{3,4},{1},{2}},

{{1,2},{3,4}},

{{1,3},{2,4}},

{{1,4},{2,3}},

{{1,2,3},{4}},

{{1,2,4},{3}},

{{1,3,4},{2}},

{{2,3,4},{1}},

{{1,2,3,4}}

其中,集合{{1,2,3,4}}由1个子集组成;集合{{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}}, {{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}},{{2,3,4},{1}}由2 个子集组成;集合{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4},{2},{3}},{{2,3},{1},{4}}, {{2,4},{1},{3}},{{3,4},{1},{2}}由3个子集组成;集合{{1},{2},{3},{4}}由4个子集组成。

给定正整数n和m,计算出n个元素的集合{1,2,……, n }可以划分为多少个不同的由m个非空子集组成的集合。

输入:

输入数据只有1行有两个整数,分别表示元素个数n和非空子集数 m(n≤100,m≤100)。

输出:

输出数据只有一个整数,表示计算出的不同的由m个非空子集组成的集合数。

示例输入:

4 3

示例输出:

6

提示:

参考答案(内存最优[748]):

#include"stdio.h"
int c(int n,int m)
{
	if(m==1||m==n)
		return 1;
	else
		return c(n-1,m-1)+m*c(n-1,m);
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	printf("%d\n",c(n,m));
	return 0;
}

参考答案(时间最优[0]):

#include"stdio.h"
int c(int n,int m)
{
    if(m==1||m==n)
        return 1;
    else
        return c(n-1,m-1)+m*c(n-1,m);
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%d\n",c(n,m));
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注