《信息学竞赛中数学知识.ppt》由会员分享，可在线阅读，更多相关《信息学竞赛中数学知识.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息学竞赛中的信息学竞赛中的数学知识数学知识2020/12/181逻辑代数逻辑代数n主要掌握主要掌握辑代数的逻辑运算，逻辑运算和辑代数的逻辑运算，逻辑运算和Pascal中的逻辑运算相似，只不过符号不同而已。中的逻辑运算相似，只不过符号不同而已。n逻辑代数的运算符和逻辑代数的运算符和Pascal的运算符有如下对应关系：的运算符有如下对应关系：NOT（非）（非）：OR（或）（或）：AND（与）（与）它们的运算顺序和它们的运算顺序和Pascal中的规定是一致的，中的规定是一致的，“非非”优先级最高，优先级最高，“或或”最低。怎么来记忆符号最低。怎么来记忆符号和优先级顺序和优先级顺序?2020/12/
2、182逻辑代数运算练习题逻辑代数运算练习题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)B2020/12/183排列组合问题排列组合问题n此处我们只讨论最简单的排列组合问题。此处我们只讨论最简单的排列组合问题。n
3、乘法原理：完成一件事可以分为乘法原理：完成一件事可以分为n个步骤，每个步骤又可分为个步骤，每个步骤又可分为a1,a2,a3，an个不同的方个不同的方法，则完成此事的总方法有法，则完成此事的总方法有a1a2a3an种方法。种方法。n加法原理：如果完成一件任务有加法原理：如果完成一件任务有n类方法，在第一类方法中有类方法，在第一类方法中有m1种不同方法，在第二类方法种不同方法，在第二类方法中有中有m2种不同方法种不同方法在第在第n类方法中有类方法中有mn种不同方法，那么完成这件任务共有种不同方法，那么完成这件任务共有N=m1+m2+mn2020/12/184排列组合问题n加法原理典型例题：加法原理
4、典型例题：从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中火车有从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中火车有4班，汽车有班，汽车有3班，轮船有班，轮船有2班。问：一天中乘坐这些交通工具从甲地到乙地，共有多少种不同走法？班。问：一天中乘坐这些交通工具从甲地到乙地，共有多少种不同走法？n乘法原理典型例题：乘法原理典型例题：从甲地到乙地有从甲地到乙地有2条路，从乙地到丙地有条路，从乙地到丙地有3条路，从丙地到丁地也有条路，从丙地到丁地也有2条路。问：从甲地经条路。问：从甲地经乙、丙两地到丁地，共有多少种不同的走法？乙、丙两地到丁地，共有多少种不同的走法？2020/1
5、2/185排列组合问题n排列及计算公式排列及计算公式从从n个不同元素中，任取个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从个元素按照一定的顺序排成一列，叫做从n个不同元素中取出个不同元素中取出m个个元素的一个排列；从元素的一个排列；从n个不同元素中取出个不同元素中取出m(mn)个元素的所有排列的个数，叫做从个元素的所有排列的个数，叫做从n个不同元素中取个不同元素中取出出m个元素的排列数，用符号个元素的排列数，用符号p(n,m)表示表示.p(n,m)=n(n-1)(n-2)(n-m+1)=n!/(n-m)!(规定规定0!=1).n2组合及计算公式组合及计算公式从从n个不同元素中
6、，任取个不同元素中，任取m(mn)个元素并成一组，叫做从个元素并成一组，叫做从n个不同元素中取出个不同元素中取出m个元素的一个组合；个元素的一个组合；从从n个不同元素中取出个不同元素中取出m(mn)个元素的所有组合的个数，叶做从个元素的所有组合的个数，叶做从n个不同元素中取出个不同元素中取出m个元素的组合个元素的组合数数.用符号用符号c(n,m)表示表示.c(n,m)=p(,m)/m!=n!/(n-m)!*m!)；c(n,m)=c(n,n-m);2020/12/186排列组合练习题n1.一个班级有一个班级有45名同学，从中任意选取名同学，从中任意选取2名同学参加作文比赛，共有多少种不同的选法？
7、名同学参加作文比赛，共有多少种不同的选法？n2.5个同学到饭堂排队打饭，共有多少种不同的排队方法？个同学到饭堂排队打饭，共有多少种不同的排队方法？n3.用用0，1，2，3，4组合可以得到多少个无重复数字的四位数？组合可以得到多少个无重复数字的四位数？n4.两条平行的直线两条平行的直线L1和和L2，L1上有上有3个点，个点，L2上有上有5个点，问由这些点总共可以组成多少个个点，问由这些点总共可以组成多少个三角形？三角形？n5.书架上有书架上有4本不同的书本不同的书A、B、C、D。其中。其中A和和B是红皮的，是红皮的，C和和D是黑皮的。把这是黑皮的。把这4本书摆本书摆在书架上，满足所有黑皮的书都排
8、在一起的摆法有在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足种。满足A必须比必须比C靠左，址有红靠左，址有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有_种摆法。种摆法。2020/12/187集合n集合：由确定的、互相区别的一些对象组成的总体。集合的每个对象称为元素。如初一（11）班同学组成一个集合，里面的每个同学称为元素。n常用的集合表示法：列举法、描述法n集合的运算：并（）、交（）、差（-）、补（或）2020/12/188集合运算例题集合运算例题 设全集I=0,1,2,3,4,5,6,7,8,9，A=2,4，B=4,5,6,7
9、，C=0,8,9，D=1,2,3，则AB=A B C D=AB=A-B=B-A=C-A=A=B=2020/12/189集合问题的图示法n文氏图：由矩形、圆形及内部的点组成。矩形：其内部的点表示全集的所有元素；矩形内的圆（或其它闭曲线）：表示不同的集合；圆（或闭曲线）内部的点：表示相应集合的元素。2020/12/1810文氏图例题n某单位的某单位的100名员工进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中名员工进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球人喜欢看球赛，赛，38人喜欢看戏剧，人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有人喜欢看电影，既喜欢看球
10、赛又喜欢看戏剧的有18人，既喜欢看电人，既喜欢看电影又喜欢看戏剧的有影又喜欢看戏剧的有16人，三种都喜欢看的有人，三种都喜欢看的有12人，则只喜欢看电影的有：人，则只喜欢看电影的有：A、22人人B、28人人C、30人人D、36人人2020/12/1811文氏图练习n有有47本书，有本书，有27本是小说，本是小说，32本是红皮的，本是红皮的，6不既不是红皮的，也不是小说。问有多少本红不既不是红皮的，也不是小说。问有多少本红皮小说？皮小说？n某班某班50人，语文、数学考试中，语文及格人，语文、数学考试中，语文及格45人，数学及格人，数学及格42人，两门都不及格人，两门都不及格2人，则两门人，则两门都不及格有多少人？都不及格有多少人？n外语学校有英语、法语、日语老师总共外语学校有英语、法语、日语老师总共27人，其中只能教英语的有人，其中只能教英语的有8人，只能教日语的有人，只能教日语的有6人，人，能教英语、日语的有能教英语、日语的有5人，能教法语、日语的有人，能教法语、日语的有3人，能教英、法语的有人，能教英、法语的有4人，三种都能教的人，三种都能教的有有2人，则只能教法语的有：人，则只能教法语的有：A、4人人B、5人人C、6人人D、7人人2020/12/1812