信息学竞赛中数学知识

信息学竞赛中数学知识第一页，共13页。逻辑代数主要掌握�辑代数的逻辑运算，逻辑运算和Pascal中的逻辑运算相似，只不过符号不同而已。逻辑代数的运算符和Pascal的运算符有如下对应关系：┓：NOT〔非〕∨：OR〔或〕∧：AND〔与〕它们的运算顺序和Pascal中的规定是一致的，“非〞优先级最高，“或〞最低。怎么来记忆符号和优先级顺序?第二页，共13页。逻辑代数运算练习题1.设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是〔〕。A.(A∧B)∨(C∧D∨A)B.((A∧B)∨C)∧DC.(B∨C∨D)∧D∧AD.A∧(D∨C)∧B2.设A=B=true，C=D=false，以下逻辑运算表达式值为假的有〔〕。A.(¬A∧B)∨(C∧D∨A)B.¬(((A∧B)∨C)∧D)C.A∧(B∨C∨D)∨DD.(A∧(D∨C))∧B

第三页，共13页。排列组合问题此处我们只讨论最简单的排列组合问题。乘法原理：完成一件事可以分为n个步骤，每个步骤又可分为a1,a2,a3，…，an个不同的方法，那么完成此事的总方法有a1×a2×a3×…×an种方法。加法原理：如果完成一件任务有n类方法，在第一类方法中有m1种不同方法，在第二类方法中有m2种不同方法……在第n类方法中有mn种不同方法，那么完成这件任务共有N=m1+m2+…+mn第四页，共13页。排列组合问题加法原理典型例题：从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中火车有4班，汽车有3班，轮船有2班。问：一天中乘坐这些交通工具从甲地到乙地，共有多少种不同走法？

乘法原理典型例题：从甲地到乙地有2条路，从乙地到丙地有3条路，从丙地到丁地也有2条路。问：从甲地经乙、丙两地到丁地，共有多少种不同的走法？第五页，共13页。排列组合问题排列及计算公式从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!(规定0!=1).2．组合及计算公式从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叶做从n个不同元素中取出m个元素的组合数.用符号c(n,m)表示.c(n,m)=p(빮,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m);第六页，共13页。排列组合练习题1.一个班级有45名同学，从中任意选取2名同学参加作文比赛，共有多少种不同的选法？2.5个同学到饭堂排队打饭，共有多少种不同的排队方法？3.用0，1，2，3，4组合可以得到多少个无重复数字的四位数？4.两条平行的直线L1和L2，L1上有3个点，L2上有5个点，问由这些点总共可以组成多少个三角形？5.书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_____种。满足A必须比C靠左，址有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有______种摆法。

第七页，共13页。集合集合：由确定的、互相区别的一些对象组成的总体。集合的每个对象称为元素。如初一〔11〕班同学组成一个集合，里面的每个同学称为元素。常用的集合表示法：列举法、描述法集合的运算：并〔∪〕、交〔∩〕、差〔-〕、补〔~或ˉ〕

第八页，共13页。集合运算例题设全集I={0,1,2,3,4,5,6,7,8,9}，A={2,4}，B={4,5,6,7}，C={0,8,9}，D={1,2,3}，那么A∪B=A∪B∪C∪D=A∩B=A-B=B-A=C-A=~A=B=第九页，共13页。集合问题的图示法文氏图：由矩形、圆形及内部的点组成。

矩形：其内部的点表示全集的所有元素；

矩形内的圆〔或其它闭曲线〕：表示不同的集合；

圆〔或闭曲线〕内部的点：表示相应集合的元素。第十页，共13页。文氏图例题某单位的100名员工进展调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，那么只喜欢看电影的有：

A、22人B、28人C、30人D、36人第十一页，共13页。文氏图练习有47本书，有27本是小说，32本是红皮的，6不既不是红皮的，也不是小说。问有多少本红皮小说？某班50人，语文、数学考试中，语文及格45人，数学及格42人，两门都不及格2人，那么两门都不及格有多少人？外语学校有英语、法语、日语教师总共27人，其中只能教英语的有8人，只能教日语的有6人，能教英