目录
1. 集合及其基本运算的实现
第一关:set简单应用
第二关:《仲夏夜之梦》中的回文单词对
第三关:求幂集
第四关:计算n个集合的笛卡尔乘积
2. 自然数系统
第一关:NaturalNumber的输出
第二关:NaturalNumber的加法
第三关:NaturalNumber的乘法
第四关:将NaturalNumber转换为阿拉伯数字
第五关:后继函数
第六关:foldn构建自然数
第七关:另一种foldn表示自然数
自然数系统代码总和
本人没有系统学过离散数学,完成这些实训仅仅是在熟悉python。
1. 集合及其基本运算的实现
第一关:set简单应用
任务简述:读取文本并输出第一次出现的单词
总体思路:读取一个单词后,判断是否已经出现过
相关知识:集合及其方法的使用、文件读取
关卡难度:0.5文章来源:https://www.toymoban.com/news/detail-697011.html
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日。文章来源地址https://www.toymoban.com/news/detail-697011.html
到了这里,关于【头歌educoder】离散数学实训参考-第一章-集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!