信息學(xué)競賽中問題求解常見題分析三

1、信息學(xué)競賽中問題求解常見題分析（三）容斥問題在 1 9 世紀(jì)末，德國數(shù)學(xué)家康托系統(tǒng)地描繪了一個能夠為全部數(shù)學(xué)提供基礎(chǔ)的通用數(shù)學(xué)框架，他創(chuàng)立的這個學(xué)科一直是數(shù)學(xué)發(fā)展的根植地，這個學(xué)科就叫做集合論。它的概念與方法已經(jīng)有效地滲透到所有的現(xiàn)代數(shù)學(xué)?？梢哉J(rèn)為，現(xiàn)代數(shù)學(xué)的幾乎所有內(nèi)容都是在“集合”中、生長的。集合中的容斥問題在信息學(xué)競賽一、知識點求解中也經(jīng)常出現(xiàn)。集合與元素：把一類事物的全體放在一起就形成一個集夸。每個集合總是由一些成員組成的，集合的這些成員，叫做這個集合的元素。如：集合A=0，1，2，3，9，其中 0，1，2， 9 為 A 的元素。并集：由所有屬于集合 A 或集合 B 的元素所組成的集合

2、，叫做 A，B 的并集，記作 Au B，記號“u”讀作“并”。Au B 讀作。A 并 B，用圖表示為圖中陰影部分表示集合 A，B 的并集 AuB。例：已知 6 的約數(shù)集合為A=1，2，3，6，10 的約數(shù)集合 B=1，2，5，l0，則 Au B=1，2，3，5，6，10。交集：A，B 兩個集合公共的元素，也就是那些既屬于 A，又屬于 B 的元素，它們組成的集合叫做 A 和 B 的交集，記作“An B”，讀作“A 交 B”，如圖陰影表示：例：已知 6 的約數(shù)集合 A=1，2，3，6，1 0 的約數(shù)集合 B=1， 2，5，1 0，則 An B=1，2)。容斥原理(包含與排除原理)：(用|A|表示集

3、合 A 中元素的個數(shù)，如A=1，2，3)，則|A|=3)原理一：給定兩個集合 A 和 B，要計算Au B 中元素的個數(shù)，可以分成兩步進(jìn)行：第一步：先求出 lA|+| B|(或者說把 AB 的一切元素都“包含”進(jìn)來，加在一起)：第二步：減去口 An B 口(即“排除”加了兩次的元素)總結(jié)為公式：|Au B=|A|+|B|-|An B|口原理二：給定三個集合 A，B，C。要計算Au BUC 中元素的個數(shù)，可以分三步進(jìn)行：第一步：先求| A|+|B|+|C |；第二步：減去口An B 口，口 BnC 口，口 Cn A 口；第三步：再加上口 An BnC 口。即有以下公式：二、解題關(guān)鍵|Au BuC|

4、=|A|+|B|+|C| -l An B|-|BnC|-|CnA|+|An BnC|遇到集合問題，首先要弄清：集合里的元素是什么?集合新名詞新概念多，如集合、元素，有限集無限集、列舉法、描述法、子集、真子集、空集、非空集合、全集，補集交集、并集等。新關(guān)系新符號多，如屬于、不屬于、包含、包含于、真包含、真包含于、相等不相等、相交、相并互補等，這些新概念新關(guān)系，多而抽象。在這千頭萬緒中，應(yīng)該抓住“元素”這個關(guān)鍵，因為集合是由元素確定的，“子、全、補、交并、空”等集合也都是通過元素來定義的。集合中元素的特征即 “確定性”、“互異性”、“無序性”，也就是元素的性質(zhì)。集合的分類(有限集與無限集)與表示方

5、法(列舉法與描述法)也是通過元素來刻畫的。元素是集合的基本內(nèi)核，研究集合，首先就要確定集合里的元素是什么。三、例題分析例 1求不超過 20 的正整數(shù)中是 2 的倍數(shù)或 3 的倍數(shù)的數(shù)共有多少個。分析：設(shè)A=20 以內(nèi) 2 的倍數(shù)，B=20 以內(nèi) 3 的倍數(shù)，顯然，要求計算 2 或 3 的倍數(shù)個數(shù)，即求口 Au B 口解 1：A=2，4，6，20，共有 10 個元素，即|A|=10,B=3，6，9，18)，共有 6 個元素，即| B|=6A n B=(既是 2 的倍數(shù)又是 3 的倍數(shù))=6，l 2，18，共有 3 個元素，即|An B|=3所以|Au B |=|A|+| B|-|An B|=10

6、+6-3=l 3，即Au B 中共有 1 3 個元素。解 2：本題可直觀地用圖示法解答如圖，其中，圓 A 中放的是不超過 20 的正整數(shù)中 2的倍數(shù)的全體；圓 B 中放的是不超過 20 的正整數(shù)中 3的倍數(shù)的全體，其中陰 A 影部分的數(shù) 6，12，18 是既是 2 的倍數(shù)又是 3 的倍數(shù)的數(shù)(即An B 中的數(shù))，只要數(shù)一數(shù)集合Au B 中的數(shù)的個數(shù)即可。例 2 某班統(tǒng)計成績，數(shù)學(xué)得 90 分上的有 25 人語文得 90 分以卜的有 21 人，兩科中至少有一科在 90 分以上的有 38 人。問兩科都在 90 分以上的有多少人？解：設(shè) A=數(shù)學(xué)成績 90 分以上的學(xué)生B=語文成績 90 分以上的

7、學(xué)生那么，集合A u B 表示兩科中至少有一科在 90 分以上的學(xué)生，由題意知，口 |A|=2 5，|B|=2l，|AuB|=38現(xiàn)要求兩科均在 90 分以上的學(xué)生人數(shù)，即求口 |AnB|，由容斥原理得口 |An B |=|A|+| B| Au B |=25+21-38=8點評：解決本題首先要根據(jù)題意，設(shè)出集合A，B，并且會表示AuB，A n B，再利用容斥原理求解。例 3某班同學(xué)中有 39 人打籃球，37 人跑步，25 人既打籃球又跑步：問令班參加籃球、跑步這兩項體育活動的總?cè)藬?shù)是多少?解：設(shè) A=打籃球的同學(xué)：B=跑步的同學(xué)Au B=(參加打籃球或跑步的同學(xué))則 An B=既打籃球又跑步的

8、同學(xué)應(yīng)用容斥原理| Au B|=A|+|lB|+|C|-|AnB|=39+37-25=5l(人)例 4 某年級的課外學(xué)科小組分為數(shù)學(xué)、語文、外語_三個小組，參加數(shù)學(xué)小組的有 23人，參加語文小組的有 27 人參加外語小組的有 18 人；同時參加數(shù)學(xué)、語文兩個小組的有 4 人，同時參加數(shù)學(xué)、外語小組的有 7 人，同時參加語文、外語小組的有 5 人；三個小組都參加的有 2 人。問：這個年級參加課外學(xué)科小組的共有多少人?解 l：設(shè) A=數(shù)學(xué)小組的同學(xué)，B=語文小組的同學(xué)，C=外語小組的同學(xué)，An B=數(shù)學(xué)、語文小組的同學(xué)，AnC=參加數(shù)學(xué)、外語小組的同學(xué)，BnC=參加語文、外語小組的同學(xué)，An Bn

9、C=三個小組都參加的同學(xué)由題意知：|A|=23，|B|=27，|C|=18口 |AnB|=4，|AA n C|=7，|B nC|=5，|An BnC|=2根據(jù)容斥原理：得：口 |Au BuCl=|A|+l B|+fC|-|AnB|-|An C|-lBn C|+|AnBnC|=2 3+27+18-(4+5+7)+2=54(人)解 2：利用圖示法逐個填寫各區(qū)域所表示的集合的元素的個數(shù)，然后求出最后結(jié)果設(shè) A，B，c 分別表示參加數(shù)學(xué)，語文、外語小組的同學(xué)的集合，其圖分割成七個互不相交的區(qū)域，區(qū)域 VII(即 A n Bnc)表示三個小組都參加的同學(xué)的集合，由題意，應(yīng)填 2。區(qū)域表示僅參加數(shù)學(xué)與語丈

10、小組的同學(xué)的集合，其人數(shù)為 4-2=2(人)。區(qū)域VI 表示僅參加數(shù)學(xué)與外語小組的同學(xué)的集合，其人數(shù)為 7-2=5(人)區(qū)域 V 表示僅參加語文、外語小組的同學(xué)的集合，其人數(shù)為 5-2：3(人)。區(qū)域 I 表示只參加數(shù)學(xué)小組的同學(xué)的集合，其人數(shù)為 23-2-2-5=14(人)。同理，可把區(qū)域 II、I所表示的集合的人數(shù)逐個算出，分別填入相應(yīng)的區(qū)域內(nèi)，則參加課外小組的人數(shù)為：14+20+8+2+5+3+2=54(人)點評：解法 2 簡單直觀，不易出錯。由于各個區(qū)域所表示的集合的元素個數(shù)都計算出來了，因此提供了較多的信息，易于回答各種方式的提問。例 5 學(xué)校教導(dǎo)處對 100 名同學(xué)，結(jié)果有 58

11、人喜歡看球賽，有 38 人喜歡看戲劇，有 52 人喜歡看6 人，既喜歡看。另外還知道，既喜歡看球賽又喜歡看戲劇(但不喜歡看)的有又喜歡看戲劇(但不喜歡看球賽)的有 4 人，三種都喜歡的有 12 人。問有多少同學(xué)只喜歡看?有多少同學(xué)既喜歡看球賽又喜歡看定每人至少喜歡一項)解法 1：畫三個圓圈使它們兩兩相交，彼此分成 7 部分(但不喜歡看戲劇)?(假(如圖)，這三個圓圈分別表示三種不同的同學(xué)的集合，由于三種都喜歡的有 12 人，把 1 2 填在三個圓圈的公共部分內(nèi)(圖中陰影部分)，其他 6 部分填上題目中所給出的不同的同學(xué)的人數(shù)(注意，有的部分的人數(shù)要經(jīng)過簡單的計算)，其中設(shè)既喜歡看又喜歡看球賽的人數(shù)為 x，這樣，全班同學(xué)人數(shù)就是這 7 部分人數(shù)的和，即 16+4+6+(40-x)+(36-x)+12=100解得 x=14只喜歡看的人數(shù)為 36-14=22B=喜歡看戲劇的人，c=喜歡看的人，依題目的條件有|Au B u c|=100，| A nB|=6+12=1 8(這里加 12 是因為三種都喜歡的人當(dāng)然喜歡其中的兩種)，|B n c|=4