离散数学实验报告

实验1_闭包1离散数学闭包实验报告专业12计算机科学与技术学号12407127姓名周谦益时间2011—11--15一、实验目的1.通过上机程序，进一步加深对关系中自反闭包，对称闭包，传递闭包的理解。2.掌握Warshall算法。3.学会用程序解决离散数学中的问题。4.增强我们编写程序的能力。二、实验内容求有限集上给定关系的自反、对称和传递闭包（用Warshall算法）。三、实验环境我的实验是在Vs2008实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。四、实验原理和实现过程设计思路在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则只需要将矩阵中数值为1的元素关于主对角线对称的元素数值也设为1就可以了；而对于传递闭包，用Warshall算法可以很方便的计算出来。下面我就来具体分析一下每一种闭包运算的设计。自反闭包的设计：我们只要把关系矩阵的对角线的元素全赋值为1就可以啦。实验1_闭包2具体程序如下：求自反闭包的程序：intRelation::Reflexive()//求自反闭包的函数{for(inti=0;iLen;i++)if(!R[i][i])return(0);return(1);};对称闭包的求法：对于对称闭包，我们只只需要将矩阵中数值为1的元素的对称位置的元素数值也设为1就可以了。具体程序如下：对称闭包：intRelation::Symmetric()//对称闭包的函数{inti,j,K=Len-1;for(i=0;iK;i++)for(j=i+1;jLen;j++)if(R[i][j]!=R[j][i])return(0);return(1);};传递闭包设计：传递闭包我主要用Warshall算法来求。书上的Walshall算法的伪代码如下：设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)，否则结束根据Warshall算法，我设计求出了关系的传递闭包，具体程序如下：intRelation::Transitive()//传递闭包函数{Relationt;t=C_t(1);for(inti=0;iLen;i++)for(intj=0;jLen;j++)实验1_闭包3if(R[i][j]!=t.R[i][j])return(0);return(1);};把上面的每个子函数串在一起，再加上主函数，就可以实现这次实验的要求。程序的完整代码如下所示：#includestdafx.h#includeiostreamusingnamespacestd;intconstMax=20;classRelation{protected:intLen,A[Max],R[Max][Max];intIndex(intx);public:Relation(){Len=0;};//空集A，空关系RRelation(int*p,intQ[Max][Max],intn);//n个元素集合A及其关系intIsofA(intx);//x是否属于AintIsofR(intx,inty);RelationUnionA(RelationR1);//AUR1RelationCrossR(RelationR1);RelationC_r();RelationC_s();RelationC_t();RelationC_t(int);intReflexive();intSymmetric();//判断R是否对称intTransitive();intEquivalent_Relations();voidPrintA();voidPrintR();};intRelation::Index(intx){inti;for(i=0;iLen;i++)if(A[i]==x)return(i);return(-1);};Relation::Relation(int*p,intQ[Max][Max],intn)实验1_闭包4{inti,j;for(i=0;in;i++){A[i]=p[i];for(j=0;jn;j++)R[i][j]=Q[i][j];};Len=i;};intRelation::Reflexive()//求自反闭包的函数{for(inti=0;iLen;i++)if(!R[i][i])return(0);return(1);};intRelation::Symmetric()//对称闭包的函数{inti,j,K=Len-1;for(i=0;iK;i++)for(j=i+1;jLen;j++)if(R[i][j]!=R[j][i])return(0);return(1);};intRelation::IsofA(intx){for(inti=0;iLen;i++)if(A[i]==x)return(1);return(0);};intRelation::IsofR(intx,inty){inti,j;i=Index(x);j=Index(y);if(i==-1||j==-1||R[i][j]==0)return(0);return(1);};RelationRelation::UnionA(RelationR1){inti,j;Relationt;for(i=0;iLen;i++)t.A[i]=A[i];实验1_闭包5t.Len=Len;for(j=0;jR1.Len;j++){for(i=0;iLen;i++)if(t.A[i]==R1.A[j])break;if(i=Len)t.A[t.Len++]=R1.A[j];};for(i=0;it.Len;i++)for(j=0;jt.Len;j++)t.R[i][j]=0;return(t);};RelationRelation::CrossR(RelationR1){inti,j;Relationt;for(i=0;iLen;i++){t.A[i]=A[i];for(j=0;jLen;j++)t.R[i][j]=R[i][j]&&R1.R[i][j];};t.Len=Len;return(t);};RelationRelation::C_r()//自反闭包{inti,j;Relationt;for(i=0;iLen;i++){t.A[i]=A[i];for(j=0;jLen;j++){t.R[i][j]=R[i][j];if(i==j)t.R[i][j]=1;};};t.Len=Len;return(t);};实验1_闭包6RelationRelation::C_s()//对称闭包{inti,j;Relationt;for(i=0;iLen;i++){t.A[i]=A[i];for(j=i;jLen;j++){if(R[i][j]==1)t.R[i][j]=t.R[j][i]=1;else{if(R[j][i]==1)t.R[i][j]=t.R[j][i]=1;elset.R[i][j]=t.R[j][i]=0;};};};t.Len=Len;return(t);};RelationRelation::C_t()//传递闭包{inti,j,k,l,v;Relationt;intM[Max][Max],N[Max][Max];for(i=0;iLen;i++){t.A[i]=A[i];for(j=0;jLen;j++)t.R[i][j]=M[i][j]=R[i][j];};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||M[j][l]&&R[l][k];//布尔加乘N[j][k]=v;};for(j=0;jLen;j++)for(k=0;kLen;k++)实验1_闭包7{t.R[j][k]=t.R[j][k]||N[j][k];M[j][k]=N[j][k];};};t.Len=Len;return(t);};RelationRelation::C_t(intx){inti,j,l;Relationt;for(i=0;iLen;i++){t.A[i]=A[i];for(j=0;jLen;j++)t.R[i][j]=R[i][j];};for(i=0;iLen;i++){for(j=0;jLen;j++)if(t.R[j][i]==1){for(l=0;lLen;l++)t.R[j][l]=t.R[j][l]||t.R[i][l];};};t.Len=Len;return(t);};intRelation::Transitive()//求传递闭包函数{Relationt;t=C_t(1);for(inti=0;iLen;i++)for(intj=0;jLen;j++)if(R[i][j]!=t.R[i][j])return(0);return(1);};intRelation::Equivalent_Relations(){return(this-Reflexive()&&Symmetric()&&Transitive());};实验1_闭包8voidRelation::PrintA(){inti;if(Len==0)cout空集\n;else{for(i=0;iLen;i++){coutA[i]'\t';if((i+1)%10==0)coutendl;};};coutendl;};voidRelation::PrintR(){inti,j;if(Len==0)cout空关系\n;else{for(i=0;iLen;i++){cout第i行：endl;for(j=0;jLen;j++){coutR[i][j]'\t';if((i+1)%10==0)coutendl;};};};coutendl;};intmain(intargc,char*argv[]){intB[10]={10,11,12,13,14,15,16,17,18,19};intC[6]={30,31,12,16};intM1[Max][Max]={{0,1,0,1},{1,1,0,1},{0,0,1,0},{0,1,0,1}};RelationR1,R2(C,M1,4);RelationRb(B,M1,4);Rb.PrintA();Rb.PrintR();coutRb.IsofA(12)isof12!endl;coutRb.IsofA(15)isof15!endl;实验1_闭包9coutRb.IsofR(10,11)isof10-11!endl;coutRb.IsofR(9,11)isof9-11!endl;coutRb.IsofR(10,21)isof10-21!endl;R1=R2.CrossR(Rb);R1.PrintR();cout等价:R1.Equivalent_Relations()endl;coutR2\n;R2.PrintR();coutR1\n;R1.PrintR();coutReflexive:R1.Reflexive()endl;coutSymmetric:R1.Symmetric()endl;coutTransitive:R1.Transitive()endl;R1=R2.C_r();R1.PrintR();coutC_r\n;coutReflexive:R1.Reflexive()endl;R1=R2.C_s();R1.PrintR();coutC_s\n