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

1、精选优质文档-倾情为你奉上“离散数学”实验报告(实验2AC)专 业 班 级 学 号 姓 名 日期：2011.12.12目录一、实验目的3二、实验内容3三、实验环境3四、实验原理和实现过程（算法描述）3A题型3C题型4五、实验数据及结果分析7A题型7B题型9六、源程序清单11A题型11B题型12七、其他收获及体会18一、实验目的掌握关系的概念与性质，基本的关系运算，关系的各种闭包的求法。理解等价类的概念，掌握等价类的求解方法。二、实验内容1. 求有限集上给定关系的自反、对称和传递闭包。（有两种求解方法，只做一种为A，两种都做为B）2. 求有限集上等价关系的数目。（有两种求解方法，只做一种为A，两

2、种都做为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题型的流程图如下所示：开 始输入要计算的集合的元素数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结束YNC题型 求解商集，输入集合和等价关系，求相应的商集商集即等价类构成的集合，要求商集，首先需要判断输入的关系是否为等价关系，否则没有商集。判断输入的关系是否为等价关系的算法如下：(1)将输入的关系转换为关系矩阵，这里定义

4、了一个函数translate()，转换的方法为：依次查找输入的关系中的二元组的两个元素在集合中的位置，例如，若a在集合A中的位置为i，b在集合A中的位置为j，就令存放关系矩阵的二维数组Mij=1,这样就将输入的关系R转换为关系矩阵的形式。(2)定义三个函数zifan(),duichen()和chuandi()，分别的作用是判断输入的关系是否自反、对称和传递。由等价关系的定义知，若三个函数的返回值均为1，则输入的关系是等价关系。判断的方法是：若关系矩阵M中所有的Mii=1，则是自反关系；若M中所有的Mij=Mji，则是对称关系；若Mij=1并且Mjk=1，那么一定有Mik=1，则是传递关系。判断

5、了所输入的关系为等价关系后就可以求其商集了，由于商集即等价类构成的集合，所以要求其等价类。确定集合A=a1,a2,a3,an关于R的等价类的算法如下：(1) 令A中每一个元素自成一个子集，A1=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)的方法。并查集是一种树型的数据结构，多棵树构成一个森林，每棵树构成一个

6、集合，树中的每个节点就是该集合的元素，找一个代表元素作为该树(集合)的祖先。并查集支持以下三种操作：(1) Make_Set(x) 把每一个元素初始化为一个集合初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身。(2) Find_Set(x) 查找一个元素所在的集合查找一个元素所在的集合，只要找到这个元素所在集合的祖先即可。判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。(3) Union(x,y) 合并x,y所在的两个集合合并两个不相交集合操作很简单：首先设置一个数组Fatherx，表示x的父亲的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合

7、的祖先，将另外一个集合的祖先指向它。C题型的流程图如下所示：开 始输入集合A输入A上的关系R转换为关系矩阵M是否为等价关系？求解商集A/R输出商集结 束是否五、实验数据及结果分析以下是实验过程中的实验数据截图：A题型 以上三图显示了集合元素数为3、4、5的等价关系数目分别为5、15、52，根据原递归式计算也是此值。说明程序正确。 上图显示的是当输入错误的情况，当输入错误时提示错误，再次输入后正确计算出其结果。由以上图示数据可以看出程序完整地实现了实验A的要求。C题型(1)运行程序开始提示输入集合A：(2)输入集合并回车，频幕上显示要计算的集合A，并提示下一步输入集合上的等价关系R：(3)输入集

8、合A上的一个等价关系R并回车，显示关系R和它的关系矩阵，以及计算出的商集：(4)再次运行程序，此次输入的关系不是等价关系，则会出现提示：您输入的不是等价关系，没有商集，请重新输入！(5)重新输入一个等价关系，输出其正确的计算结果：由以上实验数据可以看出，程序完整地实现了题目要求。当然程序编写及调试过程中还遇到很多错误，都一一解决了，但没有截取数据六、源程序清单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;

9、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); /*调用递归函数*/printf(给定%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

10、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_set(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+)

11、 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= 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);p

12、rintf( );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,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

13、() /*转换为关系矩阵的函数*/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;jn;j+) if (Bi=Aj) q=j; Mpq=1; break; if(j=n) i+; else i+; break; elsei+;void display() /*输出关系矩阵函数*/int i,j; for(i=0;in;i+)for(j=0;jn;j+) printf(%2d,Mij);printf(n);int zi

14、fan() /*判断输入的关系是否自反函数*/int count = 0;for(i=0;in;i+)if(Mii=1)count+;if(count = n) return 1;elsereturn 0;int duichen() /*判断输入的关系是否对称函数*/ 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(fl

15、ag=0)break;for(k=0;kn;k+)if(Mij=1&Mjk=1&Mik!=1) flag=0;break; return flag;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)

16、;printf(请输入这个集合上的一个等价关系R:n);getguanxi(); /*调用获得关系R并输出显示函数*/ translate(); /*调用转换为关系矩阵函数*/printf(R的关系矩阵为：n);display(); /*调用输出关系矩阵函数*/t=zifan()&duichen()&chuandi(); /*判断关系是否等价*/while(t!=1) printf(您输入的不是等价关系，没有商集，请重新输入！n); getguanxi(); /*调用获得关系R并输出显示函数*/ clearM(); /*矩阵清零*/ translate(); /*调用转换为关系矩阵函数*/ printf(R的关系矩阵为：n); display(); /*调用输出关系矩阵函数*/t=zifan()&duichen()&chuandi(); /*判断关系是否等价*/printf(您所输入的集合和等价关系相应的商集为：n);caculate(equ,A,n); /*调用计算商集函数*/getchar();七、其他收获和体会相对于上一次的实验，由于积累了经验，并且掌握了一定的技巧，所以本次实验相对来说更得心应手，但在实验期间还是碰到了许多困难。本次实验中，我选择了2. 求有限集上等价关系的数目和3. 求解商集，输入集合和等价关系，求相应的商集。首先我还