实验二离散报告

实 验 报 告课程名称离散数学实验名称集合上二元关系性质判定的实现指导单位计算机科学与技术系实 验 报 告实验名称集合上二元关系性质判定的实现指导教师实验类型验证实验学时4实验时间一、 实验目的和要求内容：编程实现任意集合上二元关系的性质判定。要求：能正确判定任意二元关系的自反性、对称性、传递性、反自反性和反对称性。二、实验环境(实验设备)X86计算机IDE:CodeBlocks 16.01编译器：GUN GCC三、实验原理及内容输入集合已经集合上面的序偶关系，输出关系满足的性质。整体思路为将关系转换成矩阵，根据矩阵判断关系的性质。若矩阵主对角线元素都是1，则满足自反性。若矩阵主对角线元素都是0，则满足反自反性。若矩阵所有元素关于主对角线对称，则满足对称性。若矩阵中出现了关于主对角线对称的元素，则不满足反对称性，否则满足反对称性。若矩阵的传递闭包等于矩阵自己，则矩阵满足传递性。为了能够处理集合中含有字母的情况，程序将所有输入当成字符串来处理，然后将每一个字符与矩阵下标进行键值映射，这样，在序偶关系中，通过字符就可以很轻松的找到对应的下标，从而很轻松将序偶关系用矩阵表示。程序定义的全局变量有：char a200; /保存输入的集合A字符串char R300; /保存输入的序偶R字符串map M; /保存字符与矩阵下标的映射（需#include）int X200200; /关系对应的矩阵int len; /集合A中含有的元素数量int tmp200200; /求传递闭包过程中，用来保存矩阵的传递闭包int tmp1200200; /求传递闭包过程中，用来保存矩阵的N次方。 第一步：将集合中的元素与矩阵下标映射由于集合A中可能含有字母，为了后面能够更加方便的将序偶关系转换成矩阵，第一步先将集合A中所以元素与矩阵下标进行映射，并统计集合A中元素个数。引用STL库文件#include实现键值映射。代码为：int init() int i=0; int l=strlen(a); int j=0; for(i=0;i=a&ai=A&ai=0&ai=9) Mai=j+; return j; 算法复杂度分析：对输入的字符串进行循环遍历，时间复杂度为O（n）。第二步，将关系转换成矩阵 由于上一步中已经将集合中元素与矩阵下标进行了映射,那定位关系中第一元素和第二元素就可以直接用语句MRI,将关系转换成矩阵也就容易多了，XMRi+1MRi+3表示序偶对应的矩阵元素。代码:void solve() int i,j; i=j=0; int l=strlen(R); while(il) if(Ri=) if(find(a,a+strlen(a),Ri+1)=a+strlen(a)|find(a,a+strlen(a),Ri+3)=a+strlen(a) printf(输入有误，关系R中包含非法元素n); exit(0); XMRi+1MRi+3=1; i+=5; else i+; 算法复杂度分析：对输入的序偶字符串进行遍历，时间复杂度是O(n)。用矩阵进行运算，空间复杂度是O(n2)。 第三步：根据矩阵求满足的性质 （1）.自反性 如果矩阵中主对角线元素都是1，那么就满足自反性，否则不满足。判断的时候只要找到第一个对角线元素不是1，就可以断定不满足自反性代码：bool JudgeZiFan() int i; int flag=1; for(i=0;ilen;i+) if(Xii!=1) flag=0; break; if(flag) return true; else return false; 算法复杂度分析：由于只要扫描对角线元素，所以时间复杂度是O(n)。（2）反自反性 如果矩阵中主对角线元素都是0，那么就满足反自反性，否则，就不满足。判断的时候扫描对角线元素，只要出现1就可断定不满足反自反性。代码： bool JudgeFanZiFan() for(int i=0;i0) return false; return true; （3）对称性如果对矩阵中，每一个Xij，都有Mji=1，那么就满足对称性，否则，不满足对称性。若出现Xij=1&Xji=0,就可以断定不满足对称性。判断的时候只要扫描上三角矩阵即可。 bool JudgeDuiCheng() int i,j; for(i=0;ilen;i+) for(j=0;jlen;j+) if(Xij) if(Xji!=1) return false; return true; 算法复杂度分析：扫描上三角矩阵，时间复杂度是O(n2)。（4）反对称性 如果矩阵中出现了关于主对角线对称的元素，那么就不满足反对称性，否则，满足反对称性。判断的时候只要出现了Xij=1&Xji=1就可以断定不满足反对称性。判断的时候也只要扫描上三角矩阵。代码：bool JudgeFanDuiCheng() for(int i=0;ilen;i+) for(int j=i+1;jlen;j+) if(Xij) if(Xji) return false; return true;算法复杂度分析：扫描上三角矩阵，时间复杂度是O(n2)（5）.传递性如果矩阵的传递闭包等于矩阵自己，那么就满足传递性，否则不满足。求矩阵的传递闭包首先定义一个求矩阵的幂的运算，这个地方只要求矩阵和X矩阵相乘就可以。还要定义一个特殊的求矩阵相加的运算，如果相加后矩阵元素大于1 ，就把元素置为1.最后只要比较一下传递闭包是不是与X相等就行了。具体步骤是先定义两个全局数组tmp,和tmp1，首先初始化为X矩阵。tmp1用来累计和矩阵X的乘积，每次都和X相乘一次tmp1的幂就增加1，然后将tmp1与tmp矩阵相加（元素大于1就置成1），如此循环。函数cal（）为tmp1与X相乘，函数combine为tmp1与tmp相加。代码：bool JudgeChuanDi() int i,j; for(i=0;ilen;i+) for(j=0;jlen;j+) tmpij=Xij; tmp1ij=Xij; for(i=2;i=len;i+) cal(); combine(); for(int i=0;ilen;i+) for(int j=0;jlen;j+) if(tmpij!=Xij) return false; return true;求矩阵的幂的运算：首先0将X矩阵拷贝到tmp1200200，然后每次都将tmp1与X相乘代码：void cal() int xtmp200200; int k,p; for(int i=0;ilen;i+) for(int j=0;jlen;j+) int sum=0; for(k=0;klen;k+) sum+=tmp1ik*Xkj; if(sum=0) xtmpij=0; else xtmpij=1; for(int i=0;ilen;i+) for(int j=0;jlen;j+) tmp1ij=xtmpij; 矩阵相加的运算：如果相加后元素大于1，就置为1代码：void combine() for(int i=0;ilen;i+) for(int j=0;jlen;j+) if(tmp1ij|tmpij) tmpij=1; 算法复杂度分析：主函数中，初始化tmp和tmp1时间复杂度是O(n2)。调用循环len-1次，然后每次cal函数进行矩阵相乘的复杂度是O(n3)，combine进行矩阵相加是O(n2)。这个运算步骤的时间复杂度是O(n4)，最后将tmp与X比较的时间复杂度是O(n2)。综上，时间复杂度是O(n4)。空间复杂度分析：由于定义了两个临时数组tmp和tmp1，每一个是O(n2),所以，空间复杂度是O(n2)。主函数进行数据的读入，输出，以及函数的调用Main函数代码：int main() memset(tmp,0,sizeof(tmp); memset(tmp1,0,sizeof(tmp1); memset(a,0,sizeof(a); memset(R,0,sizeof(R); printf(请输入集合A,以逗号隔开各元素,回车结束n); gets(a); len=init(); printf(请输入关系R，格式,.回车结束n); gets(R); solve(); bool ZiFan=JudgeZiFan(); bool DuiCheng=JudgeDuiCheng(); bool ChuanDi=JudgeChuanDi(); bool FanZiFan=JudgeFanZiFan(); bool FanDuiCheng=JudgeFanDuiCheng(); printf(性质为:n); if(ZiFan) printf(自反性n); if(FanZiFan) printf(反自反性n); if(DuiCheng) printf(对称性n); if(FanDuiCheng) printf(反对称性n); if(ChuanDi) printf(传递性n); return 0;程序测试：案例一：课本112页例题5输入集合为1,2,3,4关系为 ,结果正确。案例二：输入集合为 a,b,c输入关系为 ,结果正确。案例三：课本131页例题1输入集合 ： 1,2,3,4输入关系： ,结果正确案例四：输入集合 a,b,c,d输入关系：,结果正确案例五：程序容错性测试结果正确四、实验小结（包括问题和解决方法、心得体会、意见与建议等）1. 个人感觉这个程序的难点是传递性的判断，因为要求传递闭包，涉及到矩阵的乘法和加法，矩阵相乘在循环的时候，循环变