实验五--关系(答案)

实验五关系【实验目的】1.了解关系及其基本性质2.介绍等价关系3.*熟悉闭包【实验内容】要求：有基本流程描述、程序源码及运行结果截图。①写一个程序,测试关系是否是自反和对称的②判断关系是否是等价关系③*写程序实现Warshall算法,求出传递闭包【实验原理和方法】解题思路：自反：一个n阶矩阵a,对于0=in,和0=jn若a[i][j]=a[j][i]，则该关系为对称，若a[i][i]0则关系自反。用矩阵表示关系，判断关系是否是自反和对称。基本流程描述：关系的描述方法包括列举，关系图和关系矩阵等描述方法。（1）A上的二元关系用一个n×n关系矩阵R=nnijr)(表示，定义一个n×n数组r[n][n]表示n×n矩阵关系。（2）若R对角线上的元素都是1，则R具有自反性。（3）若R是对称矩阵，则R具有对称性。对称矩阵的判断方法是：RrRrjiij有,。（4）关系的传递性判断方法：对任意i，j，k，若111ikjkijrrr有且。（5）判断关系是否是等价关系，必须同时满足自反性、对称性、传递性。程序源代码：#includestdio.h#defineN3voidmain(){inta[N][N],i,j,m=0,n=0;printf(请输入您所需要测试的关系的关系矩阵（元素之限于0和1）：\n);for(i=0;iN;i++)for(j=0;jN;j++)scanf(%d,&a[i][j]);printf(\n);printf(关系矩阵为：\n);for(i=0;iN;i++){for(j=0;jN;j++)printf(%5d,a[i][j]);printf(\n);}for(i=0;iN;i++)for(j=0;jN;j++)if(a[i][j]==a[j][i])m++;if(m==N*N)printf(该关系是对称的!\n);elseprintf(该关系不是对称的!\n);for(i=0;iN;i++)if(a[i][i]0)n++;if(n==N)printf(该关系是自反的!\n);elseprintf(该关系不是自反的!\n);}//guanxi2.cpp:定义控制台应用程序的入口点。////#includestdafx.h#includestdio.h#defineN3voidmain(){inta[N][N],b[N][N],i,j,k,flag=1,flag1=1,flag2=1,flag3=1,m=0,n=0;printf(请输入您所需要测试的关系的关系矩阵（元素之限于和）：\n);for(i=0;iN;i++)for(j=0;jN;j++)scanf(%d,&a[i][j]);printf(\n);printf(关系矩阵为：\n);for(i=0;iN;i++){for(j=0;jN;j++)printf(%5d,a[i][j]);printf(\n);}//判断对称for(i=0;iN&&flag1;i++)for(j=0;jN&&flag1;j++)if(a[i][j]&&(a[j][i]!=1))//if(a[i][j]!=a[j][i])flag1=0;if(flag1)printf(该关系是对称的!\n);elseprintf(该关系不是对称的!\n);//判断自反for(i=0;iN&&flag2;i++)if(a[i][i]!=1)flag2=0;if(flag2)printf(该关系是自反的!\n);elseprintf(该关系不是自反的!\n);//判断传递性/*for(i=0;iN&&flag3;i++)for(j=0;iN&&flag3;j++)for(k=0;iN&&flag3;k++)if((a[i][j]&&a[j][k])&&(a[i][k]!=1))flag3=0;if(flag3)printf(该关系是传递的!\n);elseprintf(该关系不是传递的!\n);*/for(i=0;iN;i++){for(j=0;jN;j++){if(a[i][j]!=0){for(k=0;kN;k++){if(a[i][k]a[j][k]){flag3=0;//m=m+1;}}}}}if(flag3)printf(该关系是传递的!\n);elseprintf(该关系不是传递的!\n);②写一个程序,实现Warshall算法,求出传递闭包解题思路：设N阶方正A令j从0到N-1，循环N次，每对应一个j值令i从0到N-1，若A[i][j]0,即第i个元素与第j个元素有关系，则对应这个j和i令k从0到N-1，若A[j][k]0则令A[i][k]=1。一，基本流程描述：利用warshall算法求一个关系的闭包运算，实际上就是从上到下，遍历每一列，当遇到第j行第i列为一的话，将第i行加到第j行中，如果a[j][k]0,则令a[j][k]=1。二程序源代码：#includestdio.h#defineN4voidmain(){inta[N][N],i,j,k;printf(请输入关系矩阵：\n);for(i=0;iN;i++)for(j=0;jN;j++)scanf(%d,&a[i][j]);for(i=0;iN;i++)for(j=0;jN;j++){if(a[j][i]==1)for(k=0;kN;k++){a[j][k]=a[j][k]+a[i][k];if(a[j][k]==2)a[j][k]=1;}}printf(其对应的传递闭包关系为：\n);for(j=0;jN;j++){for(k=0;kN;k++)printf(%3d,a[j][k]);printf(\n);}}程序运行结果，