简介这份离散数学实验资源面向高校计算机及相关专业学生聚焦集合运算的编程实现帮助读者用C/C把交、并、差、补四类运算从理论落到代码。压缩包共2个文件含1个c源码与1个docx实验文档整体约51KB源码可直接编译运行文档则给出实验目的、原理与数组实现思路便于对照理解。实验以数组A、B、C、E表示集合要求输入时检查元素重复并保证A、B为全集E的子集交运算逐一比对取相同元素并运算合并去重差运算从A中删除与B相同的元素补运算则用全集E减去A本质上是一种特殊的集合差。目前已有2152人学习下载适合刚接触离散数学或需要完成课程实验的读者可借此掌握集合运算的算法流程、去重判断与子集校验等基础编程技巧并作为实验报告与代码调试的参考。1. 离散数学实验里的集合运算一个 zip 包能省掉多少重复劳动期末周前两周实验室群里总会冒出同一句话“离散数学实验的集合运算到底交什么”很多人第一反应是去搜“离散数学 集合运算”翻出来的全是定义和文氏图跟要交的代码作业对不上。真正卡住人的不是并交差补的概念而是怎么把课本上的符号变成能跑、能验证、能交差的程序还要处理重复元素、空集、全集这些边界。一个整理好的“大学离散数学实验集合运算.zip”价值就在于把散落在各处的实现、测试用例和实验报告模板收拢到一处解压即用。这篇笔记面向正在做离散数学实验的本科生也面向需要快速搭一个集合运算验证环境的人把 zip 里通常该有什么、怎么自己复现一套、参数和边界怎么设讲清楚。zip 解压之后别急着跑先看目录结构这决定了你是照抄还是真懂。2. 集合运算实验到底在算什么从幂集到对称差的落地拆解2.1 离散数学实验的典型任务清单离散数学实验里的集合运算通常不是让你实现一个Set类就完事。常见的任务清单包括求两个集合的并集、交集、差集、对称差判断子集、真子集、相等关系求幂集求笛卡尔积有时还会要求用位向量表示集合做效率对比。这些任务背后对应的是离散数学教材里集合论那一章的核心定义但实验课要的是可运行、可输出、可验证的结果。我一般会把任务分成三档。第一档是基础运算并交差补用任何语言的内置集合类型都能做重点是输出格式和边界处理。第二档是关系运算子集判断、幂集、笛卡尔积这些用内置类型也能做但幂集和笛卡尔积的规模会随元素个数指数增长需要控制输入规模。第三档是表示法对比比如用位向量实现集合观察在大全集下的性能差异。zip 包里如果只有第一档那它适合交作业如果三档都有那它适合当复习工具。为什么强调任务分档因为很多同学拿到 zip 直接跑main看到输出就以为懂了结果老师一问“对称差的定义是什么、你的实现怎么保证不重复”就答不上来。实验的目的是让你把定义和实现对应起来不是让你当脚本小子。2.2 用 Python 内置 set 跑通最小闭环先给一个能直接抄的最小实现。假设 zip 里没有现成代码或者你想自己重写一遍下面这段覆盖并、交、差、对称差、子集判断和幂集。语言选 Python因为它的set类型语义清晰适合对照数学定义。# set_ops.py # 基础集合运算的最小闭环输入用列表内部转 set 去重 def to_set(lst): 把列表转成集合自动去重。空列表返回空集。 return set(lst) def union(a, b): 并集A ∪ B return a | b def intersection(a, b): 交集A ∩ B return a b def difference(a, b): 差集A - B属于 A 不属于 B return a - b def symmetric_difference(a, b): 对称差A ⊕ B只属于其中一个集合的元素 return a ^ b def is_subset(a, b): 判断 a 是否为 b 的子集 return a b def power_set(s): 幂集返回所有子集组成的集合。 用位掩码枚举元素个数超过 20 时慎用。 elements list(s) n len(elements) result [] for mask in range(1 n): subset {elements[i] for i in range(n) if mask (1 i)} result.append(subset) return result if __name__ __main__: A to_set([1, 2, 3, 4]) B to_set([3, 4, 5, 6]) print(A ∪ B , union(A, B)) print(A ∩ B , intersection(A, B)) print(A - B , difference(A, B)) print(A ⊕ B , symmetric_difference(A, B)) print(A ⊆ B ?, is_subset(A, B)) print(P({1,2,3}) , power_set(to_set([1, 2, 3])))这段代码的逻辑说明to_set负责把输入列表去重这是集合运算的前提因为数学上的集合不允许重复元素。union、intersection、difference、symmetric_difference直接调用 Python 的运算符语义和数学定义一致。is_subset用判断注意在 Python 里对集合是子集关系不是数值比较。power_set用位掩码枚举1 n是 2 的 n 次方每个 mask 的二进制位表示对应元素是否入选。参数说明power_set的输入元素个数 n 决定了输出规模2 的 n 次方个子集。n10 时是 1024 个n20 时是 1048576 个内存和耗时都会明显上升。实验里如果要求幂集输入规模一般控制在 5 以内否则输出会刷屏。symmetric_difference的结果等于(A - B) | (B - A)可以用这个恒等式做交叉验证。跑完这段你应该能看到并集是{1,2,3,4,5,6}交集是{3,4}差集是{1,2}对称差是{1,2,5,6}。如果输出对不上先检查输入有没有重复元素再看运算符有没有写错。2.3 位向量表示什么时候该换实现当全集规模固定且较大时用位向量表示集合会比 Python 的set更省内存运算也更快。位向量的思路是给全集每个元素分配一个二进制位集合用整数表示第 i 位为 1 表示第 i 个元素在集合里。并集是按位或交集是按位与差集是a ~b对称差是按位异或。# bitset_ops.py # 位向量集合运算全集大小固定为 N N 32 # 全集元素个数对应 32 位整数 def make_bitset(indices): 根据元素下标列表构造位向量 bits 0 for i in indices: bits | (1 i) return bits def bitset_union(a, b): return a | b def bitset_intersection(a, b): return a b def bitset_difference(a, b): return a ~b def bitset_symmetric_difference(a, b): return a ^ b def bitset_to_indices(bits): 把位向量还原成元素下标列表 return [i for i in range(N) if bits (1 i)] if __name__ __main__: A make_bitset([0, 1, 2, 3]) B make_bitset([2, 3, 4, 5]) print(A ∪ B , bitset_to_indices(bitset_union(A, B))) print(A ∩ B , bitset_to_indices(bitset_intersection(A, B))) print(A - B , bitset_to_indices(bitset_difference(A, B))) print(A ⊕ B , bitset_to_indices(bitset_symmetric_difference(A, B)))逻辑说明make_bitset把元素下标映射到二进制位1 i生成第 i 位为 1 的整数。四个运算直接对应位运算不需要循环。bitset_to_indices负责把结果还原成人类可读的下标列表。参数说明N是全集大小决定了位向量的位宽。Python 的整数是任意精度所以 N 可以超过 64但超过 64 后位运算的性能优势会减弱。实验里如果全集是 26 个小写字母N26 刚好如果是 100 个元素N100 也能跑但要注意输出还原时的循环开销。位向量适合全集固定、运算频繁的场景不适合元素动态增删的场景。2.4 测试用例怎么设计才不会被老师挑刺集合运算实验的测试用例不能只测“正常情况”。我一般会准备四类用例普通集合、有空集的、有重复元素的、有全集参与的。下面是一个测试脚本的骨架。# test_set_ops.py # 覆盖边界情况的测试用例 from set_ops import to_set, union, intersection, difference, symmetric_difference, is_subset def run_case(name, A, B): print(f--- {name} ---) print(A , A, B , B) print(并集:, union(A, B)) print(交集:, intersection(A, B)) print(差集 A-B:, difference(A, B)) print(对称差:, symmetric_difference(A, B)) print(A ⊆ B ?, is_subset(A, B)) if __name__ __main__: run_case(普通集合, to_set([1, 2, 3]), to_set([3, 4, 5])) run_case(含空集, to_set([]), to_set([1, 2])) run_case(含重复元素, to_set([1, 1, 2, 2]), to_set([2, 3])) run_case(子集关系, to_set([1, 2]), to_set([1, 2, 3])) run_case(相等集合, to_set([1, 2]), to_set([2, 1]))逻辑说明run_case把一组输入和所有运算打包输出方便对比。空集用例检查union和intersection在空集上的行为重复元素用例检查to_set的去重是否生效子集关系用例检查is_subset的方向相等集合用例检查顺序不同但元素相同的集合是否被判为相等。参数说明测试用例的输入规模要小方便肉眼核对。如果要用随机测试可以用random.sample生成不重复元素但要注意随机种子固定否则每次输出不同没法写进实验报告。测试脚本的输出建议重定向到文件方便贴进报告。3. 从 zip 到可交作业的工程目录、依赖和运行入口3.1 解压后先看什么目录结构的判断标准拿到“大学离散数学实验集合运算.zip”解压后第一件事不是双击运行而是看目录。一个结构清晰的实验包通常包含这几个部分源码目录、测试目录、数据目录、报告模板、README。如果解压出来只有一堆.py文件散在根目录那它大概率是个人随手打包的你需要自己补测试和文档。我一般按这个标准判断有没有README说明运行方式有没有requirements.txt或等价的依赖声明测试用例是硬编码在源码里还是单独文件有没有示例输入输出。如果这四项缺两项以上建议不要直接交先自己整理一遍。整理的过程本身就是实验的一部分老师看的是你有没有理解结构。目录结构还影响你后续的调试效率。源码和测试混在一起时改一个函数可能影响多个用例分开之后你可以单独跑测试定位问题更快。如果 zip 里没有测试目录我建议你新建一个tests/把第 2 章的测试脚本放进去源码放src/这样交上去也显得规范。3.2 依赖和运行环境Python 版本与第三方库的取舍集合运算实验对第三方库的依赖应该尽可能少。Python 内置的set已经覆盖了大部分需求不需要装numpy或sympy。如果 zip 里用了sympy的FiniteSet你要评估是否值得保留sympy的集合类型支持符号运算但安装体积大运行慢对于基础实验来说是杀鸡用牛刀。我一般会检查requirements.txt如果只有pytest这类测试框架可以保留如果有numpy、scipy、sympy先问自己实验是否真的需要。不需要就删掉换成内置实现。Python 版本建议 3.8 以上因为 3.8 之后集合运算的语法和性能都比较稳定。如果 zip 里的代码用了 3.10 的match语句而你的环境是 3.8会直接报语法错误这时候要么升级环境要么改写代码。运行入口方面建议统一用python -m src.main或python main.py不要依赖 IDE 的运行按钮。命令行运行能暴露路径问题比如相对导入失败、数据文件找不到。如果 zip 里的入口是 Jupyter Notebook注意 Notebook 的执行顺序会影响结果交作业前建议导出成.py再跑一遍。3.3 把实验报告和代码对齐输出格式的约定实验报告里通常要求贴代码和运行结果。如果代码输出格式随意报告会显得乱。我一般约定每个运算的输出占一行格式为运算名: 结果结果用排序后的列表表示方便核对。比如并集: [1, 2, 3, 4, 5, 6]而不是并集: {1, 2, 3, 4, 5, 6}因为集合的打印顺序在不同 Python 版本里可能不同排序后更稳定。如果实验要求用位向量输出要同时给位向量和元素列表比如A 0b1111 (元素: [0, 1, 2, 3])。这样老师能看到你的表示法和结果之间的对应关系。报告里的截图要清晰命令行输出建议用等宽字体避免排版错乱。还有一个细节空集的输出。Python 里set()打印出来是set()不是{}因为{}是空字典。报告里如果写{}表示空集严格来说是错的。我一般会在代码里把空集输出成∅或[]并在报告里说明约定。这种小地方容易被扣分但改起来只是一行代码。4. 避坑与排查集合运算实验里最容易翻车的五件事4.1 现象并集结果里出现重复元素原因输入没去重解决入口统一转 set这是最常见的翻车。数学上的集合不允许重复元素但如果你用列表做并集[1,1,2] [2,3]会得到[1,1,2,2,3]重复元素还在。原因是你把列表当集合用了。解决办法是在所有运算的入口处统一调用to_set把输入转成集合。如果实验要求保留列表顺序那你要在输出前手动去重但更推荐直接用set。4.2 现象对称差结果和手算对不上原因把对称差当成并集减交集解决用恒等式交叉验证对称差的定义是“只属于其中一个集合的元素”公式是(A - B) | (B - A)也等于(A | B) - (A B)。有些同学直接写A ^ B但输入是列表时^不支持会报TypeError。还有人手算时把对称差算成了并集结果多出了交集部分。解决办法是用两个恒等式交叉验证先算(A - B) | (B - A)再算(A | B) - (A B)两者相等才说明实现正确。4.3 现象幂集输出规模爆炸程序卡死原因输入元素个数没控制解决限制 n 并加提示幂集的规模是 2 的 n 次方。n20 时是 1048576 个子集n25 时是 33554432 个内存直接爆掉。很多同学测试时随手输入 20 个元素程序跑几分钟没反应以为代码错了。解决办法是在power_set入口加判断n 超过 15 就提示用户确认或者直接限制 n 的最大值。实验里幂集的输入规模一般不超过 5超过 10 就要谨慎。4.4 现象子集判断方向搞反原因和混淆解决用具体例子验证方向a b表示 a 是 b 的子集a b表示 a 是 b 的超集。有些同学写is_subset(a, b)时返回a b结果方向反了。比如{1,2} {1,2,3}是 True但{1,2} {1,2,3}是 False。解决办法是写一个最小用例is_subset({1}, {1,2})应该返回 Trueis_subset({1,2}, {1})应该返回 False。跑一遍就知道方向对不对。4.5 现象位向量运算结果还原成元素时下标偏移原因位下标从 0 开始还是从 1 开始没统一解决全局约定从 0 开始位向量表示里第 0 位对应第一个元素还是第 1 位对应第一个元素必须全局统一。如果make_bitset用1 i而bitset_to_indices用range(1, N1)结果就会偏移一位。解决办法是在文件开头写注释约定“位下标从 0 开始”所有函数都遵守。测试时用make_bitset([0])应该得到1bitset_to_indices(1)应该得到[0]跑通这个最小用例再测复杂情况。5. 进阶技巧用属性测试和性能对比把实验做出区分度基础实验做完如果想拿高分或者真正理解集合运算可以加两个进阶内容属性测试和性能对比。属性测试是指不写具体用例而是写“对所有集合都成立的性质”比如并集交换律A | B B | A、交集幂等律A A A、对称差自反律A ^ A set()。用hypothesis库可以自动生成随机集合来验证这些性质比手写用例覆盖更广。# test_properties.py # 用 hypothesis 做集合运算的属性测试 from hypothesis import given, strategies as st from set_ops import union, intersection, symmetric_difference given(st.sets(st.integers()), st.sets(st.integers())) def test_union_commutative(a, b): assert union(a, b) union(b, a) given(st.sets(st.integers())) def test_intersection_idempotent(a): assert intersection(a, a) a given(st.sets(st.integers())) def test_symmetric_difference_self(a): assert symmetric_difference(a, a) set()逻辑说明given装饰器让 hypothesis 自动生成随机集合st.sets(st.integers())表示元素为整数的集合。每个测试函数断言一条性质失败时 hypothesis 会给出反例。参数说明hypothesis 默认生成 100 个用例可以通过settings(max_examples1000)增加。注意st.sets生成的集合可能很大如果测试超时可以加max_size限制。性能对比是另一个加分项。用timeit对比set和位向量在相同运算下的耗时画一个简单的柱状图或表格。全集大小从 10 到 1000分别测并集和交集。你会发现小规模时set更快大规模时位向量优势明显。这个结论写进报告比只贴代码有说服力。# bench.py # 对比 set 和位向量的并集性能 import timeit N 1000 A_set set(range(0, N, 2)) B_set set(range(0, N, 3)) A_bits sum(1 i for i in range(0, N, 2)) B_bits sum(1 i for i in range(0, N, 3)) t_set timeit.timeit(lambda: A_set | B_set, number1000) t_bits timeit.timeit(lambda: A_bits | B_bits, number1000) print(fset 并集: {t_set:.6f}s) print(f位向量并集: {t_bits:.6f}s)逻辑说明timeit.timeit重复执行 1000 次取总时间lambda里是要测的表达式。参数说明N是全集大小number是重复次数。注意位向量的构造用sum(1 i ...)在 N1000 时生成一个 1000 位的整数Python 能处理但构造本身有开销所以对比的是运算阶段。跑出来如果位向量更快说明位运算的常数优势如果更慢可能是整数位宽太大导致。我自己的习惯是基础实验用set保证正确性进阶对比用位向量展示理解深度。报告里把属性测试的通过截图和性能对比表格放上去区分度就出来了。做实验最怕的是只跑通一个用例就交老师一眼就能看出你没测边界。希望帮到你。本文还有配套的精品资源点击获取