目录
本人没有系统学过离散数学，完成这些实训仅仅是在熟悉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迭代，而不是reversefor 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日。
来源地址：https://blog.csdn.net/wander_alice/article/details/129893836
