离散数学测试题

西华师大实验报告利用Warshall算法求二元关系的可传递闭包1离散数学半期考核专业软件工程指导老师蒲在毅学生姓名曾舜尧学号201113340348（11级）西华师大实验报告利用Warshall算法求二元关系的可传递闭包2提交日期2012年5月1日利用Warshall算法求二元关系的可传递闭包学生：曾舜尧指导老师：蒲在毅摘要本实验主要是研究利用Warshall算法求二元关系的可传递闭，实验主要内容是研究当集合的阶数N较大时,求二元关系的可传递闭包的工作量时相当庞大的。幸运的时1962年S.Warshall提出了一个计算R+的有效方法,可在计算机上编程实现。采用C语言函数写出这个算法。程序中用temp[i][j]表示关系矩阵MR的第i行第j列元素,用||表示逻辑或计算。计算R+的函数名为Warshall,它的两个形式参数m和n分别表示关系矩阵M和矩阵的行数。函数的实现实际上是一个三重循环结构.关键词二元关系关系矩阵可传递闭包Warshall算法三重循环引言离散数学是现代数学的一个重要分支,也是计算机科学技术,电子信息技术,生物技术等的核心基础课程.二元关系是离散数学中重要内容。世界上的事物都在一定范围内以某种方式互相联系,例如天体之间可以用的是同一星系来划分,人们之间可以用是否有共同的祖先来定血缘.类似的数学或者计算机科学中的研究对象也以各种不同形式互相联系着,例如整数之间以大小,整除或同余关系互相联系着,命题公式之间以是否具有相同的主合取范式相联系,程序中两个变量可以是否占有同一内存地址相联系。总之,事物之间总可以根据需要确定相应的关系.从数学的角度来看,这类联系就是某个集合中元素之间存在的关系。一个二元关系可能具有某种性质,也可能不具有这种性质。关系闭包就是使一个二元关系变成具有指定性质的关系,并且还要满足最小条件。Warshall算法的基本思想对每个结点（从第一列开始），找出所有具有到此结点的有向边的结点（即该列中元素为1的所在行的结点），再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行（添加新的有向边）（反映了如果这些结点没有到其它结点的有向边，但有到该结点的有向边，再通过该结点间接到达其它结点，根据传递闭包的定义，这些结点就必然有一条有向边到达其它结点。）设R是集合上的二元关系,Mr是R的关系矩阵西华师大实验报告利用Warshall算法求二元关系的可传递闭包3(1)置新矩阵A:=Mr(2)置(列)j:=1(3)对所有的i(1≤i≤n)如A(i,j)=1,则对k=1,2,…,nA(i,k):=A(i,k)A(j,k)(即将A的第i行与A的第j行进行逻辑加后送回A的第i行)(4)j:=j+1(5)如j≤n转(3),否则停止。主要实验流程图西华师大实验报告利用Warshall算法求二元关系的可传递闭包4实验源代码程序开始输入矩阵的行数和列数输入矩阵各元素的值输入是否正确?计算出可传递闭包关系矩阵打印可传递闭包的关系矩阵结束正确不正确西华师大实验报告利用Warshall算法求二元关系的可传递闭包5//Warshall0.cpp#includestdio.hvoidmain(){printf(利用Warshall算法求二元关系的可传递闭包\n);voidwarshall(int,int);intm[20][20],n;printf(请输入矩阵的行数n:);scanf(%d,&n);warshall(m[20][20],n);}voidwarshall(intm[20][20],intn){inti,j,k;intm[20][20];for(i=0;in;i++){printf(请输入矩阵第%d行元素:,a);for(i=0;in;i++){scanf(%d,&m[i][j]);}}for(i=0;in;i++){for(j=0;jn;j++){if(m[j][i]==1){for(k=0;kn;k++){m[j][k]=m[i][k]||m[j][k];}}}printf(可传递闭包关系矩阵是:\n);for(i=0;in;i++){Printf(\t\t);for(j=0;jn;j++){printf(%d,m[i][j]);}printf(\n);西华师大实验报告利用Warshall算法求二元关系的可传递闭包6}}代码测试C语言中测试网络在线检查分析原因1.由于使用了数组来储存数据，但是我们无法给数组定义确切的大小，因此要重新定义函数，将原来的定义的函数中的m[][]换成一个变量，然后在定义一个固定大小的数组来存放数据。西华师大实验报告利用Warshall算法求二元关系的可传递闭包7改进方法后重新写的代码如下//Warshall.cpp#includestdio.hvoidwarshall(intk,intn){inti,j,t;inttemp[20][20];for(inta=0;ak;a++){printf(请输入矩阵第%d行元素:,a);for(intb=0;bn;b++){scanf(%d,&temp[a][b]);}}for(i=0;ik;i++){for(j=0;jn;j++){if(temp[j][i]==1){for(t=0;tn;t++){temp[j][t]=temp[i][t]||temp[j][t];}}}}printf(可传递闭包关系矩阵是:\n);for(i=0;ik;i++){printf(\t\t);for(j=0;jn;j++){printf(%d,temp[i][j]);}printf(\n);}}voidmain(){西华师大实验报告利用Warshall算法求二元关系的可传递闭包8printf(利用Warshall算法求二元关系的可传递闭包\n);voidwarshall(int,int);intk,n;printf(请输入矩阵的行数i:);scanf(%d,&k);printf(请输入矩阵的列数j:);scanf(%d,&n);warshall(k,n);}试验结果截图展示1、启动程序2、输入矩阵并得到结果西华师大实验报告利用Warshall算法求二元关系的可传递闭包9实验总结程序编写时要注意各个符号定义，要学会自己独立解决出现的各个问题。Warshall算法给我们提供了一个求二元关系传递闭包的高效方法。综合现代计算机技术,利用Warshall算法我们可轻松的求出一个二元关系的可传递闭包。西华师大实验报告利用Warshall算法求二元关系的可传递闭包10指导老师评阅意见指导老师（签字）：年月日