NOIP初赛数学知识点

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,NOIP初赛数学知识点,NOIP初赛数学知识点NOIP初赛数学知识点初赛试题形式,初赛：初赛全部为笔试，满分100分。试题由四部分组成：,1、选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题(即每题有且只有一个正确答案，选对得分)，后10题为不定项选择题(即每题有1至5个正确答案，只有全部选对才得分)。,2、问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。,3、程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序(不一定有关于程序功能的说明)，考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。,4、程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。,初赛试题形式,初赛：初赛全部为笔试，满分,100,分。试题由四部分组成：,1,、选择题：共,20,题，每题分，共计,30,分。每题有,5,个备选答案，前,10,个题为单选题,(,即每题有且只有一个正确答案，选对得分,),，后,10,题为不定项选择题,(,即每题有,1,至,5,个正确答案，只有全部选对才得分,),。,2,、问题求解题：共,2,题，每题,5,分，共计,10,分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。,3,、程序阅读理解题：共,4,题，每题,8,分，共计,32,分。题目给出一段程序,(,不一定有关于程序功能的说明,),，考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。,4,、程序完善题：共,2,题，每题,14,分，共计,28,分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。,信息学竞赛中的数学知识,集合的运算, 排列与组合,集合及其运算,1,、集合的运算：并、交、补、差,2,、容斥原理,1,、集合的运算：并、交、补、差,并：,交：,补：,或或,差,: -,A,B,A,B,A,A,B,A B,A B,A-B,8.,（,NOIP9,）设全集,E=1,，,2,，,3,，,4,，,5,，集合,A=1,，,4,，,B=1,，,2,，,5,，,C=2,，,4,，则集合（,A B,）,C,为（,e,）。,A,） 空集,B,）,1C,）,3,，,5D,）,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,，,集合,BA= a, b, c, d, e, f,，,C A= c, d, e,，,AB = 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,个队，那么同时只参加两个队的队员有多少？,9,、分母是,1001,的最简分数一共有多少个？,只是玩过其中两种的有,55-20=35,人,只是玩过其中一种人所花费用,700-20*,（,5*3,）,-35*,（,5*2,）,=50,元,只是其中一种的人数,505=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=71113,分子中不能含有质因数,7,、,11,、,13,即,1,至,1001,中，不能被,7,、,11,、,13,整除的数有多少个？,10017=143,100111=91,100113=77,10017,11=13, 7,11-7,和,11,的最小公倍数,10017,13=11, -,100111,13=7, -,10017,11,13=1,143+91+77-(13+11+7)+1=281,个,不能被,7,，,11,，,13,整除的数有,1001-281=720,个,排列与组合,1.,排列的定义,:,从,n,个不同元素中,任取,m,个元素,按照一定的顺序排成一列,叫做从,n,个不同元素中取出,m,个元素的一个排列,.,排列数公式,:,全排列问题：,n,个不同的元素排成一排，排列方法有：,=n*(n-1)*(n-2)*2*1=n!,2.,组合的定义,:,从,n,个不同元素中,任取,m,个元素,并成一组,叫做从,n,个不同元素中取出,m,个元素的一个组合,.,组合数公式,:,排列与组合的区别与联系,:,与顺序有关的为排列问题,与顺序无关的为组合问题,.,加法原理和乘法原理,从,A,到,C,共有多少中走法？,A,B,C,例,1,:,学校师生合影，共,8,个学生，,4,个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？,解,先排学生共有 种排法,然后把老师插入学生之间的空档，共有,7,个空档可插,选其中的,4,个空档,共有 种选法,.,根据乘法原理,共有的不同坐法为 种,.,结论,1,插入法,:,对于某两个元素或者几个元素要求不相邻的问题,可以用插入法,.,即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可,.,例,2 :,5,个男生,3,个女生排成一排,3,个女生要排在一起,有多少种不同的排法,?,解,因为女生要排在一起,所以可以将,3,个女生看成是一个人,与,5,个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法,.,结论,2,捆绑法,:,要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题,.,即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列,.,例,3,:,袋中有不同年份生产的,5,分硬币,23,个,不同年份生产的,1,角硬币,10,个,如果从袋中取出,2,元钱,有多少种取法,?,解,把所有的硬币全部取出来,将得到 元,所以比,2,元多元,所以剩下元即剩下,3,个,5,分或,1,个,5,分与,1,个,1,角,所以共有 种取法,.,结论,3,剩余法,:,在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法,.,分析,此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来,.,但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题,.,例,4,学校安排考试科目,9,门,语文要在数学之前考,有多少种不同的安排顺序,?,解,不加任何限制条件,整个排法有 种,“,语文安排在数学之前考,”,与,“,数学安排在语文之前考,”,的排法是相等的,所以语文安排在数学之前考的排法共有 种,.,结论,4,对等法,:,在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一,.,在求解中只要求出全体,就可以得到所求,.,分析,对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了,.,并且也避免了问题的复杂性,.,例,5,某个班级共有,43,位同学,从中任抽,5,人,正、副班长、团支部书记至少有一人在内的抽法有多少种,?,解,43,人中任抽,5,人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有,1,人在内的抽法有 种,.,结论,5,排异法,:,有些问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中排除,.,分析,此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况,.,而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便,.,这样就可以简化计算过程,.,圆周排列：,从,n,个不同的元素中取,r,个沿一圆周排列，排列的方案：,/r,N,个元素的圆周排列：,/n,=,（,n-1,）,!,有重复元素的排列问题：,如：,n,1,个,a,，,n,2,个,b,，,n,3,个,c,，排成一排，有多少种排列方法。,1.,（,NOIP7,）平面上有三条平行直线，每条直线上分别有,7,，,5,，,6,个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？,2250,2,、 （,NOIP10,）由,3,个,a,，,5,个,b,和,2,个,c,构成的所有字符串中，包含子串“,abc”,的共有（ ）个。,A. 40320 B. 39600,由,3,个,a,，,5,个,b,和,2,个,c,构成的所有字符串中，包含子串“,abc”,的共有,C. 840 D. 780 E. 60,当,abc,在第一位时,后面一共有,105,种排列,(7!/(2!*4!)=105),当,abc,在第二位时,也是,105,种,.,当,abc,在第八位时,也是,105.,105*8=840,种里面有重复的,减去有,2,个字字串,abc,的,.,一共,60,种,(6!/(2!*3!)=60),所以,840-60=780,种,1,(NOIP8),在书架上放有编号为,1,，,2,，,n,的,n,本书。现将,n,本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：,n = 3,时：,原来位置为：,1 2 3,放回去时只能为：,3 1 2,或,2 3 1,这两种,问题：求当,n = 5,时满足以上条件的放法共有多少种？（不用列出每种放法）,44,错排问题：,n,个不同元素的错排问题：,如：,1,，,2,，,3,，。，,n,的错排问题，,i,不在第,i,个位置的排列方法。,分析：,设,f(n),为,n,个不同元素的错排方案。,第一部分：,n,先不动，把另外的,n-1,个数错排，方案是：,f,（,n-1,），然后,n,和另外的,n-1,个每一个交换，共有,(n-1)*f(n-1),种方案。,第二部分：,n,和其他的,n-1,个之一交换，其余的,n-2,个错排，共有,（,n-1,）*,f,（,n-2,）种方案。,由加法原理：,f(n)=(n-1)*(f(n-1)+f(n-2),f(1)=0;f(2)=1;,错排的计算公式：,几类重要的递推关系：,一、第二类,Stirling,数,问题一：放置小球,n,个有区别的球放到,m,个相同的盒子中，要求无一空盒，其不同的方案数用,S(n,m),表示，称为第二类,Stirling,数,设有,n,个不同的球，分别用,b1,b2,bn,表示。从中取出一个球,bn,，,bn,的放法有以下两种：,1)bn,独自占一个盒子；那么剩下的球只能放在,m-1,个盒子中，方案数为,S(n-1,m-1),2)bn,与别的球共占一个盒子；那么可以事先将,b1,b2,bn-1,这,n-1,个球放入,m,个盒子中，然后再将球,bn,可以放入其中一个盒子中，方案数为,m*S(n-1,m),S(n,m)=m*S(n-1,m)+S(n-1,m-1) (n1,m1),边界条件：,S(n,1)=1,；,S(n,n)=1,；,S(n,k)=0(kn),问题二：集合划分问题。,设,S,是一个包含,n,个元素的集合，,S=b1,b2,b3,bn,现需要将,S,集合划分为,m,个满足如下条件的集合,S1,S2, Sm,。,Si;,SiSj=;,S1S2Sm=S; (1=I ,j=m),则称,S1,S2, ,Sm,是,S,的一个划分。,编程：输入,n,和,m,的值，输出不同的划分方案数。,要求：输入数据有一行，第一个数是,n,第二个数,m,。,样例：,输入：,4 3,输出：,6,noip13,1,给定,n,个有标号的球，标号依次为,1,，,2,，,，,n,。将这,n,个球放入,r,个相同的盒子里，不允许有空盒，其不同放置方法的总数记为,S(n,r),。例如，,S(4,2)=7,，这,7,种不同的放置方法依次为,(1),(234), (2),(134), (3),(124), (4),(123), (12),(34), (13),(24),(14),(23),。当,n=7,r=4,时，,S(7,4)= _350_,递推公式,S(n,r)=S(n-1,r)*r+S(n-1,r-1).,因为把,n,个球放入,r,个箱子,相当于先把,n-1,个球放好再放最后一个,.,最后一个有两种放法：放入前面已经有球的箱子或者独占一个箱子,.,前者对应,S(n-1,r)*r (,放入每一个不同的箱子都是一种不同的放法,因为箱子内原来的球不同,),后者对应,S(n-1,r-1).,二、,Catalan,数,问题一：凸,n,边形的三角形剖分,在一个凸,n,边形中，通过不相交于,n,边形内部的对角线，把,n,边形拆分成若干三角形，不同的拆分数目用,f(n),表之，,f(n),即为,Catalan,数。例如五边形有如下五种拆分方案，故,f(5)=5,。求对于一个任意的凸,n,边形相应的,f(n),。,区域是一个凸,k,边形，区域是一个凸,n-k+1,边形，,区域的拆分方案总数是,f(k),；,区域的拆分方案数为,f(n-k+1),；,故包含,P,1,P,k,P,n,的,n,边形的拆分方案数为,f(k)* f(n-k+1),种,F(n)=,问题二：二叉树数目,问题描述：求,n,个结点能构成不同二叉数的数目。,【,问题分析,】,：,设,F(n),为,n,个结点组成二叉树的数目。,容易知道：,f(1)=1; f(2)=2, f(3)=5,选定其中,1,个结点为根，左子树结点的个数为,i,，二叉树数目,f,（,i,）种；右子树结点数目为,n-i-1,，二叉树数目,f,（,n-i-1,）种，,I,的可取范围,0,，,n-1,。所以有：,F(n)=,为了计算的方便：约定,f,（,0,）,=1,问题三：出栈序列,问题描述：,N,个不同元素按一定的顺序入栈，求不同的出栈序列数目。,【,问题分析,】,：,设,f,（,n,）为,n,个元素的不同出栈序列数目。,容易得出：,f,（,1,）,=1,；,f,（,2,）,=2,。,第,n,个元素可以第,i,（,1=i=n,）个出栈，前面已出栈有,i-1,个元素，出栈方法：,f,（,i-1,）；后面出栈,n-i,个元素，出栈方法为：,f,（,n-i,）。所以有：,F(n)=,三、集合取数问题,1,、设,f(n,k),是从集合,1,，,2,，。，,n,中能够选择的没有两个连续整数的,k,个元素子集的数目，求递归式,f(n,k),。,【,问题分析,】,：,N,有两种情况：, 当,n,在子集时，则,n-1,一定不在子集中，即在,1,，,2,，。，,n-2,中选,k-1,个元素，数目为,f(n-2,k-1),。, 当,n,不在子集中时，则在,1,，,2,，。，,n-1,中选,k,个元素，数目为,f(n-1,k),。,所以：,f(n,k)= f(n-2,k-1) +f(n-1,k),边界条件：,F(n,1)=n, f(n,k)=0 ( n=k),四、整数划分问题,1,、将整数,n,分成,k,份，且每份不能为空，任意两种分法不能相同,(,不考虑顺序,),。例如：,n=7,，,k=3,，下面三种分法被认为是相同的。,1,，,1,，,5; 1,，,5,，,1; 5,，,1,，,1;,问有多少种不同的分法。输入：,n,，,k (6n=200,，,2=k=2,，可以先那出,j,个,1,分到每一份，然后再把剩下的,i-j,分成,j,份即可，分法有：,f(i-j,j).,2) : j,份中至少有一份为,1,的分法，可以先那出一个,1,作为单独的,1,份，剩下的,i-1,再分成,j-1,份即可，分法有：,f(i-1,j-1).,所以,：,f(,i,j)= f(,i,-j,j)+ f(,i,-1,j-1),边界条件：,f,（,i,，,1,）,=1,，,f,（,i,，,j,）,=0,， （,ij,）,2,、自然数,n,的拆分方案。,n=5,拆分数,6,n=6,拆分数,10,n=7,拆分数,14,1:5=1+4,2:5=1+1+3,3:5=1+1+1+2,4:5=1+1+1+1+1,5:5=1+2+2,6:5=2+3,用母函数法：,当,n=5,时：,构造母函数如下：,F(x)=(x,0,+x,1,+x,2,+x,3,+x,4,+x,5,)(x,2,0,+x,2,1,+x,2,2,)(x,3,0,+x,3,1,),(x,4,0,+x,4,1,)(x,5,0,+x,5,1,),=(1+x+x,2,+x,3,+x,4,+x,5,)(1+x,2,+x,4,)(1+x,3,)(1+x,4,)(1+x,5,),=1+x+2x,2,+3x,3,+5x,4,+7x,5,+,项,aiX,i,的系数,ai,，,ai-1,即自然数,i,的拆分数,.,减,1,是因为包含了,i=i,的一种拆分方案。,采用,a,b,c,三个数组，,a,：被乘数，,b,：乘数，,c,：乘积。,多个多项式采用逐次相乘的方法。每次借助,k,从,b,中取项。,3,、将整数,n,分成,k,份，且每份不能为空，且最大值不超过,m,的分法 。任意两种分法不能相同,(,不考虑顺序,),。,重复元素的组合问题：,从,n,种不同的元素中取,r,个的元素的组合，允许有重复元素的组合：,典型模型：,r,个相同的小球，放到,n,个不同的盒子里，所有的放置方法。,r,个相同的球放入,n,个不同的盒子,条件可以变成,:,n+r,个球放入,n,个盒子,每个盒子最少放,1,个球,.,用插空法,:,n+r,个球之间有,n+r-1,个空,插,n-1,个隔板进去,有,C(n-1,n+r-1)=C(r,n+r-1,）个组合,Thank You,世界触手可及,携手共进，齐创精品工程,