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