中南大学离散数学实验报告(实验2AC)

离散数学实验报告2AC1“离散数学”实验报告(实验2AC)专业班级学号姓名日期：2011.12.12离散数学实验报告2AC2目录一、实验目的...................................................................................................3二、实验内容...................................................................................................3三、实验环境...................................................................................................3四、实验原理和实现过程（算法描述）...................................................3A题型.................................................................................................................3C题型................................................................................................................4五、实验数据及结果分析.............................................................................7A题型.................................................................................................................7B题型................................................................................................................9六、源程序清单............................................................................................11A题型...............................................................................................................11B题型..............................................................................................................12七、其他收获及体会....................................................................................18离散数学实验报告2AC3一、实验目的掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。理解等价类的概念，掌握等价类的求解方法。二、实验内容1.求有限集上给定关系的自反、对称和传递闭包。（有两种求解方法，只做一种为A，两种都做为B）2.求有限集上等价关系的数目。（有两种求解方法，只做一种为A，两种都做为B）3.求解商集，输入集合和等价关系，求相应的商集。（C）三、实验环境C或C＋＋语言编程环境实现。四、实验原理和实现过程（算法描述）A题型求有限集上等价关系的数目。集合上的等价关系与该集合的划分之间存在一一对应关系。一个等价关系对应一个划分，一个划分也对应一个等价关系。我们把n个元素的集合划分成k块的方法数叫第二类Stirling数，表示为S(n,k)。给定S(n,n)=S(n,1)=1，有递归关系：S(n,k)=S(n−1,k−1)+kS(n−1,k)集合上所有等价类的个数即为k从1到n，所有S(n,k)之和。这个问题的算法比较简单，仅需两步就可完成，首先根据上式，定义一个递归函数S（n,k），然后对k从1到n，求取sum=∑S（n，k），sum的值就是给定n元集合上的等价关系数目，最后将其输出即可。A题型的流程图如下所示：离散数学实验报告2AC4C题型求解商集，输入集合和等价关系，求相应的商集商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价关系，否则没有商集。判断输入的关系是否为等价关系的算法如下：开始输入要计算的集合的元素数nSum=0k=1（）kn？S（n，k）=1Sum=Sum+S（n，k）k++S(n,k)=S(n-1,k-1)+k*S(n-1,k)S（n，k）=1Sum=Sum+S（n，k）输出Sum结束YN离散数学实验报告2AC5(1)将输入的关系转换为关系矩阵，这里定义了一个函数translate()，转换的方法为：依次查找输入的关系中的二元组的两个元素在集合中的位置，例如a，b，若a在集合A中的位置为i，b在集合A中的位置为j，就令存放关系矩阵的二维数组M[i][j]=1,这样就将输入的关系R转换为关系矩阵的形式。(2)定义三个函数zifan(),duichen()和chuandi()，分别的作用是判断输入的关系是否自反、对称和传递。由等价关系的定义知，若三个函数的返回值均为1，则输入的关系是等价关系。判断的方法是：若关系矩阵M中所有的M[i][i]=1，则是自反关系；若M中所有的M[i][j]=M[j][i]，则是对称关系；若M[i][j]=1并且M[j][k]=1，那么一定有M[i][k]=1，则是传递关系。判断了所输入的关系为等价关系后就可以求其商集了，由于商集即等价类构成的集合，所以要求其等价类。确定集合A={a1,a2,a3,…,an}关于R的等价类的算法如下：(1)令A中每一个元素自成一个子集，A1={a1},A2={a2},…,An={an}(2)对R中每个二元组x,y，判定x和y所属子集。假设x属于Ai，y属于Aj，若AiAj，则将Ai并入Aj，并置Ai为空；或将Aj并入Ai，并置Aj为空。一般将元素少的集合合并到元素多的集合。(3)A1,A2,…,An中所有非空子集构成的集合即为所求商集。集合的并运算采用并查集(union-findsets)的方法。并查集是一种树型的数据结构，多棵树构成一个森林，每棵树构成一个集合，树中的每个节点就是该集合的元素，找一个代表元素作为该树(集合)的祖先。并查集支持以下三种操作：(1)Make_Set(x)把每一个元素初始化为一个集合初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本离散数学实验报告2AC6身。(2)Find_Set(x)查找一个元素所在的集合查找一个元素所在的集合，只要找到这个元素所在集合的祖先即可。判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。(3)Union(x,y)合并x,y所在的两个集合合并两个不相交集合操作很简单：首先设置一个数组Father[x]，表示x的父亲的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合的祖先，将另外一个集合的祖先指向它。C题型的流程图如下所示：开始输入集合A输入A上的关系R转换为关系矩阵M是否为等价关系？求解商集A/R输出商集结束是否离散数学实验报告2AC7五、实验数据及结果分析以下是实验过程中的实验数据截图：A题型离散数学实验报告2AC8以上三图显示了集合元素数为3、4、5的等价关系数目分别为5、15、52，根据原递归式计算也是此值。说明程序正确。离散数学实验报告2AC9上图显示的是当输入错误的情况，当输入错误时提示错误，再次输入后正确计算出其结果。由以上图示数据可以看出程序完整地实现了实验A的要求。C题型(1)运行程序开始提示输入集合A：(2)输入集合并回车，频幕上显示要计算的集合A，并提示下一步输入集合上的等价关系R：离散数学实验报告2AC10(3)输入集合A上的一个等价关系R并回车，显示关系R和它的关系矩阵，以及计算出的商集：(4)再次运行程序，此次输入的关系不是等价关系，则会出现提示：您输入的不是等价关系，没有商集，请重新输入！离散数学实验报告2AC11(5)重新输入一个等价关系，输出其正确的计算结果：由以上实验数据可以看出，程序完整地实现了题目要求。当然程序编写及调试过程中还遇到很多错误，都一一解决了，但没有截取数据六、源程序清单A题型#includestdio.hintS(intx,inty)/*定义递归函数*/{intt;if(y==1||y==x){t=1;}else{t=S(x-1,y-1)+y*S(x-1,y);}returnt;}main(){intk,n,sum=0;printf(请输入有限集合的元素个数：\n);离散数学实验报告2AC12scanf(%d,&n);getchar();if(n=0||n100){printf(输入错误，请重新输入！\n);scanf(%d,&n);getchar();}for(k=1;k=n;k++){sum=sum+S(n,k);/*调用递归函数*/}printf(给定%d元有限集上等价关系的数目为:\n%d,n,sum);getchar();}C题型#includestdio.h#includectype.h#includestring.h#includestdlib.h#includemath.h#defineMAX20#defineSTUstructstuintM[MAX][MAX];/*存放关系矩阵*/charA[MAX];/*存放有限集合*/charB[MAX];/*存放等价关系*/inti,j,p,q,n,l,k,t,y;STU{intm;chartree[20];};STUequ[20];voidmake_set(STUequ[],charA[],intn)/*使集合A中的元素自成一个子集*/{inti;for(i=0;in;i++){equ[i].m=1;equ[i].tree[0]=A[i];离散数学实验报告2AC13equ[i].tree[1]='\0';}}find_set(intj)/*查找二元组中元素所属集合*/{inti;for(i=0;ij;i++){if(M[j][i]){break;}}if(i==j){return-1;}elsereturni;}voidunionit(STUequ[],intj,inti)/*合并二元组中元素所属集合*/{equ[j].tree[equ[j].m]=equ[i].tree[0];equ[i].tree[0]='\0';equ[i].m=0;equ[j].m=equ[j].m+1;equ[j].tree[equ[j].m]='\0';}voiddisp(STUequ[],intn)/*输出商集*/{inti;printf(A/R={);for(i=0;in;i++){if(equ[i].m!=0){printf({%s},equ[i].tree);}}printf(});}离散数学实验报告2AC14voidcaculate(STUequ[],charA[],intn)/*计算商集*/{intp;make_set(equ,A,n);for(i=0;in;i++){p=find_set(i);if(p!=-1){unionit(equ,p,i);}}disp(equ,n);/*调用输出商集函数*/}voidgetguanxi()/*获得关系R并输出显示