离散数学关系的闭包运算(共6页).doc

《离散数学关系的闭包运算(共6页).doc》由会员分享，可在线阅读，更多相关《离散数学关系的闭包运算(共6页).doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上离散数学实验报告学 院 软件学院 专 业 软件工程 指导教师 邹丽娜 学 号 姓 名 冯立勇 提交日期 2011-12-25 实验二 关系的闭包运算一 、实验目的熟悉关系的闭包运算，编程实现关系闭包运算算法。一 、实验内容利用矩阵求解有限集上给定关系的自反、对称和传递闭包。三. 实验过程1. 算法分析：在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（二选一即可）：算法1：直接根据计算，过程略。算法2：Warshall算法(1962)设R的关系矩阵为M

2、(1)令矩阵A=M(2)置i=1(3)对所有的j，若Aj，i=1，则对于 k=1，2，n，令Aj，k=Aj，k+Ai，k 注：此处为逻辑加，可以使用运算符|(4) i=i+l(5)若in，则转到(3)，否则结束开始声明各子函数输入关系矩阵输入z z=1；调用自反闭包函数z=2，调用对称闭包函数z=3调用传递闭包函数结束 流程图2. 程序代码：#include void output(int s100); void zifan(int s2100); void duichen(int s2100); void chuandi2(int s2100); void chuandi1(int s210

3、0); void aa(); int s100100,z;int d,n ,i,j;int main()aa();return 0;void aa() 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,&sij); printf(输入对应序号选择算法n1:自反闭包n2:传递闭包1n3:传递闭包(Warh

4、all算法)2n4:对称闭包n);scanf(%d,&z);switch(z) case 1:zifan(s); break; case 2:chuandi1(s);break; case 3:chuandi2(s);break; case 4:duichen(s); break;void output(int s100)printf(所求关系矩阵为n); for(i=0;in;i+) for(j=0;jd;j+) printf(%d,sij); printf(n); void zifan(int s2100) for(i=0;in;i+) s2ii=1;output(s2);aa();voi

5、d duichen(int s2100)int s1100100; for(i=0;in;i+) for(j=0;jd;j+) s1ji=s2ij; for(i=0;in;i+) for(j=0;j1) s2ij=1; output(s2);aa();void chuandi1(int s2100)int m100100,a100100,k,h; int t100100; for(i=0;in;i+) for(j=0;jd;j+) aij=0; tij=s2ij; mij=s2ij;for(h=0;hn;h+) for(i=0;in;i+) for(j=0;jd;j+) if(mij=1) for(k=0;kn;k+)if(s2jk=1) aik=1; for(i=0;in;i+) for(j=0;j1) tij=1; output(t);aa();void chuandi2(int s2100)int k; for(i=0;in;i+) for(j=0;jn;j+) if(s2ji=1) for(k=0;kn;k+)s2jk+=s2ik; for(i=0;in;i+) for(j=0;j1) s2ij=1;output(s2);aa();3.实验数据及结果分析专心-专注-专业