NOIP初赛数学知识点.ppt

初赛知识复****初赛试题形式●初赛:初赛全部为笔试,满分100分。试题由四部分组成:1、选择题:共20题,,共计30分。每题有5个备选答案,前10个题为单选题(即每题有且只有一个正确答案,选对得分),后10题为不定项选择题(即每题有1至5个正确答案,只有全部选对才得分)。2、问题求解题:共2题,每题5分,共计10分。试题给出一个叙述较为简单的问题,要求学生对问题进行分析,找到一个合适的算法,并推算出问题的解。考生给出的答案与标准答案相同,则得分:否则不得分。3、程序阅读理解题:共4题,每题8分,共计32分。题目给出一段程序(不一定有关于程序功能的说明),考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致,则得分;否则不得分。4、程序完善题:共2题,每题14分,共计28分。题目给出一段关于程序功能的文字说明,然后给出一段程序代码,在代码中略去了若干个语句或语句的一部分并在这些位置给出空格,要求考生根据程序的功能说明和代码的上下文,填出被略去的语句。填对则得分;否则不得分。信息学竞赛中的数学知识◆集合的运算◆排列与组合◆集合及其运算1、集合的运算:并、交、补、差2、容斥原理1、集合的运算:并、交、补、差并:∪交:∩补:^或~或差:-ABABAABA∪BA∩BA-B8. (NOIP9)设全集E={1,2,3,4,5},集合A={1,4},B={1,2,5},C={2,4},则集合(A∩B)∪~C为(   e  )。  A)空集   B){1}   C){3,5}   D){1,5}    E){1,3,5}1、(NOIP10)设全集I={a,b,c,d,e,f,g},集合A={a,b,c},B={b,d,e},C={e,f,g},那么集合为(a)。A.{a,b,c,d}B.{a,b,d,e}C.{b,d,e}D.{b,c,d,e}E.{d,f,g}2.(NOIP11)设全集I={a,b,c,d,e,f,g,h},集合B∪A={a,b,c,d,e,f},C∩A={c,d,e},A∩~B={a,d},那么集合C∩B∩A为(a)。A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}2、容斥原理在计数时,为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是: 先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。对有限集合S,用表示S的元素个数容斥原理的第一形式:设A,B是有限集合,则容斥原理的第二形式:设A、B、C是有限集合,则1、(NOIP10)75名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其中20人这三种东西都玩过,55人至少玩过其中的两种。若每样乘坐一次的费用是5元,游乐场总共收入700,可知有10名儿童没有玩过其中任何一种。2、某学校足球队有球衣30件,篮球队有球衣15件,排球队有球衣18件,三队队员总数为50人,其中有2人同时参加3个队,那么同时只参加两个队的队员有多少?93、分母是1001的最简分数一共有多少个?只是玩过其中两种的有55-20=35人只是玩过其中一种人所花费用700-20*(5*3)-35*(5*2)=50元只是其中一种的人数50÷5=10人没有玩过其中任何一种的人数75-20-35-10=10人容斥原理A+B+C-(A与B重合-A与C重合-B与C重合)+A、B、C重合=总数30+15+18-(A与B重合-A与C重合-B与C重合)+2=50(A与B重合-A与C重合-B与C重合)=30+15+18+2-50=15人15-2*3=9人1001=7×11×13分子中不能含有质因数7、11、13即1至1001中,不能被7、11、13整除的数有多少个?1001÷7=1431001÷11=911001÷13=771001÷[7,11]=13,[7,11]----7和11的最小公倍数1001÷[7,13]=11,-------1001÷[11,13]=7,-----1001÷[7,11,13]=1143+91+77-(13+11+7)+1=281个不能被7,11,13整除的数有1001-281=720个◆排列与组合