实验二离散报告

1、实验报告课程名称离散数学实验名称集合上二元关系性质判定的实现指导单位计算机科学与技术系实验报告实验名称集合上二元关系性质判定的实现指导教师实验类型验证实验学时4实验时间一、实验目的和要求内容：编程实现任意集合上二元关系的性质判定。要求：能正确判定任意二元关系的自反性、对称性、传递性、反自反性和 反对称性。二、实验环境（实验设备）X86计算机IDE:CodeBlocks 16.01 编译器：GUN GCC三、实验原理及内容输入集合已经集合上面的序偶关系，输出关系满足的性质。整体思路为将关系转换成矩阵，根据矩阵判断关系的性质。若矩阵主对角线元素都是1,则满足自反性。若矩阵主对角线元素都是0,则满足

2、反自反性。 若矩阵所有元素关于主对角线对称，则满足对称性。若矩阵中出现了关于主 对角线对称的元素，则不满足反对称性，否则满足反对称性。若矩阵的传递 闭包等于矩阵自己，则矩阵满足传递性。为了能够处理集合中含有字母的情况，程序将所有输入当成字符串来处理，然后将每一个字符与矩阵下标进行键值映射，这样，在序偶关系中，通过字符就可以很轻松的找到对应的下标，从而很轻松将序偶关系用矩阵表示程序定义的全局变量有：-_char a200;保存输入的集合A字符串char R300;保存输入的序偶R字符串map<char,int>_ML/保存字符与矩阵下标的映射_ _（一霊#include<map

3、>） _int X200200;II关系对应的矩阵int len;II集合A中含有的元素数量int tmp200200;II求传递闭包过程中，用来保存矩阵的传递闭包int tmp1200200;求传递闭包过程中，用来保存矩阵的一N 一次方。第一步：将集合中的元素与矩阵下标映射由于集合A中可能含有字母，为了后面能够更加方便的将序偶关系转换成矩阵，第一步先将集合 A中所以元素与矩阵下标进行映射，并统计集合A中元素个数。引用STL库文件#include<map>实现键值映射。代码为：int init()_intj=0;_intjl=strlen(a);intj=0;for(i=Q;

4、i<l;i+).if(ai>='a'&&ai<='z')|(ai>='A'&&ai<='Z')|(ai>='0'&&ai<='9')Mai=j+;return j; 算法复杂度分析：对输入的字符串进行循环遍历，时间一复杂度为一o_ _(m。 第二步，将关系转换成矩阵由于上一步虫已经将集合中元素与矩阵下标进行了映射，那定位关系中一第一元素和第二元素就可以直接用语句MRI,将关系转换成矩阵也就容易多了，XMRi+1

5、MRi+3表示序偶对应的矩阵元素。代码：voidjsolve() inmi=j=O;_ int 匸strle n(R); while(ivl)_if(Ri=：')_.1if(fin d(a,a+strle n(a) ,Ri+1)=a+strle n( a)|fi nd(a,a+strle n( a),Ri+3)=a+strle n( a)printf("输入有误，关系R中包含非法元素n");exitlOX.XMRi+1MRi+3=1;i+=5;_elsei+;丄算法复杂度分析：对输入的序偶字符串进行遍历，时间复杂度是0( n)。用矩阵进行运算，空间复杂度是一_0(门

6、八2)。第三步：根据矩阵求满足的性质_(1).自反性如果矩阵中主对角线元素都是1,那么就满足自反性，否则不满足。判断的时候只要找到第一个对角线元素不是1，就可以断定不满足自反性代码：bool JudgeZiFa n()int i;int flag=1;for(i=0;i<lenj+)if(Xii!=1)flag=0;break;if(flag)_return_ true;elsereturn false;算法复杂度分析：由于只要扫描对角线元素，所以时间复杂度是0( n)<(2) 反自反性_如果矩阵中主对角线元素都是_0，那么就满足反宜反性，否则，就不 满足。判断的时候扫描对角线元素

7、，只要出理丄就可断定不满足反自反性。-代码：bool JudgeFa nZiFa n()for(int i=0;i<len;i+)-if(Xii>0)-retur n false;return true;(3) 对称性如果对矩阵中，每一个Xij，都有Mji=1 _，那么就满足对称性，否 则，不满足对称性。若出现Xij=1 &&Xji=0,就可以断定不满足对称性。 判断的时候只要扫描上三角矩阵即可。bool JudgeDuiChe ng()int i,j；_foMi=0;iVenji+) _for(j=Q;j<JenJ+) _if(Xij)-if(Xji!=1)

8、retur n false;return true;算法复杂度分析：扫描上三角矩阵，时间复杂度是0(门八2)。(4) 反对称性如果矩阵中出现了关于主对角线对称的元素，那么就不满足反对称性，否则，满足反对称性。判断的时候只要出现了Xij=1 && Xji=1就可以!B!B-断定不满足反对称性。判断的时候也只要扫描上三角矩阵。代码：bool JudgeFa nDuiChe ng()for(int i=0;i<ien;i+) _for(intj=i+1;j<len；j+)if(Xij)-if(Xji)return false;丄return true;算法复杂度分析：扫描

9、上三角矩阵，时间复杂度是_O( n2)(5) 传递性如果矩阵的传递闭包等于矩阵自己，那么就满足传递性，否则不满足。求矩阵的传递闭包首先定义一个求矩阵的幕的运算，这个地方只要求矩 阵和X矩阵相乘就可以。还要定义一个特殊的求矩阵相加的运算，如果相加 后矩阵元素大于1 ,就把元素置为1最后只要比较一下传递闭包是不是与 X 相等就行了。具体步骤是先定义两个全局数组tmp叩,和tmp1，首先初始化为_ x _矩阵。_ _tmp1用来累计和矩阵_ _X_的乘积，每次都和_ _X_相乘一次-tmpi 的 幂就增加，然后将 tmpi _与Jtmp矩阵相加.(元素大于 1就置成_ 1)，如此循环。 函数cal

10、()为tmpi与X相乘，函数combine为tmpi与tmp相加。代码：booLJudgeChua nDi()int i,j;for(i=0;i<le n;i+)for(j=0;jvle n;j+)tmpij=Xij;.tmp1ij=Xij;for(i=2;i<=len;i+)_cal();jcombineO;_for(int i=0;i<Jen;i+)return false;“=retum true;求矩阵的幕的运算：首先o将X矩阵拷贝到tmp1200200,然后每次都将tmp1与X相乘代码：void cal()int_xtmp20O20Ol；_ int k,p;for(

11、i nt i=O;i<le n;i+)_for(intj=0;i<len;j+) _int sum=0;for(k=0;k<len;k+)sum+=tmp1ilk*Xkjl;if(sum=0).xtmpij=0;elsextmpij=1;for(int i=0;i<len;i+_)for(i nt j=O;jvle n;j+)tmp1ij=xtmpij;1,就置为矩阵相加的运算：如果相加后元素大于代码：void comb in e()for(in t i=0;i<le n;i+)_for(int j=0;j<le n;j+)Jf(imp1ijl|tmplij

12、) _tmpij=1;算法复杂度分析：主函数中，初始化tmp和tmpl时间复杂度是0(门八2)。调用循环len-1次，然后每次cal函数进行矩阵相乘的复杂度是 0(n八3), combine 进行矩阵相加是0(门八2)。这个运算步骤的时间复杂度是 0(n八4)，最后将tmp 与X比较的时间复杂度是0(n八2)。综上，时间复杂度是 0(n八4)。空间复杂度分析：由于定义了两个临时数组tmp和tmp1，每一个是0(n八2),所以，空间复杂度是 0(n八2)。主函数进行数据的读入，输出，以及函数的调用 二 ia.ia.ia.Main _函数代码：.int mai n()memset(tmp40,si

13、zeof(tmp);memset(tmp1,0,sizeof(tmp1);memset(a,0,sizeof(a);memset(R,0,sizeof(R);printf("请输入集合A,以逗号隔开各元素，回车结束n");gets(a);len 二i ni t();prinifd请输入关系一 R，格式 <a4>$c4>.回车结束n"Zgets(R);solve();bool ZiFa n=JudgeZiFa n();bool _DuiCheng=JudgeDuiCheng().;bool _ChuanDi=JudgeChuanDK);bool F

14、an ZiFa n=JudgeFa nZiFa n();bool Fan DuiChe ng二JudgeFa nDuiChe ng();printf("性质为:n");if(ZiFa n)_printf("自反性 n”)；丄if(Fa nZiFan)_卫infC反 自反性n");.ifDuiChengX.“griMfC 宾对称性n");1_if(FanDuiCheng)._rinlf("反对称，性 n");.1if(Chua nDi)intfC_传递性n");return 0;程序测试：案例一：课本112页例题5输

15、入集合为123,4anbi 关系为 <1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>结果正确。案例二：输入集合为一 aJb,c输入关系为 <a,a>,vb,b>,<c,c>结果正确。一案例三：课本131页例题1输入集合1,2,3,4输入关系：<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3&g

16、t;结果正确案例四：输入集合a,b,c,d输入关系：<a,b>,<b,a>,vb,c>,vc,d>结果正确案例五：程序容错性测试结果正确四、实验小结（包括问题和解决方法、心得体会、意见与建议等）1.个人感觉这个程序的难点是传递性的判断，因为要求传递闭包，涉及到 矩阵的乘法和加法，矩阵相乘在循环的时候循环变量要弄清楚，容易出错。2这个程序只能处理小批量数据，最多将矩阵行列改成几千，处理包含几千 元素的集合。对于包含上万元素的集合的数据，如果还用二维数据，会爆栈, 应该改为三兀组表示的稀疏矩阵3程序的容错性。如果不按照提示的规则输入，比如多几个空格标点亠程序_ _ _ 能恰当处理，如果关系中出现了集合以外的元素，程序能判断并提示。但是 关系一定要以a,b的形式出现，否则程序将不能识别，导致结果出错。五、指导教师评语批阅人仅供个人用于学习、研究；不得用于商业用途For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen