devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

头哥实践教育平台-离散数学-关系_头歌实践教学平台离散数学蕴含答案

作者：从前慢现在也慢 | 2024-05-14 05:04:52

赞

踩

头歌实践教学平台离散数学蕴含答案

目录

第1关：求给定集合的对角线关系（diagonal relation）

第2关：关系的合成

第3关：关系的幂运算

第4关：关系的并运算

第5关：转换为关系矩阵

第6关：自反关系的判断

第7关：反自反关系的判断

第8关：对称关系的判断

第9关：非对称关系的判断

第10关：反对称关系的判断

第11关：传递关系的判断

第12关：计算自反闭包

第13关：关系的对称闭包

第14关：关系的传递闭包

第15关：利用Warshall算法求传递闭包

第16关：判断等价关系

第17关：计算等价类

第18关：从划分生成等价关系

第19关：判断半序关系

第20关：判断拟序关系

第21关：判断全序关系 

第22关：关系矩阵的join运算

第23关：关系矩阵的meet运算

第24关：关系矩阵的布尔乘积

第1关：求给定集合的对角线关系（diagonal relation）

这个他也说了，恒等关系，好办的很！

  1. def diagonalRelation(self):
  2.         ########## Begin ##########
  3.         return Relation(self.sets, set([(a, a) for a in self.sets]))
  4.         ########## End ##########

如果 self.sets 是一个包含元素 'A'、'B' 和 'C' 的集合，那么 set([(a, a) for a in self.sets]) 将生成一个包含元组 ('A', 'A')、 ('B', 'B') 和 ('C', 'C') 的集合。

第2关：关系的合成

这好说也就是(x1,y1) (x2,y2)如果y1等于x2那么便可以合成为(x1,y2)

  1. def __mul__(self, other):
  2.         assert self.sets == other.sets
  3.         return Relation(self.sets, set([(x, y1) for x, y in other.rel for x1, y1 in self.rel if y == x1]))

第3关：关系的幂运算

  1. def __pow__(self, power, modulo=None):
  2.         assert power >= -1
  3.         if power == -1: 
  4.             return Relation(self.sets, set([(x, y) for y, x in self.rel]))
  5.         elif power == 0:  
  6.             return self.diagonalRelation()
  7.         return self ** (power - 1) * self

第4关：关系的并运算

这简单加一下就行了！

  1. def __add__(self, other):
  2.         assert self.sets == other.sets
  3.         ########## Begin ##########
  4.         # 将两个关系的关系集合进行并集操作
  5.         new_rel = self.rel.union(other.rel)
  6.         return Relation(self.sets, new_rel)
  7.         #实现两个关系的并运算，重载+运算符，即self+other表示self并other
  8.         #请注意，是Relation对象rel成员的并
  9.         #返回结果为一个Relation对象
  10.         # 请删除pass后编程实现该方法功能
  11.         
  12.         ########## End ##########

第5关：转换为关系矩阵

  1. def toMatrix(self):
  2.         #将序偶集合形式的关系转换为矩阵。
  3.         #为保证矩阵的唯一性，需对self.sets中的元素先排序
  4.         matrix = []
  5.         elems = sorted(list(self.sets))
  6.         line = [0]*len(self.sets)
  7.         for elem in elems:
  8.             ########## Begin ##########
  9.             #请在此处编写程序，实现转换为矩阵的功能
  10.             for x, y in self.rel:
  11.                 if x == elem:
  12.                     line[elems.index(y)] = 1
  13.             matrix.append(line)
  14.             line = [0] * len(self.sets)          
  15.             #请在上面编写程序，不要修改下面的代码
  16.             ########## End ##########
  17.  
  18.         return matrix

第6关：自反关系的判断

  1. def isReflexive(self):
  2.         ########## Begin ##########
  3.         #判断self是否为自反关系，是则返回True，否则返回False
  4.         # 请删除pass后编程实现该方法功能   
  5.         for x in self.sets:
  6.             if (x, x) not in self.rel:
  7.                 return False
  8.         return True    
  9.         
  10.         ########## End ##########

第7关：反自反关系的判断

  1. def isIrreflexive(self):
  2.         ########## Begin ##########
  3.         # 判断self是否为反自反关系，是则返回True，否则返回False
  4.         # 请删除pass后编程实现该方法功能 
  5.         for x in self.sets:
  6.          if (x, x) in self.rel:
  7.             return False
  8.         return True

第8关：对称关系的判断

  1. def isSymmetric(self):
  2.  
  3.         ########## Begin ##########
  4.         # 判断self是否为对称关系，是则返回True，否则返回False
  5.         # 请删除pass后编程实现该方法功能
  6.         for x, y in self.rel:
  7.             if (y, x) not in self.rel:
  8.                 return False
  9.         return True
  10.

第9关：非对称关系的判断

  1. def isAsymmetric(self):
  2.         ########## Begin ##########
  3.         # 判断self是否为非对称关系，是则返回True，否则返回False
  4.         # 请删除pass后编程实现该方法功能
  5.         for x, y in self.rel:
  6.             if (y, x) in self.rel:
  7.                 return False
  8.         return True

第10关：反对称关系的判断

  1. def isAntiSymmetric(self):
  2.         ########## Begin ##########
  3.         # 判断self是否为反对称关系，是则返回True，否则返回False
  4.         # 请删除pass后编程实现该方法功能
  5.         for x, y in self.rel:
  6.             if (y, x) in self.rel and x != y:
  7.                 return False
  8.         return True
  9.

第11关：传递关系的判断

  1. def isTransitive(self):
  2.  
  3.         ########## Begin ##########
  4.         # 判断self是否为传递关系，是则返回True，否则返回False
  5.         # 请删除pass后编程实现该方法功能
  6.         for x, y in self.rel:
  7.             for x1, y1 in self.rel:
  8.                 if x1 == y:
  9.                     if (x, y1) not in self.rel:
  10.                         return False
  11.         return True     
  12.         ########## End ##########

第12关：计算自反闭包

  1. def reflexiveClosure(self):
  2.  
  3.         ########## Begin ##########
  4.         #求self的自反闭包，注意使用前面已经重载过的运算符
  5.         #返回一个Relation对象，为self的自反闭包
  6.         # 请删除pass后编程实现该方法功能
  7.         return self + self.diagonalRelation()
  8.         
  9.         ########## End ##########

第13关：关系的对称闭包

  1. def symmetricClosure(self):
  2.  
  3.         ########## Begin ##########
  4.         # 求self的对称闭包，注意使用前面已经重载过的运算符
  5.         # 返回一个Relation对象，为self的对称闭包
  6.         # 请删除pass后编程实现该方法功能
  7.         return self + self ** -1
  8.         
  9.         ########## End ##########


第14关：关系的传递闭包

  1. def transitiveClosure(self):
  2.         closure = self
  3.         # 求self的传递闭包，注意使用前面已经重载过的运算符
  4.         # 该方法实现的算法：严格按照传递闭包计算公式求传递闭包
  5.         #**********  Begin  **********#
  6.         for i in range(2, len(self.sets) + 1):
  7.             if closure.isTransitive():  # 反正是或运算，可以省此判断，或许还会更快算得
  8.                 break
  9.             closure = closure + self ** i
  10.         #**********  End  **********#
  11.         return closure

第15关：利用Warshall算法求传递闭包

  1.  def __warshall(self, a):
  2.         assert (len(row) == len(a) for row in a)
  3.         n = len(a)
  4.         #请在下面编程实现Roy-Warshall求传递闭包的算法
  5.         #参数a：为一个关系矩阵
  6.         #**********  Begin  **********#
  7.         for r in range(n):
  8.             for c in range(len(a[r])):
  9.                 if a[c][r] == 1:
  10.                     for k in range(n):
  11.                         a[c][k] = a[c][k] | a[r][k]
  12.         #**********  End  **********#
  13.         return a

第16关：判断等价关系

  1. def isEquivalenceRelation(rel):
  2.     #该函数对给定的Relation对象rel，判断其是否为等价关系
  3.     #是则返回True，否则返回False
  4.     #**********  Begin  **********#
  5.     return rel.isReflexive() and rel.isSymmetric() and rel.isTransitive()
  6.  
  7.  
  8.     #**********  End  **********#

第17关：计算等价类

  1. def createPartition(rel):
  2.     #对给定的Relation对象rel，求其决定的rel.sets上的划分
  3.     #如果rel不是等价关系，返回空集
  4.     if not isEquivalenceRelation(rel):
  5.         print("The given relation is not an Equivalence Relation")
  6.         return set([])
  7.     #如rel是等价关系，实现求划分的程序
  8.     partition = set([])
  9.     #**********  Begin  **********#
  10.     partition = set([])
  11.     for elem in rel.sets:  # 给个元素的等价类
  12.         partition.add(frozenset(y for x, y in rel.rel if x == elem))
  13.  
  14.     #**********  End  **********#
  15.     return partition

第18关：从划分生成等价关系

  1. def createEquivalenceRelation(partition, A):
  2.     #对给定的集合A，以及A上的一个划分partition
  3.     #生成由该划分决定的等价关系
  4.     assert functools.reduce(lambda x, y: x.union(y), partition) == A
  5.     #**********  Begin  **********#
  6.     return Relation(A, set((a,b) for part in partition for a in part for b in part))
  7.  
  8.     #**********  End  **********#

第19关：判断半序关系

  1. def isPartialOrder(rel):
  2.     # 该函数对给定的Relation对象rel，判断其是否为半序关系
  3.     #是则返回True，否则返回False。
  4.     #**********  Begin  **********#
  5.     return (rel ** (-1)).rel.intersection(rel.rel) == set((x, x) for x in rel.sets)
  6.  
  7.     #**********  End  **********#

第20关：判断拟序关系

  1. def isQuasiOrder(rel):
  2.     # 该函数对给定的Relation对象rel，判断其是否为拟序关系
  3.     # 是则返回True，否则返回False。
  4.     #**********  Begin  **********#
  5.  
  6.     
  7.     return rel.isIrreflexive() and rel.isAntiSymmetric() and rel.isTransitive()
  8.  
  9.     #**********  End  **********#

第21关：判断全序关系 

  1. def isLinearOrder(rel):
  2.     # 该函数对给定的Relation对象rel，判断其是否为全序关系
  3.     #是则返回True，否则返回False
  4.     if not isPartialOrder(rel):
  5.         return False
  6.     else:
  7.         #**********  Begin  **********#
  8.         return set(x for x, y in rel.rel if x != y) == rel.sets == set(y for x, y in rel.rel if x != y)
  9.  
  10.  
  11.         #**********  End  **********#

第22关：关系矩阵的join运算

  1. def join(rel1, rel2):
  2.     #对给定的关系rel1和rel2
  3.     assert rel1.sets == rel2.sets
  4.     #首先得到二者的矩阵
  5.     M1 = rel1.toMatrix()
  6.     M2 = rel2.toMatrix()
  7.     m = len(M1)
  8.     n = m
  9.     M = []
  10.     #**********  Begin  **********#
  11.     #实现关系矩阵的join运算，结果存于M中
  12.     for r in range(m):
  13.         row = [0] * n
  14.         for c in range(n):
  15.             row[c] = M1[r][c] | M2[r][c]  # 或
  16.         M.append(row)
  17.     return M
  18.     #**********  End  **********#

第23关：关系矩阵的meet运算

  1. def meet(rel1, rel2):
  2.     # 对给定的关系rel1和rel2
  3.     assert rel1.sets == rel2.sets
  4.     # 首先得到二者的矩阵
  5.     M1 = rel1.toMatrix()
  6.     M2 = rel2.toMatrix()
  7.     m = len(M1)
  8.     n = m
  9.     M = []
  10.     #**********  Begin  **********#
  11.     # 实现关系矩阵的meet运算，结果存于M中
  12.     for r in range(m):
  13.         row = [0] * n
  14.         for c in range(n):
  15.             row[c] = M1[r][c] & M2[r][c]  
  16.         M.append(row)
  17.  
  18.  
  19.     #**********  End  **********#
  20.     return M

第24关：关系矩阵的布尔乘积

  1. def booleanProduct(rel1, rel2):
  2.     # 对给定的关系rel1和rel2
  3.     assert rel1.sets == rel2.sets
  4.  
  5.     # 首先得到二者的矩阵
  6.     M1 = rel1.toMatrix()
  7.     M2 = rel2.toMatrix()
  8.  
  9.     m = len(M1)
  10.     n = m
  11.     M = []
  12.     #**********  Begin  **********#
  13.     # 实现关系矩阵的布尔乘积运算，结果存于M中
  14.     for r in range(m):
  15.         row_M1_r = M1[r]  # 准备M1矩阵的行
  16.         row_M_r = [0] * n
  17.         for c in range(n):
  18.             col_M2_c = [M2[r_2][c] for r_2 in range(m)]  #  准备M2矩阵的列
  19.             # 计算r行c列的结果
  20.             row_M_r[c] = 1 if sum([x & y for x, y in zip(row_M1_r, col_M2_c)]) else 0
  21.         M.append(row_M_r)
  22.     #**********  End  **********#
  23.     return M

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/567417
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号