离散数学实验三
萌到你眼炸
933次浏览
2021年01月30日 01:06
最佳经验
本文由作者推荐
给老师的信-梦中的额吉简谱
实
验
报
告
（
2014
/ 2015
学年
第
一
学期）
课程名称
离散数学
实验名称
偏序关系中盖住关系的求取及格论中有补格
的判定
实验时间
指导单位
指导教师
2014
年
11
月
28
日
南京邮电大学
罗卫兰
学生姓名
沈一州
班级学号
B12040920
NIIT
（软嵌）
学院
(
系
)
计算机软件学院
专
业
实
验
报
告
实验名称
偏序关系中盖住关系的求取及格
论中有补格的判定
实验类型
Windows+V
C
实验学时
4
实验时间
指导教师
罗卫兰
11.28
一、
实验目的和要求
内容：
编程实现整除关系这一偏序关系上所有盖住关系的求取，并判定对应偏
序集是否为格。
要求：
对任意给定正整数，利用整除关 系求所有由其因子构成的集合所构成的
格，判断其是否为有补格。
二、
实验环境
(
实验设备
)
硬件：
CPU
：
3.0Ghz
内存：
1.00GB
软件：
操作系统：
Windows XP SP3
编程软件：
Visual C++ 6.0
- 1 -
三、
实验原理及内容
总体思想：
这次题目要求是根据整除关系建立偏 序关系，集合由一个正整数的因子所构成，所
以该偏序集中的最大下界为
1
，最小上界 为该正整数，所以该偏序集是一个格。又因为
是整除关系，则“交”即为求两者的最大公约数，
“并”即为求两者的最小公倍数，故
而满足分配律，因此这个偏序集是个分配格。判断这个集合是否为有 补格，根据定理可
以先判断元素数是否为
2
的倍数，不过编程起来更加复杂，于是我就 采用逐个求补元的
方法。如果对于某个元素找完了所有的元素也没找到补元，则不满足有补性，否则就为
有补格，又因为是分配格，所以也是布尔格。
对于所有可能的偏序集，有一个特例即
{1}
，这个偏序集最小上界等于最大下界等
于
1
，
1的补元是他本身。他也是个有补格，要特殊考虑。
核心代码：
1
、先编写了两个函数分别求最小公约数和最大公倍数：
//
辗转相除法求最大公约数
int GYS(int a,int b){
int temp;
if(a
temp=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++;
}
- 2 -