一、題目要求：

內容：

        求取集合A上的整除關系R對應的蓋住關系，並判定偏序集<A，R>是否為格，若是格，判斷其是否為有補格。

要求：

        集合A可以是用戶任意給定的正整數集合。

二、實驗原理以及內容：

實驗所使用的數據結構、存儲結構：列表及其sort排序，元祖(a,b)表示a|b(a整除b)以及map映射

實驗中函數：

def judge_div(a,b)  #判斷整除關系 1、0表示是否滿足整除關系

def judge_COV(A) #傳入集合A，先判斷符合整除關系的R集合，再判斷出蓋住關系，以列表的形式返回蓋住關系（其中調用judge_div(a,b)函數來判斷R集合）

def union(a,b,A) #A集合中a、b元素的並運算(得兩者上確界)

def intersect(a,b,A) #A集合中a，b元素的交運算(得兩者的下確界)，其中調用judge_div(a,b)函數向下遍歷A中的元素，尋找最小下界（存在,則返回上下確界,不存在返回0）

def judge_lattice(A) #判斷是否是格以及是不是補格,根據格的定義，調用union和intersect函數去判斷。
def print_tuple(R) #格式化輸出集合

實驗中數據傳遞關系：輸入集合A,元素必須是正整數的集合,逗號隔開相鄰元素，調用一系列函數處理即可

實驗思路與原理：

• 判斷符合整除關系的R集合和蓋住關系：逐一遍歷A中每個元素，調用judge_div函數判斷是否符合整除關系，是->以元祖的形式放入R中。R計算完後，再對R中的每一個序偶（元祖）進行判斷:在R集合中，且無第三者逐一遍歷是否符合，一旦出現<x,y><y,z>，flag=0，退出循環，若flag經歷遍歷後仍然為1，放入COVA的序偶中。
• 判斷格：從定義出發(任意兩個元素都會有上確界和下確界)，調用union和intersect函數求出上下確界即可（存在，則返回上下確界，不存在返回0）
• 判斷有補格：在是格的前提下，對於每一個元素逐一遍歷能否找到A中的元素能成為它的補元(並運算後上確界1和交運算後下確界0)即可，（只要找到一個補元即可退出對該元素的討論，當只有A中每一個元素都有至少一個補元，此時方可判斷其為有補格->一旦遍歷到一個找不到補元的元素，直接退出循環，flag2=0，不是補元）

時間復雜度：O（n²）

三、源代碼：

#蓋住關系的求取及格的判定.py
def judge_div(a,b):
'''a整除b->b除以a為整數'''
max=(a if a>b else b)
min=a+b-max
if max%min==0:#整除
return 1
else:
return 0
def judge_COV(A):#傳入集合A，判斷符合整除關系的R集合，再判斷出蓋住關系
R=[]#存儲R集合
for i in A:
for j in A[A.index(i):]:
if judge_div(i,j):
R.append(tuple([i,j]))
#得出R關系的集合，下求COV A
COVA=[]
for x in R:
if x[1]-x[0]==1:
COVA.append(x)
elif (x[1]-x[0])>1: #注意排除自反的<1,1>等元素
flag=1 #假設符合
template=A[A.index(x[0])+1:A.index(x[1])]
for y in template:
if R.count(tuple([x[0],y]))==1 and R.count(tuple([y,x[1]]))==1: #中間無其他元素才能滿足蓋住關系
flag=0
break
if flag==1:
COVA.append(x)
return COVA
'''格式化輸出偏序集'''
def print_tuple(R):
print("{",end="")
for i in R:
print("<{0},{1}>".format(i[0],i[1]),end="")
print("}")
'''兩個元素的並運算->得到兩個元素的上確界'''
def union(a,b,A):
max=(a if a>b else b)
for i in A[A.index(max):]:
if judge_div(i,a) ==1 and judge_div(i,b)==1:
return i
return 0#若為0表示A中的a，b元素的上確界不在A中
'''兩個元素的交運算->得到兩個元素的下確界'''
def intersect(a,b,A):
min=(a if a<b else b)
for i in A[A.index(min)::-1]:
if judge_div(b,i)==1 and judge_div(a,i)==1:
return i
return 0
'''判斷是否是格以及是不是補格'''
def judge_lattice(A):
#下面進行格相關的判斷(任意兩個元素均有其上確界和下確界)
flag1=1#格
flag2=1
f=1
for x in A:
if flag1==0:
break
else:
for y in A[A.index(x)+1:]:
flag1=bool(union(x,y,A) and intersect(x,y,A))#注意and的返回值！！！！
if flag1==0:
break
for m in A:
if f==1:
f=0
for n in A:
if intersect(m,n,A)==A[0] and union(m,n,A)==A[-1]:
f=1
break
else:
flag2=0
if flag1==0:
print("<A,|>不是一個格")
elif flag2==0:
print("<A,|>是一個格,但並非有補格")
else:
print("<A,|>是一個格，且為有補格")
if __name__=="__main__":
#輸入集合A,集合A可以是用戶任意給定的正整數集合。
tempstr=input("輸入集合A,元素必須是正整數的集合,逗號隔開相鄰元素")
Alist=tempstr.split(",")
A=list(map(int,Alist))
A.sort(reverse=False)#升序排序 例如：1 2 4 8等
COVA=judge_COV(A)
print("A對應的蓋住關系為:",end="")
print_tuple(COVA)
judge_lattice(A)

2022.6.29寫在最後，

有一個樣例沒有考慮，讀者可以自行修改，此樣例見下。