????????????????第17課????????容斥原理

一、課程導(dǎo)入

????????本節(jié)課你將會(huì)學(xué)到：如何解決容斥原理相關(guān)問題？如何讓Scratch實(shí)現(xiàn)關(guān)于容斥原理問題的求解過程？用Scratch編寫容斥原理的萬能方法是怎樣的？

二、知識(shí)儲(chǔ)備

????????1、容斥原理又叫重疊問題，是研究集合元素個(gè)數(shù)的一個(gè)定理。2個(gè)對(duì)象的容斥原理：元素的個(gè)數(shù)=集合A中的元素個(gè)數(shù)+集合B中的元素個(gè)數(shù)-集合A、B都包含的元素個(gè)數(shù)（元素的個(gè)數(shù)=A+B-A∩B）；3個(gè)對(duì)象的容斥原理：元素的個(gè)數(shù)=集合A中的元素個(gè)數(shù)+集合B中的元素個(gè)數(shù)+集合C中的元素個(gè)數(shù)-集合A、B都包含的元素個(gè)數(shù)-集合A、C都包含的元素個(gè)數(shù)-集合B、C都包含的元素個(gè)數(shù)-集合A、B、C都包含的元素個(gè)數(shù)（元素的個(gè)數(shù)=A+B+C-A∩B-A∩C-B∩C+A∩B∩C）。

????????2、要區(qū)分開“最多”“至少”“有幾個(gè)”這類的詞?！白疃唷笔撬袑?duì)象的總和，“至少”是“總數(shù)”減去“最多”，其余情況都是“有幾個(gè)”。

三、例題講解

????????1、已知一家小賣部某天單獨(dú)賣出去15支鉛筆，又單獨(dú)賣出去10支鋼筆，其中有2次是筆同時(shí)賣出。問：（1）如果小賣部每次賣筆都是1支1支賣出（除了有2次是兩種筆同時(shí)賣出），那么小賣部這天賣出去多少次筆？（2）如果小賣部沒有新進(jìn)的筆，且該天最初只有30支筆，那么到小賣部當(dāng)天下班后，小賣部里還剩下多少支筆？

????????我們先來看第（1）小問。通過讀題我們發(fā)現(xiàn)，這題是已知小賣部一天內(nèi)賣出若干支鉛筆和鋼筆的數(shù)量，包括單獨(dú)賣出去鉛筆、鋼筆、鉛筆同是賣出的數(shù)量，求筆賣出的次數(shù)。那么鉛筆、鋼筆賣出的支數(shù)就是我們要研究的對(duì)象?！爸А焙汀按巍辈皇峭愒~，這可怎么辦呢？再仔細(xì)讀一下題目，題目中提到了“兩種筆同時(shí)賣出”，那顯然這兩種筆就是鉛筆和鋼筆。我們把圖畫出來（如圖1所示），左邊的15是鉛筆的支

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖1

數(shù)，右邊的10是鋼筆的支數(shù)，兩個(gè)圓圈相交處的2表示鉛筆和鋼筆同時(shí)賣出的次數(shù)。問法是“每次每支筆都是1支1支賣出?！蹦敲催@樣該問題就轉(zhuǎn)化成了實(shí)際賣出去多少次的問題，如果把每次賣出去1支筆看成集合中的1個(gè)元素。那么套用公式A+B-A∩B即可求出問題：15+10-2=23（次）。答：小賣部這天賣出去23次筆。

? ? ? ? 我們?cè)賮砜吹冢?）小問。通過讀題我們發(fā)現(xiàn)，這里給出了新的條件：沒有新進(jìn)的筆、最初只有30支筆，其他地方均沒有改變。而此時(shí)我們知道了賣出去的部分，那沒賣出去就是我們要求剩下的。為了方便，我們此時(shí)可以把23次照抄下來。不妨我們?cè)佼嬕幌聢D，把30支筆

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖2

看成一個(gè)全集，A∪B為賣出去的筆的次數(shù)，那么用全集“減去”并集得”剩下”的補(bǔ)集，就是我們要求的：30-（15+10-2）=3（支）。答：到小賣部剛下班后，此時(shí)還剩3支筆。

? ? ? ? 2、在1——80中，既不是6的倍數(shù)又不是5的倍數(shù)的自然數(shù)有多少個(gè)？

????????這道題看起來非常簡(jiǎn)單，但如果按傳統(tǒng)的方法求，不但計(jì)算量大，而且還容易出錯(cuò)。那么我們不妨找規(guī)律：任何一個(gè)數(shù)，只要能被6整除，它就是6的倍數(shù)，5同理。那我們就分別求出1——80中有多少個(gè)能被6、5整除的自然數(shù)：80÷6=13……2，80÷5=16，這就說明在1——80中有13個(gè)能被6整除和16個(gè)能被5整除的自然數(shù)。但是有倍數(shù)就有最小公倍數(shù)，∴我們還要求出 1——80中有多少個(gè)數(shù)既能被6整除又能被5整除，也就是6和5的最小公倍數(shù)30：:80÷30=2……30，這就意味著有2個(gè)數(shù)我此前重復(fù)算了1次，需要從中減去，13+16-2=27，這樣的出來的是1——80中能被5或能被6整除的自然數(shù)有多少個(gè)，最后用80減去他就是最終的答案。

????????3、有14個(gè)人吃蘋果，18人吃香蕉，15人吃桃子，1人不吃蘋果，3人不吃香蕉，2人不吃桃子，4人三種水果都吃。問：一共有幾人喜歡吃蘋果或香蕉或桃子？

????????這道題還是容斥原理，只不過對(duì)象數(shù)量從2個(gè)增加到了3個(gè)。第一個(gè)要解決的問題就是原題中說的“不吃”是什么？從開頭我們能看出研究的對(duì)象有蘋果、香蕉、桃子，那么根據(jù)“不”的這種否定進(jìn)行排除可知，不吃蘋果就是香蕉和桃子。另外題目又太長(zhǎng)了，∴我們把圖畫出來（如圖3所示）。由此我們可以很直觀地套用公

? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ?圖3

式求出結(jié)果：14+18+15-1-3-2+4=45（人）答：一共有45人喜歡吃蘋果或香蕉或桃子。

? ? ?? 4、已知某班有50名學(xué)生，其中45名學(xué)生喜歡唱歌，49名學(xué)生喜歡樂器，41名學(xué)生喜歡跳舞，43名學(xué)生喜歡畫畫。問：至少有所少人4種藝術(shù)都喜歡？

????????這是一道經(jīng)典的逆向思維題。題目給出了學(xué)生的數(shù)量和每種藝術(shù)所喜歡的對(duì)應(yīng)人數(shù)，卻要問至少有多少人4種藝術(shù)都喜歡。前面我們知道了“至少”是用總數(shù)減去“最多”，“最多”是所有對(duì)象的總和。因此知道最少就必須知道最多。如果我直接50-（45+49+41+43）的話會(huì)發(fā)現(xiàn)結(jié)果為負(fù)數(shù)，從而使這道題無從下手?！辔覀儜?yīng)該正難則反考慮，先求出有多少人不喜歡唱歌、樂器、跳舞、畫畫。不喜歡唱歌的：50-45=5（名），不喜歡樂器的：50-49=1（名），不喜歡跳舞的：50-41=9（名），不喜歡畫畫的：50-43=7（名 ）。這時(shí)便能得到4種藝術(shù)都不喜歡的總?cè)藬?shù)：5+1+9+7=22（人），即最多有22名學(xué)生4種藝術(shù)都不喜歡。那除去不喜歡的肯定就是喜歡的。用全班人數(shù)減去4種藝術(shù)都不喜歡的人數(shù)，就是我們要的到的答案：50-22=28（名）答：至少有28名學(xué)生4種藝術(shù)都喜歡。我們也可以用流程圖求解（如圖7）。

四、流程圖

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖4

????????1、我們先來看圖（4）。求兩個(gè)對(duì)象的容斥原理：第一步程序開始，建立兩個(gè)集合變量：集合A、集合B、集合A∩B，第二步對(duì)集合A∩B詢問并回答，第三步套入公式A+B-A∩B并判斷其結(jié)果是否大于0，若大于0則執(zhí)行第四步，求集合元素的個(gè)數(shù)。最后程序結(jié)束。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖5

????????2、我們?cè)倏磮D（5）。要求兩個(gè)集合的補(bǔ)集，第一步除了建立變量A、B、A∩B，還要建立全集U、補(bǔ)集Cu（A∩B），第二步詢問并回答A、B、A∩B，第三步同理于圖（4），若判斷為真則第四步判斷A∩B的補(bǔ)集，若補(bǔ)集大于0為真則執(zhí)行最后一步：求A，B都不包含的元素個(gè)數(shù)，最后程序結(jié)束。

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖6?

? ? ? ? ?3 、最后看圖（6），這是一個(gè)求三個(gè)對(duì)象的容斥原理的流程圖，該流程圖同理于圖（4），這里我不多介紹了，留給大家思考。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖7

五、變量信息

????????求兩個(gè)對(duì)象容斥原理用到的：鉛筆單支賣出的銷量，鋼筆單支賣出的銷量，鉛筆、鋼筆同時(shí)賣出的次數(shù)，筆的數(shù)量，最后筆剩的支數(shù)

? ? ? ? 求三個(gè)對(duì)象的容斥原理用到的：不喜歡吃香蕉的人數(shù)、不喜歡吃蘋果的人數(shù)、不喜歡吃桃子的人數(shù)、三種水果都喜歡吃的人數(shù)、喜歡吃桃子的人數(shù)、喜歡吃蘋果的人數(shù)、喜歡吃香蕉的人數(shù)、總?cè)藬?shù)

? ? ? ? 求“至少”問題用到的：四種藝術(shù)都喜歡的最少人數(shù)、不喜歡樂器的人數(shù)、不喜歡唱歌的人數(shù)、不喜歡畫畫的人數(shù)、不喜歡跳舞的人數(shù)、喜歡跳舞的人數(shù)、喜歡畫畫的人數(shù)、喜歡樂器的人數(shù)、四種藝術(shù)都不喜歡的最多人數(shù)、喜歡唱歌的人數(shù)

六、代碼示例

????????1、先看兩個(gè)對(duì)象的容斥原理：拿例1作為我們的編寫對(duì)象。先確定原題的已知數(shù)據(jù)，再利用公式進(jìn)行變量運(yùn)算，最后說答語。代碼如下：

當(dāng)綠旗被點(diǎn)擊

詢問小賣部單獨(dú)賣出多少支鉛筆？

將鉛筆單支賣出的銷量設(shè)為回答

詢問小賣部單獨(dú)賣出去多少支鋼筆？

將鋼筆單支賣出的銷量設(shè)為回答

詢問鉛筆、鋼筆同時(shí)賣出多少次？

將鉛筆、鋼筆同時(shí)賣出的次數(shù)設(shè)為回答

詢問小賣部里總共有多少支筆？

將筆的總數(shù)量設(shè)為回答

????????我們把“筆的總數(shù)量”看成一個(gè)全集，那補(bǔ)集則是兩種筆的總銷量，根據(jù)CuA=U-（A+B-A∩B）可知，最后筆的支數(shù)應(yīng)為正數(shù)。

如果筆的總數(shù)量-（鋼筆賣出的銷量+鉛筆單支賣出的銷量-鉛筆、鋼筆同時(shí)賣出的次數(shù)）＞0那么

將最后筆剩的支數(shù)設(shè)為筆的總數(shù)量-（鋼筆賣出的銷量+鉛筆單支賣出的銷量-鉛筆、鋼筆同時(shí)賣出的次數(shù)）

說：“連接連接最后小賣部還剩和最后筆剩的支數(shù)和支筆”

? ? ? ? ?2、再來看三個(gè)對(duì)象的容斥原理，拿例3作為我們的編寫對(duì)象.還是先確定原題的已知數(shù)據(jù)，再利用公式進(jìn)行變量運(yùn)算，最后說答語。代碼如下：

當(dāng)綠旗被點(diǎn)擊

????????這里我們先不考慮輸入的“合法性”，即是否為正整數(shù)，但憑借生活常識(shí)顯然可知，測(cè)試編程的時(shí)候還是要輸入正整數(shù)，包括結(jié)果。

詢問有多少人喜歡吃蘋果

將喜歡吃蘋果的人數(shù)設(shè)為回答

詢問有多少人喜歡吃香蕉

將喜歡吃香蕉的人數(shù)設(shè)為回答

詢問有多少人喜歡吃桃子

將喜歡吃桃子的人數(shù)設(shè)為回答

詢問有多少人不喜歡吃蘋果

將不喜歡吃蘋果的人數(shù)設(shè)為回答

詢問有多少人不喜歡吃香蕉

將不喜歡吃香蕉的人數(shù)設(shè)為回答

詢問有多少人不喜歡吃桃子

將不喜歡吃桃子的人數(shù)設(shè)為回答

詢問有多少人三種水果都喜歡吃

將三種水果都喜歡吃的人數(shù)設(shè)為回答

將總?cè)藬?shù)設(shè)為：喜歡吃蘋果的人數(shù)+喜歡吃香蕉的人數(shù)+喜歡吃桃子的人數(shù)-不喜歡吃蘋果的人數(shù)-不喜歡吃桃子的人數(shù)-不喜歡吃香蕉的人數(shù)+三種水果都喜歡吃的人數(shù)

說：“連接連接一共有和總?cè)藬?shù)和人”

? ? ? ? ??3、最后我們看例4的代碼：

?當(dāng)綠旗被點(diǎn)擊

????????先確定原題的已知數(shù)據(jù)

詢問班里有多少名學(xué)生

將學(xué)生總數(shù)設(shè)為回答

詢問有多少人喜歡唱歌

將喜歡唱歌的人數(shù)設(shè)為回答

詢問有多少人喜歡跳舞

將喜歡跳舞的人數(shù)設(shè)為回答

詢問有多少人喜歡樂器

將喜歡樂器的人數(shù)設(shè)為回答

詢問有多少人不喜歡畫畫

將喜歡畫畫的人數(shù)設(shè)為回答

????????再接著求4種藝術(shù)各不喜歡的人數(shù)。

將不喜歡唱歌的人數(shù)設(shè)為：學(xué)生總數(shù)-不喜歡唱歌的人數(shù)

將不喜歡跳舞的人數(shù)設(shè)為：學(xué)生總數(shù)-不喜歡跳舞的人數(shù)

將不喜歡樂器的人數(shù)設(shè)為：學(xué)生總數(shù)-不喜歡樂器的人數(shù)

將不喜歡畫畫的人數(shù)設(shè)為：學(xué)生總數(shù)-不喜歡畫畫的人數(shù)

????????由于應(yīng)用題中的求解數(shù)量不能為0，∴要對(duì)上面相減的結(jié)果進(jìn)行判斷，同時(shí)為真才繼續(xù)執(zhí)行，里面一層判斷是四種藝術(shù)都不喜歡的最多人數(shù)。

如果不喜歡唱歌的人數(shù)＞0與不喜歡畫畫的人數(shù)＞0與不喜歡跳舞的人數(shù)＞0與不喜歡樂器的人數(shù)＞0那么

將四種藝術(shù)都不喜歡的最多人數(shù)設(shè)為：不喜歡唱歌的人數(shù)+不喜歡畫畫的人數(shù)+不喜歡樂器的人數(shù)+不喜歡跳舞的人數(shù)

如果學(xué)生總數(shù)-四種藝術(shù)都不喜歡的最多人數(shù)＞0那么

將四種藝術(shù)喜歡的最少人數(shù)設(shè)為：學(xué)生總數(shù)-四種藝術(shù)都不喜歡的最多人數(shù)

說：“連接連接班里有和四種藝術(shù)都喜歡的最少人數(shù)和人四種藝術(shù)都喜歡”