《00-信息学竞赛中问题求解题常见考查题型分析.docx》由会员分享，可在线阅读，更多相关《00-信息学竞赛中问题求解题常见考查题型分析.docx（40页珍藏版）》请在三一办公上搜索。
1、信息学竞赛中问题求解题常见考查题型分析问题求解是信息技术竞赛初赛中常见题型，它共两题，每题5分，共 10分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合 问题、逻辑推理、递推关系等问题出现在问题求解中，但是在实际的 竞赛中，问题求解得分率往往是不高的，下面我对问题求解的题型进 行了一下探索。寻找假币问题有n (nN3)个硬币，其中一个是假币，已知假币的重量比其他的要 重一些，你有一架天平。现在要称出哪个假币来。解析：首先我们先来考虑最简单的问题1。为了方便叙述，把n个硬币按 1,2,n顺次编号。若n=3，把一号硬币放在天平左边、二号硬币放在天平右边。如果天 平：左偏，一号重，是假币。右
2、偏，二号重，是假币。保持平衡，那么一、二都是正常的硬币，因此就只有可能三号硬币是 假币了。因此n=3，至多一次就能称出哪个是假币。记作f(3)二1。下面考虑n=9。把所有的硬币分成三组：A1,2,3,B4,5,6,C7,8,9。A组的硬币放在左边、B组放在右边。 如果天平：左偏，则假币在A组里面。右偏，则假币在B组里面。保持平衡，假币在C组里面。无论在哪个组里面，我们已经把假币的范围从“9”缩小到了 “3”， 也就是减少到原来的1/3。之前我们已经研究过，3个硬币1次就能 称出来，故而f(9)=2o不难推广到一般的情况：定理 1.1 f(3n) 二n。证明：n=1,2时，已证。设n=k成立，则
3、f(3k)=k；下面考虑n=k+1 的情况。将3k+1个硬币分成三堆A, B, C，使得|A| = |B| = |C|=3k。把A放在天平左边、B放在右边，天平：左偏，假币在A右偏，假币在B平衡，假币在C无论哪种结果，我们都把假币的范围缩小到了 3k个硬币里面。而 f(3k)=k，故而 f(3k+1)=k+1。综上，定理1.1成立。稍经分析不难得到：定理 1.2 f(n)=期 n这个的证明和定理1.1完全类似，分n mod 3 = 0, 1, 2适当讨论即 可。我们必须注意到log3见是可行的，因为我们能够构造出这样一个方 案。问题是它是否最优？我们采取的方案是每次将硬币尽量均匀的三分，这样做
4、的根据就是天 平只有三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一 份都能将结果的范围缩小到原来的1/3。从感性上认识，iog3见应该 就是最优解了。为了更加严格的证明log3见的最优性，我们引进判定树的概念。下图就是n=9时的一种判定树：此题的判定树是这样一棵树：叶子节点代表一种可能的结果。非叶子节点代表一次称量。非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情况。任意一种称量方案都能唯一的表示成一棵判定树；反过来一棵判定树 也唯一对应一种称量方案。容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原 因。做出判断之前，谁也无法预知哪个硬币是假币，每个都有可能是
5、我们 的目标；因此一个有意义的判定树应该具有至少n个叶子节点。n个叶子节点的树的深度hiog3n ,故而可以证明,f(n)= log3n 是最优的。我们的结论是：有n (n3)个硬币，其中一个是假币，假币的重量 比其他的要重一些。给一架天平，至少称屁尸次，就能找出那个假 币。具体的方案是将硬币每次都尽量均匀的三分。让我们总结一下。“三分”是整个解法的核心。我们选择三分，而不是二分或者四分是 有原因的，它的本质是由判定树的特殊结构一一三叉树一一所决定 的。同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。 实际上h log3n中的“二”当且仅当硬币被均匀的分配时才能达 到。这里说的“
6、均匀”是指“在最坏情况下获得最好的效果”。因为一棵 树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个 树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均 匀”分配的理论根据。练习：第12届全国青少年信息学奥林匹克联赛初赛题现有80枚硬币，其中有一枚是假币，其重量稍重，所有真币的重量都相同，如 果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？ 你还要指出第1次的称重方法。请写出你的结果：答案：4次；第一步，分成三组：27, 27, 26,将前2组放到天平 上。取石子游戏的策略及其应用有一种很有意思的游戏，就是有物体若干堆，可以是石子或是围棋子 等等均可。两个人轮
7、流从堆中取物体若干，规定最后取光物体者取胜。 取石子游戏是我国民间流传已久的一种博奕，在国外亦称Nim游戏。 别看这游戏极其简单，却蕴含着深刻的道理。下面我们来分析一下要 如何才能够取胜。游戏I有若干堆任意数目的小石子al，a2，am(mN1)，两人 轮流取石子，每人每次可以从其中任意一堆中取，每次可以取1、2、 3、 或k(1WkWmina1，a2，am)颗石子，把石子取完的人 为胜者。采用符号a1，a2,，am； k来代表游戏I中小石子的初始状况和 限制条件，一个人取一次石子实际上就是把a1，a2,，am； k中 某个分量ai(1WiWm)减小为ai，即a1，a2，ai，am；kal, a
8、2,，ai，am； k（0Wai，ai）,我们把这种取一次石子使数组发生的变换称为T变换，根据现成博奕论先驱 冯诺伊曼（VonNeumann）的“完全确定信息游戏必定存在一种确定的 获胜策略”的经典理论，要么对先取者存在某种取法，即某个T变换， 无论后取者如何取，先取者总有相应对策，直至最终取得胜利；要么 无论先取者如何取，后取者可以找到某种T变换，保证后取者总有相 应策略获胜。为了解决游戏al，a2,，am； k的对策，我们先看 一个简单的例子。例1桌上放着一堆小石子一共100颗，两人（甲、乙）轮流取，每次 可以取1至10颗，取完的人为胜者，怎样才能取胜？分析这个问题实际上是取石子游戏的特殊
9、情形100； 10，我们利用 倒推法：容易看出11是取胜的关键数学，因为到此时，不论对方（甲） 取多少颗（大于0且小于11），总留下大于0且小于11颗石子，这样 乙方一次取完即获得胜利。同样地分析，要取到11必须取到22, 33, 44，55，66，77，88，99，这样我们就知道了获胜之道：先取1颗石子，留下99颗，然后对方取a（1WaW10）颗，己方取 （11-a）颗，就总能掌握这种致胜的关键数，从而确保获胜。如果 对方先取，己方只需利用对方不知道其中奥秘，争取到一个致胜数， 就总能依中方法取到下一个致胜数，最后取得胜利。实际上，如果 局中人均熟知获胜策略，那么开局的局势就已经完全决定了结
10、局的输 赢，例1其实是先取者必胜的局势，从这个例子的分析过程我们得到 启示：可以用同余理论来探讨一般情况。一般地，在取石子游戏al, a2,，am； k中，ai三ai (modk+1)(i=1, 2,，m)其中 0WaiWk，在al, a2,，am； k中有取 胜策略的一方在al, a2,，am； k中也有取胜策略。证明在al, a2,，am； k中有获胜策略的一方，对于大于k的分量ai(i=1, 2,，m总能做到ai三ai (modk+1)，即对方取a(1WWk)，己方 取k+1-a，使两人各取一次之后该分量减小k+1,也就对第i堆各取 n(nN1)次之后石子数便由ai=ai +n(k+1)
11、变成ai ,故在a1, a2,，am； k中有取胜策略的一方在a1, a2,，am； k中 也有取胜策略。游戏II有若干堆任意数目的小石子a1, a2,，am,两人轮流从 中取石子，每人每次可以取走任意一堆中任意数目的石子，不能不取， 把石子取完的人为胜者。采用m元数组a1, a2,，am(mN1)来描述这类取石子游戏，一人 取走一次石子相当于用某个T变换把其中某个分量ai(1WiWm)减小 为 ai，即a1, a2,，ai,，amTa1, a2,，ai,， am(0Wai ai)。有趣的是为了解决这类一般情况，我们需要用到整数的二进位制，把 m元数组a1, a2,，am中的每一个分量用二进位
12、制数表示，ai(1 WiWm)写在第i行，同时对齐二进位制数的位数，在列上作十进位 制加法，其和写在第(m+1)行，记为n1, n2,，nj,，nl，如果所有这些和数nj(1 W j Wl)均为偶数，我们称这个m元数组为偶数组；若nj(1WjWl)，中有一个数为奇数，则称之为非偶数组。例如：对于3元数组2, 3, 5；a1201 0a2301 1a3510 12n1n2 n3因为其中n1=1,所以2, 3, 5是非偶数组。同样，对于3元数组2, 3, 1：a121 0a231 1a3102n1 n2由于nj(j=1, 2)为偶数，则2, 3, 1为偶数组。偶数组与非偶数组在T变换下具有如下性质
13、：偶数组经过一次T变换之后一定变为非偶数组；对于非偶数组，一定可以找到某一个T变换，使其变为偶数组。这样我们容易判定：如果给定的m元数组是偶数组，则后取者必有获 胜策略；相反，若给定m元数组为非偶数组，则先取者有方法获胜， 因为给定的m元数组为偶数组，先取者无论怎样取，只能将偶数组变 为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每 次取走石子，剩下石子数目一定越来越小，而0，0，0是偶数 组，所以后取者获胜，同理可证相反情况。例2有三堆石子，各堆数目分别是2、3、6，两人轮流取，取完的人 为胜者，若甲先乙后，谁取胜？解：al2010a23011a361101n1 n2 n3ni为
14、奇数i=1，2, 3,所以2, 3, 6为非偶数，我们可以判定：先 取者甲获胜，依性质证明过程给出的操作方法，只需将a3=6变为1， 可以验证2, 3，1是偶数组，无论乙如只可能变成如下六种情形之 一：2，3，0，1，2，1，1，2，0，1，1，3，1，0，3， 1，都是非偶数组，同样按原方法可以将其变2或1，1，乙再取 后，甲总能确保获胜。例3：第12届全国青少年信息学奥林匹克联赛初赛题现有5堆石子， 石子数依次为3, 5, 7, 19, 50，甲乙两人轮流从任一堆中任取（每 次只能取自一堆，不能不取），取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略(即无论乙怎样取，甲只要不失误，都能
15、获胜)？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：O解：由游戏II知，得到如下推理：010011000111000101000011010010(18)1050-18 = 32所以第1次只能在第5堆石子中取32粒，使得取出32粒后为偶数组。最后我们看一道综合利用游戏1、11的例子：例4在3X25的棋盘上放着三颗石a、b、c(如图所示)，两人轮流将石子向右移人一次只可以移动其中一颗石子1至5后无格可走者为输 家，若甲先行，乙后行，赢？abc解 由25三7(mod6)，根据游戏I的策略25, 25, 25； 5中有获胜策 略的一方在7，7， 7； 5中也有获胜方法，又把石子由图中所示3
16、,2, 6移到7, 7, 7即相当于取石子游戏II的4, 5, 1,由于4, 5, 1是偶数组，故先移者输。抽屉原理“抽屉原理”最先是由19世纪的德国数学家迪里赫莱(Dirichlet) 运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢 原理”的。这个原理可以简单地叙述为“把10个苹果，任意分放在 9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。这 个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常 常得到一些令人惊异的结果。抽屉原理是国际国内各级各类信息学竞 赛中的重要内容，本讲就来学习它的有关知识及其应用。知识点：定理1、如果把n+1个元素分成n个集合，那么
17、不管怎么分，都存在 一个集合，其中至少有两个元素。证明：(用反证法)若不存在至少有两个元素的集合，则每个集合至 多1个元素，从而n个集合至多有n个元素，此与共有n+1个元素矛 盾，故命题成立。在定理1的叙述中，可以把“元素”改为“物件”，把“集合”改成 “抽屉”，抽屉原理正是由此得名。同样，可以把“元素”改成“鸽子”，把“分成n个集合”改成“飞 进n个鸽笼中”。“鸽笼原理”由此得名。讲解范例:一个小组共有13名同学，其中至少有2名同学同一个月过生日。为 什么？ 【分析】每年里共有12个月，任何一个人的生日，一定在其中的某 一个月。如果把这12个月看成12个“抽屉”，把13名同学的生日 看成13
18、只“苹果”，把13只苹果放进12个抽屉里，一定有一个抽 屉里至少放2个苹果，也就是说，至少有2名同学在同一个月过生日。【例2】任意4个自然数，其中至少有两个数的差是3的倍数。这是 为什么？【分析与解】首先我们要弄清这样一条规律：如果两个自然数除以3 的余数相同，那么这两个自然数的差是3的倍数。而任何一个自然数 被3除的余数，或者是0，或者是1，或者是2，根据这三种情况， 可以把自然数分成3类，这3种类型就是我们要制造的3个“抽屉”。 我们把4个数看作“苹果”，根据抽屉原理，必定有一个抽屉里至少 有2个数。换句话说，4个自然数分成3类，至少有两个是同一类。 既然是同一类，那么这两个数被3除的余数
19、就一定相同。所以，任意 4个自然数，至少有2个自然数的差是3的倍数。有规格尺寸相同的5种颜色的袜子各15只混装在箱内，试问不论如 何取，从箱中至少取出多少只就能保证有3双袜子（袜子无左、右之 分）？【分析与解】试想一下，从箱中取出6只、9只袜子，能配成3双袜 子吗？回答是否定的。按5种颜色制作5个抽屉，根据抽屉原理1， 只要取出6只袜子就总有一只抽屉里装2只，这2只就可配成一双。 拿走这一双，尚剩4只，如果再补进2只又成6只，再根据抽屉原理 1，又可配成一双拿走。如果再补进2只，又可取得第3双。所以， 至少要取6 + 2 + 2=10只袜子，就一定会配成3双。一个布袋中有35个同样大小的木球，
20、其中白、黄、红三种颜色球各 有10个，另外还有3个蓝色球、2个绿色球，试问一次至少取出多 少个球，才能保证取出的球中至少有4个是同一颜色的球？【分析与解】从最“不利”的取出情况入手。最不利的情况是首先取出的5个球中，有3个是蓝色球、2个绿色球。 接下来，把白、黄、红三色看作三个抽屉，由于这三种颜色球相等均 超过4个，所以，根据抽屉原理2,只要取出的球数多于（4-1）X 3=9个，即至少应取出10个球，就可以保证取出的球至少有4个是 同一抽屉（同一颜色）里的球。故总共至少应取出10 + 5=15个球，才能符合要求。思考：把题中要求改为4个不同色，或者是两两同色，情形又如何？当我们遇到“判别具有某
21、种事物的性质有没有，至少有几个”这样的 问题时，想到它一一抽屉原理，这是你的一条“决胜”之路。【例5】.现有64只乒乓球，18个乒乓球盒，每个盒子里最多可以放 6只乒乓球，至少有 个乒乓球盒子里的乒乓球数目相同？【分析与解】：18个乒乓球盒，每个盒子里至多可以放6只乒乓球。 为使相同乒乓球个数的盒子尽可能少，可以这样放：先把盒子分成6 份，每份有186=3 （只 ），分别在每一份的3个盒子中放入1只、 2只、3只、4只、5只、6只乒乓球，即3个盒子中放了 1只乒乓球，3个盒中放了 2只乒乓球3个盒子中放了 6只乒乓球。这样，18 个盒子中共放了乒乓球（1+2+3+4+5+6）X3=63 （只）
22、。把以上6种不同的放法当做抽屉，这样剩下64-63=1 （只）乒乓球不 管放入哪一个抽屉里的任何一个盒子里（除已放满6只乒乓球的抽屉 外），都将使该盒子中的乒乓球数增加1只，这时与比该抽屉每盒乒 乓数多1的抽屉中的3个盒子里的乒乓球数相等。例如剩下的1只乒 乓球放进原来有2只乒乓球的一个盒子里，该盒乒乓球就成了 3只，再加上原来装有3只乒乓球的3个盒子，这样就有4个盒子里装有3个乒乓球。所以至少有4个乒乓球盒里的乒乓球数目相同。提示语抽屉原理还可以反过来理解：假如把n+1个苹果放到n个抽屉里， 放2个或2个以上苹果的抽屉一个也没有（与“必有一个抽屉放2个 或2个以上的苹果”相反），那么，每个抽
23、屉最多只放1个苹果，n 个抽屉最多有n个苹果，与“n+1个苹果”的条件矛盾。运用抽屉原理的关键是“制造抽屉”。通常，可采用把n个“苹果” 进行合理分类的方法来制造抽屉。比如，若干个同学可按出生的月份 不同分为12类，自然数可按被3除所得余数分为3类等等。容斥问题在19世纪末，德国数学家康托系统地描绘了一个能够为全部数学提 供基础的通用数学框架，他创立的这个学科一直是我们数学发展的根 植地，这个学科就叫做集合论。它的概念与方法已经有效地渗透到所 有的现代数学。可以认为，数学的所有内容都是在“集合”中讨论、 生长的。容斥问题在信息学竞赛的问题求解中也经常出现。知识点集合与元素：把一类事物的全体放在
24、一起就形成一个集合。每个集合 总是由一些成员组成的，集合的这些成员，叫做这个集合的元素。如：集合A=0，1，2，3，9，其中0，1，2，9为A的元 素。并集：由所有属于集合A或集合B的元素所组成的集合，叫做A，B 的并集，记作AUB，记号“U”读作“并”。AUB读作“A并B”， 用图表示为图中阴影部分表示集合A，B的并集AUB。例：已知6的约数集合为A=1, 2, 3, 6, 10的约数集合为B=1,2, 5, 10，则 AUB=1, 2, 3, 5, 6, 10交集：A、B两个集合公共的元素，也就是那些既属于A，又属于B的 元素，它们组成的集合叫做A和B的交集，记作“ACB”，读作“A 交B
25、”，如图阴影表示：例：已知6的约数集合A=1, 2, 3, 6, 10的约数集合B=1, 2, 5, 10,则 ACB=1, 2。容斥原理（包含与排除原理）：（用|A |表示集合A中元素的个数，如A=1, 2, 3,则|A|=3）原理一：给定两个集合A和B,要计算AUB中元素的个数，可以分 成两步进行：第一步：先求出I A | + | B 1（或者说把A, B的一切元素都“包含” 进来，加在一起）；第二步：减去I ACB |（即“排除”加了两次的元素）总结为公式：|AUB|二 I A | + | B | - | APB I原理二：给定三个集合A, B, C。要计算AUBUC中元素的个数，可 以
26、分三步进行：第一步：先求 I A | + | B | + | C |；第二步：减去 I APB |,| BPC |,| CPA |；第三步：再加上I APBPC |。即有以下公式：|AUBUC| = |A| + |B| + |C|-|APB|-|BPC| - |CPA| + |A PBPC|解题思路：遇到集合问题，首先要弄请：集合里的元素是什么。集合新名词新概念多。如集合、元素、有限集、无限集、列举法、描 述法、子集、真子集、空集、非空集合、全集、补集、交集、并集等。新关系新符号多，如属于、不属于、包含、包含于、真包含、真包含 于、相等、不相等、相交、相并、互补（E、任、G、1、N、将、Z、Q
27、、R、C、U、CA、I、品=、2）等，这些新概念新关系，多而 抽象。在这千头万绪中，应该抓住“元素”这个关键，因为集合是由 元素确定的，“子、全、补、交、并、空”等集合也都是通过元素来 定义的。集合中元素的特征即“确定性”，“互异性”、“无序性” 也就是元素的性质。集合的分类（有限集与无限集）与表示方法（列举 法与描述法）也是通过元素来刻画的。元素是集合的基本内核，研究 集合，首先就要确定集合里的元素是什么。例题分析：例1求不超过20的正整数中是2的倍数或3的倍数的数共有多少个。 分析：设A=20以内2的倍数，B=20以内3的倍数，显然，要求 计算2或3的倍数个数，即求I AUB |o解1：
28、A=2, 4，6，20，共有10个元素，即|A|=10B=3，6，9，18，共有6个元素，即|B|二6ACB=既是2的倍数又是3的倍数 = 6, 12, 18，共有3个元素，即 |ACB|=3所以 I AUB | = | A | + | B | - | ACB | =10+6-3=13，即 AUB 中共有13个元素。14121015解2：本题可直观地用图示法解答如图，其中，圆A中放的是不超过20的正整数中2的倍数的全体;圆B 中放的是不超过20的正整数中3的倍数的全体，其中阴影部分的数 6,12,18是既是2的倍数又是3的倍数的数（即ACB中的数）只要数 一数集合AUB中的数的个数即可。例2某
29、班统计考试成绩，数学得90分上的有25人；语文得90分以 上的有21人；两科中至少有一科在90分以上的有38人。问两科都 在90分以上的有多少人？解：设A=数学成绩90分以上的学生B=语文成绩90分以上的学生那么，集合AUB表示两科中至少有一科在90分以上的学生，由题意 知，|A|=25,|B|=21,|AUB|二38现要求两科均在90分以上的学生人数，即求| ACB |，由容斥原理得| ACB | = | A | + | B | - | AUB | =25+21-38=8点评：解决本题首先要根据题意，设出集合A，B，并且会表示AUB， A CB，再利用容斥原理求解。例3某班同学中有39人打篮
30、球，37人跑步，25人既打篮球又跑步， 问全班参加篮球、跑步这两项体育活动的总人数是多少？ 解：设A=打篮球的同学; B=跑步的同学则ACB=既打篮球又跑步的同学A U B=参加打篮球或跑步的同学应用容斥原理 | AUB | = | A | + | B | - | ACB | =39+37-25=51 （人）例4某年级的课外学科小组分为数学、语文、外语三个小组，参加 数学小组的有23人，参加语文小组的有27人，参加外语小组的有 18人；同时参加数学、语文两个小组的有4人，同时参加数学、外 语小组的有7人，同时参加语文、外语小组的有5人；三个小组都参 加的有2人。问：这个年级参加课外学科小组共有
31、多少人？解1：设A=数学小组的同学，B=语文小组的同学，C=外语小组 的同学，ACB=数学、语文小组的同学，AAC= 参加数学、外语小 组的同学，BAC=（参加语文、外语小组的同学，ACBCC=三个小 组都参加的同学由题意知：| A | =23，| B | =27，| C | =18|ACB|=4，|ACC|=7，|BCC|=5，|ACBCC|=2根据容斥原理二得：|aubuc| = |a| + |b| + |c|Tacb|Tacc|Tbcc| + |acBCC |=23+27+18- （4+5+7） +2=54 （人）解2：利用图示法逐个填写各区域所表示的集合的元素的个数，然 后求出最后结果
32、。设A、B、C分别表示参加数学、语文、外语小组的同学的集合，其图 分割成七个互不相交的区域，区域W （即ACBCC）表示三个小组都 参加的同学的集合，由题意，应填2。区域W表示仅参加数学与语文 小组的同学的集合，其人数为4-2=2 （人）。区域可表示仅参加数学 与外语小组的同学的集合，其人数为7-2=5 （人）。区域V表示仅参 加语文、外语小组的同学的集合，其人数为5-2=3 （人）。区域I表 示只参加数学小组的同学的集合，其人数为23-2-2-5=14 （人）。同 理可把区域II、III所表示的集合的人数逐个算出，分别填入相应的区 域内，则参加课外小组的人数为； 14+20+8+2+5+3+
33、2=54 （人）点评：解法2简单直观，不易出错。由于各个区域所表示的集合的元 素个数都计算出来了，因此提供了较多的信息，易于回答各种方式的 提问。例5学校教导处对100名同学进行调查，结果有58人喜欢看球赛， 有38人喜欢看戏剧，有52人喜欢看电影。另外还知道，既喜欢看球 赛又喜欢看戏剧（但不喜欢看电影）的有6人，既喜欢看电影又喜欢 看戏剧（但不喜欢看球赛）的有4人，三种都喜欢的有12人。问有 多少同学只喜欢看电影？有多少同学既喜欢看球赛又喜欢看电影（但 不喜欢看戏剧）？（假定每人至少喜欢一项）解法1：画三个圆圈使它们两两相交，彼此分成7部分（如图）这三 个圆圈分别表示三种不同爱好的同学的集合
34、，由于三种都喜欢的有 12人，把12填在三个圆圈的公共部分内（图中阴影部分），其它6 部分填上题目中所给出的不同爱好的同学的人数（注意，有的部分的 人数要经过简单的计算）其中设既喜欢看电影又喜欢看球赛的人数为 X，这样，全班同学人数就是这7部分人数的和，即16+4+6+ （40-x ） + （36-X ） +12=100解得X =14只喜欢看电影的人数为36-14=22解法2：设A=(喜欢看球赛的人, B=喜欢看戏剧的人，C=(喜欢看 电影的人,依题目的条件有|AUBUC|=100, |AAB|=6+12=18 (这里 加12是因为三种都喜欢的人当然喜欢其中的两种)，|BC C|=4+12=1
35、6, |ACBCC|=12,再设|ACC|=12+x 由容斥原理二：|A UBUC | = |A| + |B| + |C|-|ACB|-|ACC|-|BCC| + |ACBCC| 得：100=58+38+52- (18+16+x +12) +12 解得：x =14 .36-14=22所以既喜欢看电影又喜欢看球赛的人数为14,只喜欢看电影的人数 为22。排列组合问题知识点： 1 一分类计数原理：做一件事情，完成它可以有n类办法，在第一类办 法中有气种不同的方法，在第二类办法中有闩种不同的方法，, 在第n类办法中有种不同的方法.那么完成这件事共有N = mi + m2 + mn种不同的方法2. 分
36、步计数原理：做一件事情，完成它需要分成n个步骤，做第一步 有m1种不同的方法，做第二步有m2种不同的方法， ，做第n步 有气种不同的方法，那么完成这件事有N = mi X m2 X X mn种不同的方 法.3. 排列的概念：从n个不同元素中，任取m ( m n )个元素(这里 的被取元素各不相同)按照一定的顺序排成一列，叫做从n个不同元 素中取出m个元素的一个排列.4. 排列数的定义：从n个不同元素中，任取m ( m n )个元素的所 有排列的个数叫做从n个元素中取出m元素的排列数，用符号弋表示 5 .排列数公式：Am = n(n - 1)(n - 2) (n - m +1) ( m, n e
37、 N*, m n )7 .排列数的另一个计算公式:Am =(n - m)!6阶乘：n!表示正整数1到n的连乘积，叫做n的阶乘规定0! = 1.8组合的概念：一般地，从n个不同元素中取出m（m n）个元素并成一 组，叫做从n个不同元素中取出m个元素的一个组合.9.组合数的概念：从n个不同元素中取出m（mn）个元素的所有组合 的个数，叫做从n个不同元素中取出m个元素的组合数.用符号。：表 示.Am n(n-1)(n2) (nm+1)10.组合数公式:n!Cm = =n Amm!m或 n m!（n 一 m）! （n,m e N*,且m n）ii,组合数的性质1： Cm=Cm.规定：Cn=1 ；2：
38、Cm = Cm+&一12 .圆排列由A = 。,a ,a，,a 的n个元素中，每次取出r个元素排在一个圆环 上，叫做一个圆排列（或叫环状排列）.圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍 是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同， 但元素之间的顺序不同，才是不同的圆排列.定理：在A = a , a , a , ., a 的n个元素中，每次取出r个不同的元素进 123n行圆排列，圆排列数为生.r13. 可重排列允许元素重复出现的排列，叫做有重复的排列在m个不同的元素中，每次取出n个元素，元素可以重复出现，按照 一定的顺序那么第一、第二、第n位是的选取元素
39、的方法都是m种， 所以从m个不同的元素中，每次取出n个元素的可重复的排列数为m n .14. 不尽相异元素的全排列如果n个元素中，有p个元素相同，又有p个元素相同，又有p 个元素相同（p1 + p2+.+ , n），这n个元素全部取的排列叫做不 尽相异的n个元素的全排列，它的排列数是n! p ! p !p !15 .可重组合从n个元素，每次取出p个元素，允许所取的元素重复出现1,2,p次12s的组合叫从n个元素取出p个有重复的组合.定理：从n个元素每次取出p个元素有重复的组合数为：Hp =Crn n+（ p-1）解题思路：排列组合题的求解策略排除：对有限条件的问题，先从总体考虑，再把不符合条件
40、的所有情 况排除，这是解决排列组合题的常用策略.分类与分步有些问题的处理可分成若干类，用加法原理，要注意每两类的交集为 空集，所有各类的并集是全集；有些问题的处理分成几个步骤，把各 个步骤的方法数相乘，即得总的方法数，这是乘法原理.对称思想：两类情形出现的机会均等，可用总数取半得每种情形的方 法数.插空：某些元素不能相邻或某些元素在特殊位置时可采用插空法.即 先安排好没有限制条件的元素，然后将有限制条件的元素按要求插入 到排好的元素之间.捆绑：把相邻的若干特殊元素“捆绑”为一个“大元素”，然后与其 它“普通元素”全排列，然后再“松绑”，将这些特殊元素在这些位 置上全排列.隔板模型：对于将不可辨
41、的球装入可辨的盒子中，求装的方法数，常 用隔板模型.如将12个完全相同的球排成一列，在它们之间形成的 11个缝隙中任意插入3块隔板，把球分成4堆，分别装入4个不同 的盒子中的方法数应为c 3，这也就是方程a + b + c + d = 12的正整数解 的个数.11解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成， 对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就 是会正确使用分类计数原理和分步计数原理、排列定义和组合定义， 其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解 题方法：讲解范例：相临问题一一整体捆绑法例1. 7名学生站成一排，甲、乙必须站在一起有多
42、少不同排法？ 解：两个元素排在一起的问题可用“捆绑”法解决，先将甲乙二人 看作一个元素与其他五人进行排列，并考虑甲乙二人的顺序，所以 共有4 4? =1440种。捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决 问题.即将需要相邻的元素合并为一个元素，再与其它元素一起作排列，同时要注意合并元素内部也可以作排列.一般地：冉个人站成一排, 其中某刑个人相邻，可用“捆绑”法解决，共有种排法。练习：5个男生3个女生排成一排,3个女生要排在一起，有多少种不 同的排法？分析此题涉及到的是排队问题，对于女生有特殊的限制，因此，女生 是特殊元素,并且要求她们要相邻，因此可以将她们看成是一个元素 来
43、解决问题.解 因为女生要排在一起，所以可以将3个女生看成是一个人，与5 个男生作全排列，有彳 种排法，其中女生内部也有勺 种排法，根 据乘法原理，共有P6 P；种不同的排法.不相临问题一一选空插入法例2. 7名学生站成一排，甲乙互不相邻有多少不同排法？解：甲、乙二人不相邻的排法一般应用“插空”法，所以甲、乙二 人不相邻的排法总数应为：W A =焚00种.插入法:对于某两个元素或者几个元素要求不相邻的问题，可以用插 入法.即先排好没有限制条件的元素，然后将有限制条件的元素按要 求插入排好元素的空档之中即可.若就个人站成一排，其中幽个人不 相邻，可用“插空”法解决，共有忒如嫂-心种排法。练习： 学
44、校组织老师学生一起看电影，同一排电影票12张。8个 学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少 种不同的坐法？分析 此题涉及到的是不相邻问题，并且是对老师有特殊的要求，因此 老师是特殊元素，在解决时就要特殊对待.所涉及问题是排列问题.解 先排学生共有彳种排法，然后把老师插入学生之间的空档，共有 7个空档可插，选其中的4个空档，共有P4种选法.根据乘法原理，共 有的不同坐法为 P8P4种.复杂问题一一总体排除法或排异法有些问题直接法考虑比较难比较复杂，或分类不清或多种时，而它的 反面往往比较简捷，可考虑用“排除法”，先求出它的反面，再从整 体中排除.解决几何问题必须注意几何图形
45、本身对其构成元素的限 制。例3.正六边形的中心和顶点共7个点，以其中3个点为顶点的三角 形共有个.解：从7个点中取3个点的取法有痣种，但其中正六边形的对角线 所含的中心和顶点三点共线不能组成三角形，有3条，所以满足条 件的三角形共有-3 = 32个.练习：我们班里有43位同学，从中任抽5人，正、副班长、团支部书 记至少有一人在内的抽法有多少种？分析此题若是直接去考虑的话，就要将问题分成好几种情况,这样解 题的话，容易造成各种情况遗漏或者重复的情况.而如果从此问题相 反的方面去考虑的话，不但容易理解，而且在计算中也是非常的简便. 这样就可以简化计算过程.解43人中任抽5人的方法有 彳 种，正副班
46、长，团支部书记都不在 内的抽法有勺。种,所以正副班长，团支部书记至少有1人在内的抽 法有 C；3 q种.特殊元素一一优先考虑法对于含有限定条件的排列组合应用题，可以考虑优先安排特殊位置， 然后再考虑其他位置的安排。例4. 1名老师和4名获奖学生排成一排照像留念，若老师不排在 两端，则共有不同的排法 种.解：先考虑特殊元素（老师）的排法，因老师不排在两端，故可在 中间三个位置上任选一个位置，有典种，而其余学生的排法有式 种，所以共有盅式=72种不同的排法.例5.乒乓球队的10名队员中有3名主力队员，派5名队员参加比 赛，3名主力队员要安排在第一、三、五位置，其余7名队员选2 名安排在第二、四位置，那么不同的出场安排共有 种.解：由于第一、三、五位置特殊，只能安排主力队员，有/种排法， 而其余7名队员选出2名安排在第二、四位置，有&种排法，所以 不同的出场安排共有式=252种.多元问题一一分类讨论法对于元素多，选取情况多，
