离散数学关系的闭包运算

《离散数学》实验报告学院软件学院专业软件工程指导教师邹丽娜学号10008118姓名冯立勇提交日期2011-12-25实验二关系的闭包运算一、实验目的熟悉关系的闭包运算，编程实现关系闭包运算算法。一、实验内容利用矩阵求解有限集上给定关系的自反、对称和传递闭包。三.实验过程1.算法分析：在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（二选一即可）：算法1：直接根据niiRRt1)(计算，过程略。算法2：Warshall算法(1962)设R的关系矩阵为M(1)令矩阵A=M(2)置i=1(3)对所有的j，若A[j，i]=1，则对于k=1，2，…，n，令A[j，k]=A[j，k]+A[i，k]注：此处为逻辑加，可以使用运算符||(4)i=i+l．(5)若i≤n，则转到(3)，否则结束．流程图开始声明各子函数输入关系矩阵输入zz=1；调用自反闭包函数z=2，调用对称闭包函数z=3调用传递闭包函数结束2.程序代码：#includestdio.hvoidoutput(ints[][100]);voidzifan(ints2[][100]);voidduichen(ints2[][100]);voidchuandi2(ints2[][100]);voidchuandi1(ints2[][100]);voidaa();ints[100][100],z;intd,n,i,j;intmain(){aa();return0;}voidaa(){printf(请输入矩阵的行数(必须小于10)\n);scanf(%d,&n);printf(请输入矩阵的列数(必须小于10)\n);scanf(%d,&d);printf(请输入关系矩阵\n);for(i=0;in;i++){printf(\n);printf(请输入矩阵的第%d行元素,i);for(j=0;jd;j++)scanf(%d,&s[i][j]);}printf(输入对应序号选择算法\n1:自反闭包\n2:传递闭包1\n3:传递闭包(Warhall算法)2\n4:对称闭包\n);scanf(%d,&z);switch(z){case1:zifan(s);break;case2:chuandi1(s);break;case3:chuandi2(s);break;case4:duichen(s);break;}}voidoutput(ints[][100]){printf(所求关系矩阵为\n);for(i=0;in;i++){for(j=0;jd;j++)printf(%d,s[i][j]);printf(\n);}}voidzifan(ints2[][100]){for(i=0;in;i++)s2[i][i]=1;output(s2);aa();}voidduichen(ints2[][100]){ints1[100][100];for(i=0;in;i++)for(j=0;jd;j++)s1[j][i]=s2[i][j];for(i=0;in;i++)for(j=0;jd;j++){s2[i][j]=s2[i][j]+s1[i][j];if(s2[i][j]1)s2[i][j]=1;}output(s2);aa();}voidchuandi1(ints2[][100]){intm[100][100],a[100][100],k,h;intt[100][100];for(i=0;in;i++)for(j=0;jd;j++){a[i][j]=0;t[i][j]=s2[i][j];m[i][j]=s2[i][j];}for(h=0;hn;h++){for(i=0;in;i++)for(j=0;jd;j++)if(m[i][j]==1){for(k=0;kn;k++)if(s2[j][k]==1)a[i][k]=1;}for(i=0;in;i++)for(j=0;jd;j++){m[i][j]=a[i][j];t[i][j]+=a[i][j];a[i][j]=0;if(t[i][j]1)t[i][j]=1;}}output(t);aa();}voidchuandi2(ints2[][100]){intk;for(i=0;in;i++)for(j=0;jn;j++)if(s2[j][i]==1)for(k=0;kn;k++)s2[j][k]+=s2[i][k];for(i=0;in;i++)for(j=0;jn;j++)if(s2[i][j]1)s2[i][j]=1;output(s2);aa();}3.实验数据及结果分析