


























容斥原理是计算集合并集大小的基本工具。简单说,就是:
先加上各个集合的大小,再减去两两交集的大小,再加回三三交集的大小……依此类推,避免重复计数。
对于两个集合 ( A ) 和 ( B ):
[
|A \cup B| = |A| + |B| - |A \cap B|
]
图示理解:
A B
( ∩ )
交集被数了两次,需减去一次。
[
|A \cup B \cup C| = |A| + |B| + |C|
题中:
用容斥原理:
[
|A \cup B| = 20 + 14 - 2 = 32
]
这样就把重复计算的两个数(35 和 70)只算了一次。
如果你想看更一般的 ( n ) 个集合的公式或推广,我也可以展开讲。
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。