离散数学实验三

实验报告（2014/2015学年第一学期）课程名称离散数学实验名称偏序关系中盖住关系的求取及格论中有补格的判定实验时间2014年11月28日指导单位南京邮电大学指导教师罗卫兰学生姓名沈一州班级学号B12040920学院(系)计算机软件学院专业NIIT（软嵌）-1-实验报告实验名称偏序关系中盖住关系的求取及格论中有补格的判定指导教师罗卫兰实验类型Windows+VC实验学时4实验时间11.28一、实验目的和要求内容：编程实现整除关系这一偏序关系上所有盖住关系的求取，并判定对应偏序集是否为格。要求：对任意给定正整数，利用整除关系求所有由其因子构成的集合所构成的格，判断其是否为有补格。二、实验环境(实验设备)硬件：CPU：3.0Ghz内存：1.00GB软件：操作系统：WindowsXPSP3编程软件：VisualC++6.0-2-三、实验原理及内容总体思想：这次题目要求是根据整除关系建立偏序关系，集合由一个正整数的因子所构成，所以该偏序集中的最大下界为1，最小上界为该正整数，所以该偏序集是一个格。又因为是整除关系，则“交”即为求两者的最大公约数，“并”即为求两者的最小公倍数，故而满足分配律，因此这个偏序集是个分配格。判断这个集合是否为有补格，根据定理可以先判断元素数是否为2的倍数，不过编程起来更加复杂，于是我就采用逐个求补元的方法。如果对于某个元素找完了所有的元素也没找到补元，则不满足有补性，否则就为有补格，又因为是分配格，所以也是布尔格。对于所有可能的偏序集，有一个特例即{1}，这个偏序集最小上界等于最大下界等于1，1的补元是他本身。他也是个有补格，要特殊考虑。核心代码：1、先编写了两个函数分别求最小公约数和最大公倍数：//辗转相除法求最大公约数intGYS(inta,intb){inttemp;if(ab){temp=a;a=b;b=temp;}while(temp=a%b){a=b;b=temp;}returnb;}//根据最大公约数求最小公倍数intGBS(inta,intb){returna*b/GYS(a,b);}2、求给定正整数的因子：a[0]=1;//第一个元素肯定是1j=n=1;//j代表数组a[]的下标，n标记元素个数for(i=2;i=m/2;i++){if(m%i==0){//若是能被给定正整数整除，即加入数组a[]a[j++]=i;n++;}}if(m!=1){//最后把该正整数加入数组a[]，1不重复加入a[j]=m;n++;}-3-3、判断是否为有补格：flag=0;//1则为找到反例for(i=0;in;i++){for(j=n-1;j=0;j--){if(GBS(a[i],a[j])==m&&GYS(a[i],a[j])==1){couta[i]有补元素a[j]。\n;break;}if(j==0){flag=1;}}}if(!flag){cout因为所有成员都有补元素，所以这是一个有补格。\n;}4、判断是否为分配格：flag=0;//已知肯定是分配格，这里只是进一步确信，flag标记是否有反例for(i=0;in;i++){for(j=0;jn&&j!=i;j++){for(k=0;kn&&k!=j&&j!=i;k++){if(GYS(a[i],GBS(a[j],a[k]))!=GBS(GYS(a[i],a[j]),GYS(a[i],a[k]))){flag=1;cout因为a[i]∧(a[j]∨a[k])!=(a[i]∧a[j])∨(a[i]∧a[k]),所以这不是一个布尔格。\n;//验证a∧(b∨c)==(a∧b)∨(a∧c)break;}if(GBS(a[i],GYS(a[j],a[k]))!=GYS(GBS(a[i],a[j]),GBS(a[i],a[k]))){flag=1;cout因为a[i]∨(a[j]∧a[k])!=(a[i]∨a[j])∧(a[i]∨a[k]),所以这不是一个布尔格。\n;//验证a∨(b∧c)==(a∨b)∧(a∨c)break;}}if(flag)break;}if(flag)break;}if(!flag)cout因为所有成员都满足分配性，所以这是一个分配格。\n;-4-四、运行结果：首先是输入界面：然后输入24：然后询问是否再次输入：这次输入99：特殊情况，若输入0或者负数：此时会一直提示输入错误直到输入成功。若输入1：若输入非Y，则退出程序：-5-实验报告五、实验小结这次题目要求是根据整除关系建立偏序关系，集合由一个正整数的因子所构成，所以该偏序集中的最大下界为1，最小上界为该正整数，所以该偏序集是一个格。又因为是整除关系，则“交”即为求两者的最大公约数，“并”即为求两者的最小公倍数，故而满足分配律，因此这个偏序集是个分配格。判断这个集合是否为有补格，根据定理可以先判断元素数是否为2的倍数，不过编程起来更加复杂，于是我就采用逐个求补元的方法。如果对于某个元素找完了所有的元素也没找到补元，则不满足有补性，否则就为有补格，又因为是分配格，所以也是布尔格。通过这次实验，加深了我对格的相关知识的理解，也提高了我动手编程的能力。五、指导教师评语成绩批阅人日期