算法--集合划分问题

╰+攻爆jí腚メ 2022-11-21 04:26 220阅读 0赞

**问题描述：**  
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 个  
非空子集组成的集合。  
**数据输入：**  
由文件input.txt 提供输入数据。文件的第1 行是元素个数n 和非空子集数m。  
**结果输出:**  
程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt中。  
**输入：**  
4 3  
**输出：**  
6

代码：

#include<stdio.h>
    
    int Divide(int m,int n) { 
    	if (n == 1 || m == n) { 
    		return 1;
    	}
    	else{ 
    		return Divide(m - 1,n - 1) + n*Divide(m - 1,n);
    	}
    }
    
    /* 输入m和n，m表示元素的个数，n表示划分后子集的个数 1 1 = 1 2 1 = 1 ，2 2 = 1 3 1 = 1 ，3 2 = 2 1 + 2*2 2 ，3 3 = 1 4 1 = 1 ，4 2 = 3 1 + 2*3 2 ，4 3 = 3 2 + 3*3 3 ，4 4 = 1 5 1 = 1 ，5 2 = 4 1 + 2*4 2 ，5 3 = 4 2 + 3*4 3 ，5 4 = 4 3 + 4*4 4 ，5 5 = 1 m n = m-1 n-1 + n*m-1 n */
    
    
    int main(){ 
    	int m,n;
    	scanf("%d %d", &m, &n);
    	printf("%d",Divide(m,n));
    	return 0;
    }