集合划分

我就是我 2022-08-02 12:39 90阅读 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 条评论，90人围观）

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

相关阅读

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

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

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

相关 1296. 划分数组为连续数字的集合

给你一个整数数组 `nums` 和一个正整数 `k`，请你判断是否可以把这个数组划分成一些由 `k` 个连续数字组成的集合。如果可以，请返回 `True`；否则，返回 `

╰半橙微兮°/ 2023年10月04日 10:27/ 0 赞/ 9 阅读

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

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

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

相关划分

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

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

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

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

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

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

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

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

相关集合划分

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

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

相关水平划分和垂直划分

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

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

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

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

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

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

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

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