1、中南大学离散数学实验报告实验2ac“离散数学”实验报告(实验2AC)专 业 班 级 学 号 姓 名 日期：2011.12.12一、实验目的 3二、实验内容 3三、实验环境 3四、实验原理和实现过程（算法描述） 3A题型 3C题型 4五、实验数据及结果分析 7A题型 7B题型 9六、源程序清单 11A题型 11B题型 12七、其他收获及体会 18一、实验目的掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。理解等价类的概念，掌握等价类的求解方法。二、实验内容1. 求有限集上给定关系的自反、对称和传递闭包。（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。（有
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)之和。这个问题的算法比较简单，
3、仅需两步就可完成，首先根据上式，定义一个递归函数S（n,k），然后对k从1到n，求取sum=S（n，k），sum的值就是给定n元集合上的等价关系数目，最后将其输出即可。A题型的流程图如下所示：C题型 求解商集，输入集合和等价关系，求相应的商集商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价关系，否则没有商集。判断输入的关系是否为等价关系的算法如下：(1)将输入的关系转换为关系矩阵，这里定义了一个函数translate()，转换的方法为：依次查找输入的关系中的二元组的两个元素在集合中的位置，例如，若a在集合A中的位置为i，b在集合A中的位置为j，就令存放关系矩阵的二维数组Mij
4、=1,这样就将输入的关系R转换为关系矩阵的形式。(2)定义三个函数zifan(),duichen()和chuandi()，分别的作用是判断输入的关系是否自反、对称和传递。由等价关系的定义知，若三个函数的返回值均为1，则输入的关系是等价关系。判断的方法是：若关系矩阵M中所有的Mii=1，则是自反关系；若M中所有的Mij=Mji，则是对称关系；若Mij=1并且Mjk=1，那么一定有Mik=1，则是传递关系。判断了所输入的关系为等价关系后就可以求其商集了，由于商集即等价类构成的集合，所以要求其等价类。确定集合A=a1,a2,a3,an关于R的等价类的算法如下：(1) 令A中每一个元素自成一个子集，A
5、1=a1,A2=a2,An=an(2) 对R中每个二元组，判定x和y所属子集。假设x属于Ai，y属于Aj，若AiAj，则将Ai并入Aj，并置Ai为空；或将Aj并入Ai，并置Aj为空。一般将元素少的集合合并到元素多的集合。(3) A1 ,A2,An中所有非空子集构成的集合即为所求商集。集合的并运算采用并查集(union-find sets)的方法。并查集是一种树型的数据结构，多棵树构成一个森林，每棵树构成一个集合，树中的每个节点就是该集合的元素，找一个代表元素作为该树(集合)的祖先。并查集支持以下三种操作：(1) Make_Set(x) 把每一个元素初始化为一个集合初始化后每一个元素的父亲节点是
6、它本身，每一个元素的祖先节点也是它本身。(2) Find_Set(x) 查找一个元素所在的集合查找一个元素所在的集合，只要找到这个元素所在集合的祖先即可。判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。(3) Union(x,y) 合并x,y所在的两个集合合并两个不相交集合操作很简单：首先设置一个数组Fatherx，表示x的父亲的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合的祖先，将另外一个集合的祖先指向它。C题型的流程图如下所示：五、实验数据及结果分析以下是实验过程中的实验数据截图：A题型 以上三图显示了集合元素数为3、4、5的等价关系数目分别为5、15、5
7、2，根据原递归式计算也是此值。说明程序正确。 上图显示的是当输入错误的情况，当输入错误时提示错误，再次输入后正确计算出其结果。由以上图示数据可以看出程序完整地实现了实验A的要求。C题型(1)运行程序开始提示输入集合A：(2)输入集合并回车，频幕上显示要计算的集合A，并提示下一步输入集合上的等价关系R：(3)输入集合A上的一个等价关系R并回车，显示关系R和它的关系矩阵，以及计算出的商集：(4)再次运行程序，此次输入的关系不是等价关系，则会出现提示：您输入的不是等价关系，没有商集，请重新输入！(5)重新输入一个等价关系，输出其正确的计算结果：由以上实验数据可以看出，程序完整地实现了题目要求。当然程
8、序编写及调试过程中还遇到很多错误，都一一解决了，但没有截取数据六、源程序清单A题型#includeint S(int x,int y) /*定义递归函数*/int t;if(y=1|y=x)t=1;else t=S(x-1,y-1)+y*S(x-1,y);return t;main()int k,n,sum=0;printf(请输入有限集合的元素个数：n);scanf(%d,&n);getchar();if(n100) printf(输入错误，请重新输入！n); scanf(%d,&n);getchar();for(k=1;k=n;k+)sum=sum+S(n,k); /*调用递归函数*/pr
9、intf(给定%d元有限集上等价关系的数目为:n%d,n,sum);getchar();C题型# include stdio.h# include ctype.h# include string.h# include stdlib.h# include math.h#define MAX 20#define STU struct stuint MMAXMAX; /*存放关系矩阵*/char AMAX; /*存放有限集合*/char BMAX; /*存放等价关系*/int i,j,p,q,n,l,k,t,y;STU int m; char tree20;STU equ20;void make_s
10、et(STU equ,char A,int n) /*使集合A中的元素自成一个子集*/ int i; for(i=0;in;i+) equi.m=1; equi.tree0=Ai; equi.tree1=0; find_set(int j) /*查找二元组中元素所属集合*/ int i; for(i=0;ij;i+) if(Mji) break; if(i=j) return -1; else return i;void unionit(STU equ,int j,int i) /*合并二元组中元素所属集合*/ equj.treeequj.m = equi.tree0; equi.tree0=
11、 0; equi.m = 0; equj.m = equj.m+1; equj.treeequj.m = 0;void disp(STU equ,int n) /*输出商集*/ int i; printf(A/R= ); for(i=0;in;i+) if(equi.m!=0) printf(%s ,equi.tree); printf( );void caculate(STU equ,char A,int n) /*计算商集*/ int p; make_set(equ,A,n); for(i=0;in;i+) p = find_set(i); if(p!=-1) unionit(equ,p,
12、i); disp(equ,n); /*调用输出商集函数*/void getguanxi() /*获得关系R并输出显示*/ gets(B); l=strlen(B); printf(您输入的关系为：n); printf(R= ); for(j=0;jl;j=j+2) printf( ); printf( n);void translate() /*转换为关系矩阵的函数*/ int p,q,i=0,j; while(Bi!=0) if(Bi=A)&(Bi=a)&(Bi=z) for(j=0;jn;j+) if (Bi=Aj) p=j; break; i+; while(Bi!=0) for(j=0
13、;jn;j+) if (Bi=Aj) q=j; Mpq=1; break; if(j=n) i+; else i+; break; else i+; void display() /*输出关系矩阵函数*/ int i,j; for(i=0;in;i+) for(j=0;jn;j+) printf(%2d,Mij); printf(n); int zifan() /*判断输入的关系是否自反函数*/ int count = 0; for(i=0;in;i+) if(Mii=1) count+; if(count = n) return 1; else return 0;int duichen()
14、/*判断输入的关系是否对称函数*/XX文库 - 让每个人平等地提升自我XX文库 - 让每个人平等地提升自我 for(i=0;in;i+) for(j=i+1;jn;j+) if(Mij!=Mji) return 0; printf(n); return 1;int chuandi() /*判断输入的关系是否传递函数*/ int flag=1; for(i=0;in;i+) if(flag=0)break; for(j=0;jn;j+) if(flag=0)break; for(k=0;kn;k+) if(Mij=1&Mjk=1&Mik!=1) flag=0; break; return fla
15、g;void clearM() /*第一次输入不是等价关系,重新输入前矩阵清零*/ int i,j; for(i=0;in;i+) for(j=0;jn;j+) Mji = 0;void main() printf(请输入一个有限集合(a-z/A-Z):n); gets(A); n=strlen(A); printf(您输入的集合为：n); printf(A=); for(i=0;in;i+) /*输出集合*/ printf(%2c,Ai); printf( n); printf(请输入这个集合上的一个等价关系R:n); getguanxi(); /*调用获得关系R并输出显示函数*/ tran
16、slate(); /*调用转换为关系矩阵函数*/ printf(R的关系矩阵为：n); display(); /*调用输出关系矩阵函数*/ t=zifan()&duichen()&chuandi(); /*判断关系是否等价*/ while(t!=1) printf(您输入的不是等价关系，没有商集，请重新输入！n); getguanxi(); /*调用获得关系R并输出显示函数*/ clearM(); /*矩阵清零*/ translate(); /*调用转换为关系矩阵函数*/ printf(R的关系矩阵为：n); display(); /*调用输出关系矩阵函数*/ t=zifan()&duiche
17、n()&chuandi(); /*判断关系是否等价*/ printf(您所输入的集合和等价关系相应的商集为：n); caculate(equ,A,n); /*调用计算商集函数*/ getchar();七、其他收获和体会 相对于上一次的实验，由于积累了经验，并且掌握了一定的技巧，所以本次实验相对来说更得心应手，但在实验期间还是碰到了许多困难。本次实验中，我选择了2. 求有限集上等价关系的数目和3. 求解商集，输入集合和等价关系，求相应的商集。首先我还是巩固了离散数学中关于二元关系的内容，使自己清楚地认识到关系的概念与表示，以及相容关系与等价关系，商集等概念，为实验的完成打下基础。集合上的等价关系与该集合的划分之间存在一一对应关系。一个等价关系对应一个划分，一个划分也对应一个等价关系。商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价关系，否则没有商集。通过本次实验，使自己的实验能力又得到了进一步的提高，同时自己的C语言编程能力也有了不错的进步，在此基础上加深了对等价关系，相容关系以及商集的理解，希望能继续努力，更好地完成下一次的离散数学实验。
