集合划分

我就是我 2022-08-02 12:39 47阅读 0赞

问题描述：给定含有n个元素的集合\{1,2,...,n\}，可以将其划分为若干非空子集。例如，当n=4时，集合\{1,2,3,4\}可以构造15个不同的划分，如下。

\{ \{1\}，\{2\}，\{3\}，\{4\}\}

\{ \{1234\}\}

\{ \{1\}，\{234\}\}；\{ \{2\}，\{134\}\}；\{ \{3\}，\{124\}\}；\{ \{4\}，\{123\}\}

\{ \{12\}，\{34\}\}；\{ \{13\}，\{24\}\}；\{ \{14\}，\{23\}\}

\{ \{1\}，\{2\}，\{34\}\}；\{ \{1\}，\{3\}，\{24\}\}；\{ \{1\}，\{4\}，\{23\}\}

\{ \{12\}，\{3\}，\{4\}\}；\{ \{13\}，\{2\}，\{4\}\}；\{ \{14\}，\{2\}，\{3\}\}

编程任务：给定正整数n，试计算含有n个元素\{1,2,3,...,n\}可以划分为多少个不同的非空子集。

思路：对于n个元素的集合，可以划分成由m(1<=m<=n)个子集构成的子集，如\{ \{1\}，\{2\}，\{3\}，\{4\}\}就是由4个子集构成的非空子集。假设f(n,m)表示将n个元素的集合划分成由m个子集构成的集合的个数，那么可以这样来看：

1)若m==1，则f(n,m)=1;

2)若n==m，则f(n,m)=1;

3)若非以上两种情况，f(n,m)可以由下面两种情况构成

a.向n-1个元素划分成的m个集合里面添加一个新的元素，则有m\*f(n-1,m)种方法；

b.向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。

因此：

当m==1||n==m时   f(n,m)=1

当m<n&&m!=1时 f(n,m)=f(n-1,m-1)+m\*f(n-1,m)

参考代码：

#include<stdio.h>
    	int f(int n,int i)
    	{
    		if(i==1||n==i)
    			return 1;
    		else
    			return f(n-1,i-1)+f(n-1,i)*i;
    	}
    	int main()
    	{
    		int i,j;
    		int n,sum=0;
    		scanf("%d",&n);
    	
    		for(i=1;i<=n;i++)
    			sum+=f(n,i);
    	
    		printf("%d\n",sum);
    		return 0;
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关第十二章贪心 5 AcWing 1603. 整数集合划分

第十二章贪心 5 AcWing 1603. 整数集合划分原题链接 [AcWing 1603. 整数集合划分][AcWing 1603.] 算法标签贪心

╰+哭是因爲堅強的太久メ/ 2024年03月31日 13:51/ 0 赞/ 37 阅读

相关算法--集合划分问题

问题描述： n个元素的集合\{1,2,.,n \}可以划分为若干个非空子集。例如，当n=4 时，集合\{1,2,3,4\}可以划分为15个不同的非空子集如下： \{1\

╰+攻爆jí腚メ/ 2022年11月21日 04:26/ 0 赞/ 184 阅读

相关划分

接触快速排序之前首先需要了解划分。划分就是将数据划分为两组，比关键字大的划分在一组，比关键字小的划分在另外一组。划分算法可以理解是两个指针操作的进程。开始时指针分别指

布满荆棘的人生/ 2022年09月26日 01:59/ 0 赞/ 157 阅读

相关区间dp（整数划分，石子划分）

整数划分（四）链接： [http://acm.nyist.net/JudgeOnline/problem.php?pid=746][http_acm.nyist.net

ゞ浴缸里的玫瑰/ 2022年09月18日 13:56/ 0 赞/ 162 阅读

相关集合划分问题（贝尔数）

集合划分问题 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submi

傷城~/ 2022年08月21日 11:56/ 0 赞/ 110 阅读

相关集合划分

问题描述：给定含有n个元素的集合\{1,2,...,n\}，可以将其划分为若干非空子集。例如，当n=4时，集合\{1,2,3,4\}可以构造15个不同的划分，如下。

我就是我/ 2022年08月02日 12:39/ 0 赞/ 48 阅读

相关水平划分和垂直划分

[数据库][Link 1]的水平划分和垂直划分很早以前就接触了，只是没有实践，没有什么体会，只有最近两年才有接触，今天也和大家聊聊。垂直划分按照功

末蓝、/ 2022年07月12日 02:17/ 0 赞/ 184 阅读

相关 [分治]-集合划分问题 [分治]-逆序对问题

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

男娘i/ 2022年06月16日 03:07/ 0 赞/ 210 阅读

相关子集和问题：按给定子集和完全划分集合

需求是这样的：有44个数字A1-A44：1420, 1198, 493, 300, 3006, 881, 2450, 1372, 3643, 1350, 598, 615

柔情只为你懂/ 2022年02月04日 16:09/ 0 赞/ 234 阅读

相关划分vlan

VLAN的定义： VLAN是英文Virtual Local Area Network的简称，又叫虚拟局域网，是一种通过将局域网内的设备逻辑地而不是物理地划分成一个个网段从而

深碍√TFBOYSˉ_/ 2022年01月13日 01:37/ 0 赞/ 304 阅读