Scratch与数学的整合17

                第17课        容斥原理

一、课程导入

        本节课你将会学到：如何解决容斥原理相关问题？如何让Scratch实现关于容斥原理问题的求解过程？用Scratch编写容斥原理的万能方法是怎样的？

二、知识储备

        1、容斥原理又叫重叠问题，是研究集合元素个数的一个定理。2个对象的容斥原理：元素的个数=集合A中的元素个数+集合B中的元素个数-集合A、B都包含的元素个数（元素的个数=A+B-A∩B）；3个对象的容斥原理：元素的个数=集合A中的元素个数+集合B中的元素个数+集合C中的元素个数-集合A、B都包含的元素个数-集合A、C都包含的元素个数-集合B、C都包含的元素个数-集合A、B、C都包含的元素个数（元素的个数=A+B+C-A∩B-A∩C-B∩C+A∩B∩C）。

        2、要区分开“最多”“至少”“有几个”这类的词。“最多”是所有对象的总和，“至少”是“总数”减去“最多”，其余情况都是“有几个”。

三、例题讲解

        1、已知一家小卖部某天单独卖出去15支铅笔，又单独卖出去10支钢笔，其中有2次是笔同时卖出。问：（1）如果小卖部每次卖笔都是1支1支卖出（除了有2次是两种笔同时卖出），那么小卖部这天卖出去多少次笔？（2）如果小卖部没有新进的笔，且该天最初只有30支笔，那么到小卖部当天下班后，小卖部里还剩下多少支笔？

        我们先来看第（1）小问。通过读题我们发现，这题是已知小卖部一天内卖出若干支铅笔和钢笔的数量，包括单独卖出去铅笔、钢笔、铅笔同是卖出的数量，求笔卖出的次数。那么铅笔、钢笔卖出的支数就是我们要研究的对象。“支”和“次”不是同类词，这可怎么办呢？再仔细读一下题目，题目中提到了“两种笔同时卖出”，那显然这两种笔就是铅笔和钢笔。我们把图画出来（如图1所示），左边的15是铅笔的支

                                    图1

数，右边的10是钢笔的支数，两个圆圈相交处的2表示铅笔和钢笔同时卖出的次数。问法是“每次每支笔都是1支1支卖出。”那么这样该问题就转化成了实际卖出去多少次的问题，如果把每次卖出去1支笔看成集合中的1个元素。那么套用公式A+B-A∩B即可求出问题：15+10-2=23（次）。答：小卖部这天卖出去23次笔。

        我们再来看第（2）小问。通过读题我们发现，这里给出了新的条件：没有新进的笔、最初只有30支笔，其他地方均没有改变。而此时我们知道了卖出去的部分，那没卖出去就是我们要求剩下的。为了方便，我们此时可以把23次照抄下来。不妨我们再画一下图，把30支笔

                                    图2

看成一个全集，A∪B为卖出去的笔的次数，那么用全集“减去”并集得”剩下”的补集，就是我们要求的：30-（15+10-2）=3（支）。答：到小卖部刚下班后，此时还剩3支笔。

        2、在1——80中，既不是6的倍数又不是5的倍数的自然数有多少个？

        这道题看起来非常简单，但如果按传统的方法求，不但计算量大，而且还容易出错。那么我们不妨找规律：任何一个数，只要能被6整除，它就是6的倍数，5同理。那我们就分别求出1——80中有多少个能被6、5整除的自然数：80÷6=13……2，80÷5=16，这就说明在1——80中有13个能被6整除和16个能被5整除的自然数。但是有倍数就有最小公倍数，∴我们还要求出 1——80中有多少个数既能被6整除又能被5整除，也就是6和5的最小公倍数30：:80÷30=2……30，这就意味着有2个数我此前重复算了1次，需要从中减去，13+16-2=27，这样的出来的是1——80中能被5或能被6整除的自然数有多少个，最后用80减去他就是最终的答案。

        3、有14个人吃苹果，18人吃香蕉，15人吃桃子，1人不吃苹果，3人不吃香蕉，2人不吃桃子，4人三种水果都吃。问：一共有几人喜欢吃苹果或香蕉或桃子？

        这道题还是容斥原理，只不过对象数量从2个增加到了3个。第一个要解决的问题就是原题中说的“不吃”是什么？从开头我们能看出研究的对象有苹果、香蕉、桃子，那么根据“不”的这种否定进行排除可知，不吃苹果就是香蕉和桃子。另外题目又太长了，∴我们把图画出来（如图3所示）。由此我们可以很直观地套用公

                                 图3

式求出结果：14+18+15-1-3-2+4=45（人）答：一共有45人喜欢吃苹果或香蕉或桃子。

       4、已知某班有50名学生，其中45名学生喜欢唱歌，49名学生喜欢乐器，41名学生喜欢跳舞，43名学生喜欢画画。问：至少有所少人4种艺术都喜欢？

        这是一道经典的逆向思维题。题目给出了学生的数量和每种艺术所喜欢的对应人数，却要问至少有多少人4种艺术都喜欢。前面我们知道了“至少”是用总数减去“最多”，“最多”是所有对象的总和。因此知道最少就必须知道最多。如果我直接50-（45+49+41+43）的话会发现结果为负数，从而使这道题无从下手。∴我们应该正难则反考虑，先求出有多少人不喜欢唱歌、乐器、跳舞、画画。不喜欢唱歌的：50-45=5（名），不喜欢乐器的：50-49=1（名），不喜欢跳舞的：50-41=9（名），不喜欢画画的：50-43=7（名 ）。这时便能得到4种艺术都不喜欢的总人数：5+1+9+7=22（人），即最多有22名学生4种艺术都不喜欢。那除去不喜欢的肯定就是喜欢的。用全班人数减去4种艺术都不喜欢的人数，就是我们要的到的答案：50-22=28（名）答：至少有28名学生4种艺术都喜欢。我们也可以用流程图求解（如图7）。

四、流程图

                                    图4

        1、我们先来看图（4）。求两个对象的容斥原理：第一步程序开始，建立两个集合变量：集合A、集合B、集合A∩B，第二步对集合A∩B询问并回答，第三步套入公式A+B-A∩B并判断其结果是否大于0，若大于0则执行第四步，求集合元素的个数。最后程序结束。

                                     图5

        2、我们再看图（5）。要求两个集合的补集，第一步除了建立变量A、B、A∩B，还要建立全集U、补集Cu（A∩B），第二步询问并回答A、B、A∩B，第三步同理于图（4），若判断为真则第四步判断A∩B的补集，若补集大于0为真则执行最后一步：求A，B都不包含的元素个数，最后程序结束。

 

                                     图6 

         3 、最后看图（6），这是一个求三个对象的容斥原理的流程图，该流程图同理于图（4），这里我不多介绍了，留给大家思考。

                                     图7

五、变量信息

        求两个对象容斥原理用到的：铅笔单支卖出的销量，钢笔单支卖出的销量，铅笔、钢笔同时卖出的次数，笔的数量，最后笔剩的支数

        求三个对象的容斥原理用到的：不喜欢吃香蕉的人数、不喜欢吃苹果的人数、不喜欢吃桃子的人数、三种水果都喜欢吃的人数、喜欢吃桃子的人数、喜欢吃苹果的人数、喜欢吃香蕉的人数、总人数

        求“至少”问题用到的：四种艺术都喜欢的最少人数、不喜欢乐器的人数、不喜欢唱歌的人数、不喜欢画画的人数、不喜欢跳舞的人数、喜欢跳舞的人数、喜欢画画的人数、喜欢乐器的人数、四种艺术都不喜欢的最多人数、喜欢唱歌的人数

六、代码示例

        1、先看两个对象的容斥原理：拿例1作为我们的编写对象。先确定原题的已知数据，再利用公式进行变量运算，最后说答语。代码如下：

当绿旗被点击

询问小卖部单独卖出多少支铅笔？

将铅笔单支卖出的销量设为回答

询问小卖部单独卖出去多少支钢笔？

将钢笔单支卖出的销量设为回答

询问铅笔、钢笔同时卖出多少次？

将铅笔、钢笔同时卖出的次数设为回答

询问小卖部里总共有多少支笔？

将笔的总数量设为回答

        我们把“笔的总数量”看成一个全集，那补集则是两种笔的总销量，根据CuA=U-（A+B-A∩B）可知，最后笔的支数应为正数。

如果笔的总数量-（钢笔卖出的销量+铅笔单支卖出的销量-铅笔、钢笔同时卖出的次数）＞0那么

将最后笔剩的支数设为笔的总数量-（钢笔卖出的销量+铅笔单支卖出的销量-铅笔、钢笔同时卖出的次数）

说：“连接连接最后小卖部还剩和最后笔剩的支数和支笔”

         2、再来看三个对象的容斥原理，拿例3作为我们的编写对象.还是先确定原题的已知数据，再利用公式进行变量运算，最后说答语。代码如下：

当绿旗被点击

        这里我们先不考虑输入的“合法性”，即是否为正整数，但凭借生活常识显然可知，测试编程的时候还是要输入正整数，包括结果。

询问有多少人喜欢吃苹果

将喜欢吃苹果的人数设为回答

询问有多少人喜欢吃香蕉

将喜欢吃香蕉的人数设为回答

询问有多少人喜欢吃桃子

将喜欢吃桃子的人数设为回答

询问有多少人不喜欢吃苹果

将不喜欢吃苹果的人数设为回答

询问有多少人不喜欢吃香蕉

将不喜欢吃香蕉的人数设为回答

询问有多少人不喜欢吃桃子

将不喜欢吃桃子的人数设为回答

询问有多少人三种水果都喜欢吃

将三种水果都喜欢吃的人数设为回答

将总人数设为：喜欢吃苹果的人数+喜欢吃香蕉的人数+喜欢吃桃子的人数-不喜欢吃苹果的人数-不喜欢吃桃子的人数-不喜欢吃香蕉的人数+三种水果都喜欢吃的人数

说：“连接连接一共有和总人数和人”

          3、最后我们看例4的代码：

 当绿旗被点击

        先确定原题的已知数据

询问班里有多少名学生

将学生总数设为回答

询问有多少人喜欢唱歌

将喜欢唱歌的人数设为回答

询问有多少人喜欢跳舞

将喜欢跳舞的人数设为回答

询问有多少人喜欢乐器

将喜欢乐器的人数设为回答

询问有多少人不喜欢画画

将喜欢画画的人数设为回答

        再接着求4种艺术各不喜欢的人数。

将不喜欢唱歌的人数设为：学生总数-不喜欢唱歌的人数

将不喜欢跳舞的人数设为：学生总数-不喜欢跳舞的人数

将不喜欢乐器的人数设为：学生总数-不喜欢乐器的人数

将不喜欢画画的人数设为：学生总数-不喜欢画画的人数

        由于应用题中的求解数量不能为0，∴要对上面相减的结果进行判断，同时为真才继续执行，里面一层判断是四种艺术都不喜欢的最多人数。

如果不喜欢唱歌的人数＞0与不喜欢画画的人数＞0与不喜欢跳舞的人数＞0与不喜欢乐器的人数＞0那么

将四种艺术都不喜欢的最多人数设为：不喜欢唱歌的人数+不喜欢画画的人数+不喜欢乐器的人数+不喜欢跳舞的人数

如果学生总数-四种艺术都不喜欢的最多人数＞0那么

将四种艺术喜欢的最少人数设为：学生总数-四种艺术都不喜欢的最多人数

说：“连接连接班里有和四种艺术都喜欢的最少人数和人四种艺术都喜欢”