代码收藏家 【头歌educoder】离散数学实训参考-第一章-集合详解与实例分析
目录
1. 集合及其基本运算的实现
第一关：set简单应用
第二关：《仲夏夜之梦》中的回文单词对
第三关：求幂集
第四关：计算n个集合的笛卡尔乘积
2. 自然数系统
第一关：NaturalNumber的输出
第二关：NaturalNumber的加法
第三关：NaturalNumber的乘法
第四关：将NaturalNumber转换为阿拉伯数字
第五关：后继函数
第六关：foldn构建自然数
第七关：另一种foldn表示自然数
自然数系统代码总和
本人没有系统学过离散数学，完成这些实训仅仅是在熟悉python。
1. 集合及其基本运算的实现
第一关：set简单应用
任务简述：读取文本并输出第一次出现的单词
总体思路：读取一个单词后，判断是否已经出现过
相关知识：集合及其方法的使用、文件读取
关卡难度：0.5
def readAndPrintUniqueWords(filename):
infile = open(filename, 'r')
#********** Begin **********#
#请在此区间内编程完成函数代码
s = set() # 空集合
for line in infile.readlines():
if line.strip() not in s: # 如果此行单词未出现过
s.add(line.strip())
print(line.strip())
#请在此区间内编程完成函数代码
#********** End **********#
infile.close()第二关：《仲夏夜之梦》中的回文单词对
任务简述：将所有长度大于等于5，且该单词的字母反序单词也出现在了全部找出 总体思路：单词读出于一列表；集合化；从集合中去除不满足的单词 相关知识：字符串分割与切片、集合及其remove方法、文件读取 关卡难度：1
def shakeSpeare(filename):
#********** Begin **********#
#请在此区间内编程实现函数功能
words = None
with open(filename, 'r') as f:
text = f.read()
words = text.split(' ') # 数组
# 集合化
reverse = set(words)
# 要对words迭代，而不是reverse
for word in words:
# 先判断单词是否在集合里，不然set::remove()可能报错
if word in reverse:
# 字符串切片来表回文
if word[::-1] not in reverse or len(word) < 5:
reverse.remove(word)
#请在此区间内编程实现函数功能
#********** End **********#
return reverse第三关：求幂集
任务简述：返回一个集合的幂集，是一个以frozen集合为元素的集合 总体思路：幂集中的元素分为两类：包含e的、不包含e的(e为原集合中任意元素) 相关知识：frozenset的使用，递归(函数内调用函数自身) 关卡难度：1.5
def powSet(S):
#********** Begin **********#
#请在此区域内编程
# 空集的幂集
if not S:
return {frozenset({})}
else:
# 先求出不含元素elem的幂集
elem = S.pop()
WithoutElem = powSet(S)
# 再求出包含elem的幂集元素
WithElem = set()
for ei in WithoutElem:
# ei 是frozenset()，可使用union，不能add
WithElem.add(ei.union({elem}))
# 包含elem的幂集和不包含elem的幂集之并
return WithoutElem.union(WithElem)
#请在此区域内编程
#********** End **********#
第四关：计算n个集合的笛卡尔乘积
任务简述：求n维笛卡尔乘积，返回n元序偶(元组tuple)为元素的集合 总体思路：求出n-1维，对其修正 相关知识：不定长参数的函数、递归或迭代、元组的使用 关卡难度：1.8
def DescartesProduct(*args):
#********** Begin **********#
#请在此区域编程实现函数功能
n = len(args) # args是一个元组
# 0D
if n == 0:
return {}
# 判断第一个参数的类型，如果是长度为1且其为元组，则修正
if n == 1 and isinstance(args[0], tuple):
args = args[0]
n = len(args)
# 1D，递归终止条件
if n == 1:
return {(arg,) for arg in args[0]}
# nD
a = args[0]
x = DescartesProduct(args[1:]) # (n-1)D
# 如果选出的维度里无元素
if not a:
return x
# 以下从n-1维得到n维
y = set()
for ai in a:
for xi in x:
y.add((ai, ) + xi)
return y
#请在此区域编程实现函数功能
#********** End **********#
2. 自然数系统
第一关：NaturalNumber的输出
任务简述：重载类NaturalNumber的方法__str__(self)，使打印自己想要的结果 总体思路：自然数n表示为None的(n+1)次后继，只需简单迭代 相关知识：类(属性与方法)、类方法重载、迭代 难度：0.3 代码于末尾
第二关：NaturalNumber的加法
任务简述：重载类NaturalNumber的方法__add__(self)，实现加法 总体思路：n+0 = n、n+m`=(n+m)`、`表示后继 相关知识：类(属性与方法)、类方法重载、迭代 难度：0.7 代码于末尾
第三关：NaturalNumber的乘法
任务简述：重载类NaturalNumber的方法__mul__(self)，实现乘法 总体思路：n*0 = 0、n*m` = n*m + n 相关知识：类(属性与方法)、类方法重载、迭代 难度：1 代码于末尾
第四关：将NaturalNumber转换为阿拉伯数字
任务简述：添加方法toNumber(self)，将NaturalNumber对象转换成阿拉伯数字 总体思路： 0 = 0、toNumber(n) = toNumber(n-1) + 1 相关知识：类(属性与方法)、迭代 难度：0.5 代码于末尾
第五关：后继函数
任务简述：添加函数succ(n)，该函数返回以n为前继的NaturalNumber对象 总体思路：简单加1(NaturalNumber中的实例1)、succ(n) = n + 1 相关知识：函数 难度：0.3 代码于末尾
第六关：foldn构建自然数
任务简述：添加函数foldn(init, h, n)，实现自然数m的表示，m = h(foldn(init, h, n-1)) or 0 总体思路：foldn(z, h, 0) = z、foldn(z, h, n) = h(fold(z, h, n-1)) 相关知识：函数名作为参数的函数、迭代 难度：1.8 代码于末尾
第七关：另一种foldn表示自然数
任务简述：添加函数foldn2(init, h)，实现加、乘、幂运算 总体思路：内部还是一个加法式的迭代 相关知识：返回函数名的函数(简单认为)、迭代 难度：2 代码于末尾
自然数系统代码总和
class NaturalNumber(object):
def __init__(self, pre):
self.pre = pre
def __str__(self):
if self.pre is None: # 0是None的后继
return 'Zero'
if self.pre.pre is None: # 1是None的后继的后继
return 'Succ Zero'
# 迭代时注意圆括号
return f'Succ({self.pre.__str__()})'
def __add__(self, other):
# 该方法重载 + 运算
# a + zero = a
# a + succ(b) = succ(a + b)
if other.pre is None:
return self
else:
return NaturalNumber(self + other.pre)
def __mul__(self, other):
# 该方法重载 * 运算
# a * zero = zero
# a * succ(b) = a * b + a
if self.pre is None or other.pre is None:
return NaturalNumber(None)
else:
return self.pre * other + other
def toNumber(self):
# 实现转换为阿拉伯数字
# 0 = 0、toNumber(n) = toNumber(n-1) + 1
if self.pre is None:
return 0
else:
return 1 + self.pre.toNumber()
def succ(n: NaturalNumber):
# 返回一个以对象n为前继的NaturalNumber对象
# succ(n) = n + 1
return n + NaturalNumber(NaturalNumber(None))
def foldn(init: NatualNumber, h, n: int):
# n=0，无需迭代
if n == 0:
return init
# n>0，迭代n-1次
return h(foldn(init, h, n - 1))
def foldn2(init: NaturalNumber, h):
# 下面函数实现foldn函数
def f(n: NaturalNumber):
if n.pre is None:
return init
else:
return h(foldn2(init, h)(n.pre))
return f初笔于2023年4月1日。
![＜urlopen error [Errno 11001] getaddrinfo failed＞的解决、isinstance()函数初略介绍](https://i3.wp.com/img-blog.csdnimg.cn/ef7d1cc438ce48b8aa7a0e08c6724b45.png)
