离散数学实验报告

1、 离散数学闭包实验报告 专业 12计算机科学与技术 学号 姓名 周谦益 时间 201111-15 一、实验目的1. 通过上机程序，进一步加深对关系中自反闭包，对称闭包，传递闭包的理解。2. 掌握Warshall算法。3. 学会用程序解决离散数学中的问题。4. 增强我们编写程序的能力。二、实验内容 求有限集上给定关系的自反、对称和传递闭包（用Warshall算法）。三、实验环境 我的实验是在Vs2008实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。四、实验原理和实现过程设计思路 在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置

2、为1就可；对称闭包则只需要将矩阵中数值为1的元素关于主对角线对称的元素数值也设为1就可以了；而对于传递闭包，用Warshall算法可以很方便的计算出来。下面我就来具体分析一下每一种闭包运算的设计。 自反闭包的设计：我们只要把关系矩阵的对角线的元素全赋值为1就可以啦。具体程序如下：求自反闭包的程序：int Relation:Reflexive()/求自反闭包的函数for(int i=0;iLen;i+)if(!Rii)return(0);return(1);对称闭包的求法：对于对称闭包，我们只只需要将矩阵中数值为1的元素的对称位置的元素数值也设为1就可以了。具体程序如下：对称闭包： int Re

3、lation:Symmetric()/对称闭包的函数int i,j,K=Len-1;for(i=0;iK;i+)for(j=i+1;jLen;j+)if(Rij!=Rji)return(0);return(1);传递闭包设计：传递闭包我主要用Warshall算法来求。书上的Walshall算法的伪代码如下：设R的关系矩阵为M(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)，否则结束根据Warshall算法，我设计求出了关系的传递闭包，具体程序如下：int Relation:Tra

4、nsitive()/传递闭包函数Relation t;t=C_t(1);for(int i=0;iLen;i+)for(int j=0;jLen;j+)if(Rij!=t.Rij)return(0);return(1);把上面的每个子函数串在一起，再加上主函数，就可以实现这次实验的要求。程序的完整代码如下所示：#include stdafx.h#include using namespace std;int const Max=20;class Relationprotected:int Len,AMax,RMaxMax;int Index(int x);public:Relation()Le

5、n=0;/空集A，空关系RRelation(int *p,int QMaxMax,int n);/n个元素集合A及其关系int IsofA(int x);/x是否属于Aint IsofR(int x,int y);Relation UnionA(Relation R1);/AUR1Relation CrossR(Relation R1);Relation C_r();Relation C_s();Relation C_t();Relation C_t(int);int Reflexive();int Symmetric();/判断R是否对称int Transitive();int Equiva

6、lent_Relations();void PrintA();void PrintR();int Relation:Index(int x)int i;for(i=0;iLen;i+)if(Ai=x)return(i);return(-1);Relation:Relation(int *p,int QMaxMax,int n)int i,j;for(i=0;in;i+)Ai=pi;for(j=0;jn;j+)Rij=Qij;Len=i;int Relation:Reflexive()/求自反闭包的函数for(int i=0;iLen;i+)if(!Rii)return(0);return(1)

7、;int Relation:Symmetric()/对称闭包的函数int i,j,K=Len-1;for(i=0;iK;i+)for(j=i+1;jLen;j+)if(Rij!=Rji)return(0);return(1);int Relation:IsofA(int x)for(int i=0;iLen;i+)if(Ai=x)return(1);return(0);int Relation:IsofR(int x,int y)int i,j;i=Index(x);j=Index(y);if(i=-1|j=-1|Rij=0)return(0);return(1);Relation Relat

8、ion:UnionA(Relation R1)int i,j;Relation t;for(i=0;iLen;i+)t.Ai=Ai;t.Len=Len;for(j=0;jR1.Len;j+)for(i=0;i=Len)t.At.Len+=R1.Aj;for(i=0;it.Len;i+)for(j=0;jt.Len;j+)t.Rij=0;return(t);Relation Relation:CrossR(Relation R1)int i,j;Relation t;for(i=0;iLen;i+)t.Ai=Ai;for(j=0;jLen;j+)t.Rij=Rij & R1.Rij;t.Len=

9、Len;return(t);Relation Relation:C_r()/自反闭包int i,j;Relation t;for(i=0;iLen;i+)t.Ai=Ai;for(j=0;jLen;j+)t.Rij=Rij;if(i=j)t.Rij=1;t.Len=Len;return(t);Relation Relation:C_s()/对称闭包int i,j;Relation t;for(i=0;iLen;i+)t.Ai=Ai;for(j=i;jLen;j+)if(Rij=1)t.Rij=t.Rji=1;elseif(Rji=1)t.Rij=t.Rji=1;else t.Rij=t.Rji=

10、0;t.Len=Len;return(t);Relation Relation:C_t()/传递闭包int i,j,k,l,v;Relation t;int MMaxMax,NMaxMax;for(i=0;iLen;i+)t.Ai=Ai;for(j=0;jLen;j+)t.Rij=Mij=Rij;for(i=1;iLen;i+)/共Len-1次for(j=0;jLen;j+)/行for(k=0;kLen;k+)/列v=0;for(l=0;lLen;l+)/对行列加乘v=v|Mjl&Rlk;/布尔加乘Njk=v;for(j=0;jLen;j+)for(k=0;kLen;k+)t.Rjk=t.Rj

11、k|Njk;Mjk=Njk;t.Len=Len;return(t);Relation Relation:C_t(int x)int i,j,l;Relation t;for(i=0;iLen;i+)t.Ai=Ai;for(j=0;jLen;j+)t.Rij=Rij;for(i=0;iLen;i+)for(j=0;jLen;j+)if(t.Rji=1)for(l=0;lLen;l+)t.Rjl=t.Rjl|t.Ril;t.Len=Len;return(t);int Relation:Transitive()/求传递闭包函数Relation t;t=C_t(1);for(int i=0;iLen;

12、i+)for(int j=0;jReflexive()&Symmetric()&Transitive();void Relation:PrintA()int i;if(Len=0)cout空集n;elsefor(i=0;iLen;i+)coutAit;if(i+1)%10=0)coutendl;coutendl;void Relation:PrintR()int i,j;if(Len=0)cout空关系n;elsefor(i=0;iLen;i+)cout第i行：endl;for(j=0;jLen;j+)coutRijt;if(i+1)%10=0)coutendl;coutendl;int ma

13、in(int argc, char* argv)int B10=10,11,12,13,14,15,16,17,18,19;int C6=30,31,12,16;int M1MaxMax=0,1,0,1,1,1,0,1,0,0,1,0,0,1,0,1;Relation R1,R2(C,M1,4);Relation Rb(B,M1,4);Rb.PrintA();Rb.PrintR();coutRb.IsofA(12)isof12!endl;coutRb.IsofA(15)isof15!endl;coutRb.IsofR(10,11)isof 10-11!endl;coutRb.IsofR(9,1

14、1)isof 9-11!endl;coutRb.IsofR(10,21)isof 10-21!endl;R1=R2.CrossR(Rb);R1.PrintR();cout等价:R1.Equivalent_Relations()endl;coutR2n;R2.PrintR();coutR1n;R1.PrintR();coutReflexive:R1.Reflexive()endl;coutSymmetric:R1.Symmetric()endl;coutTransitive:R1.Transitive()endl;R1=R2.C_r();R1.PrintR();coutC_rn;coutReflexive:R1.Reflexive()endl;R1=R2.C_s();R1.PrintR();coutC_sn;coutSymmetric:R1.Symmetric()endl;R1=R2.C_t();R1.PrintR();coutC_tn;R1=R2.C_t(1);coutTransitive:R1.Transitive()endl;R1.PrintR();coutC_rn;cout等价:R1.Equivalent_Relations()endl;Rb