算法设计与分析实验(一)
集合划分问题
实验目的：通过对集合划分问题的算法的设计，进一步熟悉理解并灵活运用递归与
分治策略，掌握该算法思想的核心内容。
实验内容：
1）内容描述：n 个元素的集合{1,2,., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2， 3，4}可以划分为15 个不同的非空子集
2）编程任务：给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。 3）数据输入：
由文件input.txt 提供输入数据。文件的第1 行是元素个数n 和非空
子集数m。 4）结果输出:
程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输
出到文件output.txt 中。
实验原理：假设将m个元素分解到n 个集合中，首先考虑将(m – (n - 1))个元素
分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(n - 1)个集合中，然后再考虑将(m – (n - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(n - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。对于每种分配方法的集合个数的求法，可以先用排列组合的方法计算出元素选取的情况，在通过递归计算出选取该元素后所组成的集合的个数。各种分配情况的遍历可以利用一个for()循环来实现，算法源代码如下：
实验源代码：
#include
//构造计算排列组合的函数
int zuhe(int m, int n, int r) //n为分母，m 为分子 { int p = m, q = n, t = 1, s = 1 ; //用t记录n到(n - m + 1)的乘积, 用 s 记录m到1的乘积 for(int i = 0; i < p; i++) { t *= n ; n-- ; s *= m ; m-- ;
}
if(q == p * 2 && r == 1) return (t / s) / 2 ;
/**当出现在四个元素的集合中选取两个元素作为一个集合时，可能出现的情况是这两个
元素在被计算了两次，故在这里先将其组合数的结果除2*/
1
算法设计与分析实验(一)
}
return t / s ;
//运用递归计算集合的个数
int jihe(int m, int n) //m为元素的个数, n为集合的个数 {
int count = 0 ;
if(m == n || m == 0) return 1; if(n == 1) return 1 ; for(int i = (m - n + 1); i >= (m - i + (n - 2))/(n - 1); i--) { count += zuhe(i, m, n - 1) * jihe(m - i, n - 1) ; } return count ; }
int main() { int m, n ; cout<<\请输入元素的个数和集合的个数: \ cin>>m>>n ; cout< 实验感悟：在这个实验中，运用自顶向下的方法，将第一个集合中的元素的个数从最高依次往下分配，在分配过程中运用递归分治法来计算集合的个数。在这个过程中，关键部分还是循环条件的控制。 2