初中信息学竞赛中的数学知识-2018

信息学竞赛中的数学知识⼩结信息学竞赛中的数学知识简要梳理信息学竞赛经常涉及⼀些数学知识。

现在梳理⼀下。

⽬录1组合数学：1.1排列与组合1.2母函数1.3⼆项式定理1.4容斥原理1.5鸽巢原理1.6群论（特别是置换群）1.7Burnside引理与Polya定理2线性代数：2.1矩阵定义及运算2.2⾼斯消元解线性⽅程组2.3Matrix-Tree定理3数论：3.1扩展欧⼏⾥得3.2逆元3.3解模意义下⽅程3.4莫⽐乌斯反演3.5Miller-Rabin素数测试3.6Pollard-Rho 因⼦分解3.7BSGS 离散对数4博弈论：4.1组合游戏4.2GS函数和GS定理5数值运算：5.1Simpson 启发式积分1组合数学：1.1排列与组合n个不同元素，其所有排列个个数：全排列n个不同元素，选出m个来做全排列，排列数：n个不同元素，选出m个的组合数：n个元素，有m种，第i种有n i个，每种则所有元素的排列数：n种元素，每种有⽆限多个，选出r个（可重复）的⽅案数（⽤夹棍法理解）：n个不同元素，选出m个，且每个都不相邻：1.2母函数母函数是⼀个函数，该函数有⽆限多项，且具有下⾯的形式：这样，⼀个母函数的的各项的系数就可以组成⼀个数列，并且任意⼀个数列都和母函数⼀⼀对应，对数列的研究就可以⽤母函数来帮忙了（还需要⽜顿⼆项式定理来推导某些特殊级数的有限多项式表⽰）。

1.3⼆项式定理1.4容斥原理：思想是：“统计所有的，减去多统计的，加上多减的，再减去多加的…”。

由德摩根定理：所以：这样，我们不光可以⽤容斥定理来统计“满⾜a，或满⾜b，或满⾜c…”的元素的个数，也可以⽤来统计“不满⾜a并且不满⾜b并且不满⾜c”的元素的个数。

1.5鸽巢原理：将n只鸽⼦放到n-1个巢中，⾄少有⼀个巢有⼤于⼀只鸽⼦。

很显然的事情，但是⽤它的题⽬却不是那么显然，需要我们不断的强化问题（加更多⾃⼰的限制）。

我见过的⽤处是：给出n 个⾃然数，找出其中⼀堆，使得他们的和为n的倍数。

信息学竞赛知识点一、知识概述《算法复杂度》①基本定义：算法复杂度就是用来衡量算法执行效率的东西。

简单说就是算法执行时要花多少时间、多少内存之类的资源。

时间复杂度就看算法要运行多久，空间复杂度就看算法运行时占用多少内存空间。

②重要程度：在信息学竞赛里这可是相当重要的。

就好比盖房子得考虑用多少材料花多少时间一样，要衡量一个算法好不好用，复杂度是重要的标准。

要是复杂度太高，程序可能就运行得很慢或者占用太多内存而没法正常运行。

③前置知识：得先知道一些基本的算法操作，像循环、条件判断这些，还得知道数据结构里的数组、链表等基础知识，因为算法复杂度离不开对这些操作和结构的分析。

④应用价值：在设计软件或者解决实际数据处理问题的时候，我们通过分析算法复杂度可以选择出更高效的算法。

比如说处理大量用户订单信息，用复杂度低的算法就能更快地完成任务，让用户体验更好。

二、知识体系①知识图谱：算法复杂度在信息学里就像一个衡量工具。

在整个算法知识体系里，它是评估算法性能的重要依据。

无论写什么算法，最后都得考虑复杂度问题。

②关联知识：和数据结构紧密联系。

不同的数据结构会影响算法的复杂度。

比如用数组和用树结构来存储数据做搜索操作时，复杂度可能就不一样。

跟算法优化也有关联，如果一个算法复杂度太高，可以通过优化算法或者更换数据结构来降低复杂度。

③重难点分析：- 掌握难度：说实话，对于新手来说有点难理解。

像大O表示法那种抽象的表示方式不好懂。

但是只要多做例子，逐渐就能有感觉。

- 关键点：关键是能够准确分析算法里每个操作的数量级，像循环嵌套了几层，每次循环里又做了多少操作等。

④考点分析：- 在考试中的重要性：超级重要。

无论是初赛考察概念，还是复赛考察算法优化，总能涉及到算法复杂度。

- 考查方式：可能直接问某个算法的时间复杂度或者空间复杂度；也可能给一段代码让你分析复杂度；或者给你复杂度的要求让你设计满足要求的算法。

三、详细讲解（这里当作理论概念类）①概念辨析：- 时间复杂度：主要是看算法执行基本操作（比如比较、赋值这些简单操作）的次数随着数据规模（比如输入的数据量大小）的增长趋势。

初中信息学竞赛中的数学知识逻辑代数• 主要掌握逻辑代数的逻辑运算，逻辑运算和主要掌握逻辑代数的逻辑运算， Pascal中的逻辑运算相似，只不过符号不同而已。

中的逻辑运算相似，中的逻辑运算相似只不过符号不同而已。

• 逻辑代数的运算符和逻辑代数的运算符和Pascal的运算符有如下对应的运算符有如下对应关系：关系：┓：not（非）（∨：OR（或）（∧：AND（与）（它们的运算顺序和Pascal中的规定是一致的。

中的规定是一致的。

它们的运算顺序和中的规定是一致的逻辑代数P True True False False P True False Q True False True False P∨Q ∨ True True True False ┓P False True P∧Q True False False False 逻辑代数运算练习题设A=TRUE，B=FALSE，C=TRUE，，，， D=FALSE，求以下逻辑运算的结果：，求以下逻辑运算的结果：A ∨ B ∧ C=( ) ) ┓C ∧ A=( A ∧B ∨ C ∧D=( )排列组合问题• 此处我们只讨论最简单的排列组合问题。

此处我们只讨论最简单的排列组合问题。

• 乘法原理：完成一件事可以分为n个步骤，每个乘法原理：完成一件事可以分为个步骤，个步骤步骤又可分为a1,a2,a3，…，an个不同的方法，个不同的方法，步骤又可分为，，个不同的方法则完成此事的总方法有a1×a2×a3×…×an种方则完成此事的总方法有a1×a2×a3×…×an种方法。

• 加法原理：如果完成一件任务有类方法，在第加法原理：如果完成一件任务有n类方法类方法，一类方法中有m1种不同方法种不同方法，一类方法中有种不同方法，在第二类方法中有 m2种不同方法……在第类方法中有在第n类方法中有种不同种不同方法在第类方法中有mn种不同方法，那么完成这件任务共有N=m1+m2+…+mn 方法，那么完成这件任务共有排列组合问题• 加法原理典型例题：加法原理典型例题：从甲地到乙地，可以乘火车，也可以乘汽车，从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。

信息学竞赛中的数学知识与应用技巧信息学竞赛在培养学生的计算机科学素养和解决问题能力方面起到了关键作用。

然而，我们不能忽视数学在信息学竞赛中的重要性。

本文将探讨数学在信息学竞赛中的知识和应用技巧。

一、离散数学与图论离散数学作为数学的一个重要分支，在信息学竞赛中扮演着重要角色。

图论作为离散数学的一个重要分支，在解决问题时发挥着关键作用。

许多信息学竞赛的问题可以转化为图论问题，因此，掌握好图论的基本概念和算法是至关重要的。

1. 图的表示与遍历在解决图论问题时，首先需要了解图的表示方法。

常用的表示方法有邻接矩阵和邻接表。

使用邻接矩阵可以方便地查找两个节点之间的边的关系，而使用邻接表可以更有效地存储大规模图的信息。

在了解了图的表示方法后，我们需要学会如何遍历图。

常用的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

这两种算法在解决图相关问题时经常用到，对于信息学竞赛非常有帮助。

2. 最短路径和最小生成树最短路径和最小生成树是信息学竞赛中常见的问题类型。

Dijkstra 算法和Floyd算法是解决最短路径问题的经典算法。

Prim算法和Kruskal算法是解决最小生成树问题的经典算法。

熟练掌握这些算法可以帮助我们更好地解决与图相关的问题。

二、概率与统计在信息学竞赛中，概率与统计也是一个重要的数学知识点。

学生需要掌握概率论和统计学的基本概念，以便解决与概率和统计相关的问题。

1. 概率计算与统计分析在解决与概率相关的问题时，我们需要掌握概率的基本计算方法，如加法原理、乘法原理和条件概率等。

此外，对于离散型和连续型随机变量的概率分布函数的掌握也是重要的。

在解决与统计相关的问题时，我们需要掌握统计学的基本概念和统计分析方法。

常见的统计分析方法包括均值、方差、标准差、相关系数和回归分析等。

2. 概率与统计在信息学竞赛中的应用概率与统计在信息学竞赛中的应用非常广泛。

例如，在解决数据压缩、遗传算法和机器学习等问题时，概率与统计的知识经常被用到。

信息学竞赛中的数学知识与应用随着科技的迅速发展，信息学竞赛成为了一项备受关注的知识竞赛。

信息学竞赛不仅考察学生在程序设计、算法等方面的能力，也对数学知识的掌握和应用提出了较高要求。

本文将从数学知识的重要性、数学在信息学竞赛中的应用以及数学的相关准备等方面展开论述。

一、数学知识在信息学竞赛中的重要性信息学竞赛作为一项具有较高难度的比赛，对参赛者的数学基础要求较为严格。

在信息学竞赛中，数学知识可以作为竞赛的基础，起到提升解题能力的作用。

首先，数学基础是理解和掌握计算机科学的基础。

信息学竞赛中，很多问题都需要通过数学的推理和计算来解决。

比如在算法设计和复杂度分析中，掌握好数学原理可以帮助选手更好地理解问题的本质和规律，从而设计出更高效的算法。

其次，数学作为一门逻辑性较强的科学，培养了参赛者的分析和解决问题的能力。

信息学竞赛中，很多题目需要选手进行数学建模和问题抽象，通过数学方法来解决实际问题。

数学训练使得选手能够培养出较强的逻辑思维和问题解决能力，在竞赛中应用数学知识更加得心应手。

另外，信息学竞赛的评判标准中，对于题目的正确性和效率都有较高要求。

数学的推理和计算能力是提高解题效率的关键因素。

例如，在解决图论问题时，对于图的遍历和最短路径算法的理解都离不开数学的支持。

二、数学在信息学竞赛中的应用数学在信息学竞赛中广泛应用于多个领域，包括算法设计、数据结构、图论等。

下面以一些典型的应用进行说明：1. 算法设计：在信息学竞赛中，算法设计是关键的一环。

而对于算法的正确性和效率分析，都需要借助于数学的推理和计算。

例如，对于时间复杂度的分析，需要运用到离散数学中的递推关系和大O表示法。

2. 数据结构：数据结构是信息学竞赛中另一个重要的知识点。

而在数据结构的选择和设计中，数学知识也起着关键的作用。

例如，在树的表示和遍历中，树的数学性质可以帮助选手更好地理解和操作树结构。

3. 图论：图论作为信息学竞赛中经常涉及的领域，也需要借助于数学的知识进行解决。

注意：如果复习时间不够，我们猜他红色部分不考第一节数制及其转换一、二、八、十六进制转十进制的方法：乘权相加法。

例如：（11010110）2 = 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 1×22 + 1×21 + 0×20 = （214）10（2365）8 = 2×83 + 3×82 + 6×81 + 5×80 = （1269）10（4BF）16 = 4×162 + 11×161 + 15×160 = (1215)10带小数的情况：（110.011）2 = 1×22 + 1×21 + 1×20 + 0×2-1 + 1×2-2 + 1×2-3 = （6.375）10（5.76）8= 5×80 + 7×8-1 + 6×8-2 = （5.96875）10（D.1C）16= 13×160+ 1×16-1 + 12*16-2 = （13.109375）10二、十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。

例一：（43）10 = （101011）2例二：（0.375）10 = （0.011）2三、二进制转八进制的方法1位数八进制与二进制对应表转换方法:对二进制以小数点为分隔，往前往后每三位划为一组，不足三位补0，按上表用对应的八进制数字代入即可。

例如：(10111011.01100111) = 010,111,011.011,001,110 = （273.36）8三、二进制转十六进制的方法1位数十六进制与二进制对应表转换方法:对二进制以小数点为分隔，往前往后每四位划为一组，不足四位补0，按上表用对应的十六进制数字代入即可。

信息学竞赛数学知识与应用技巧的案例讲解一、引言在信息学竞赛中，数学知识和应用技巧是非常重要的一部分。

本文将通过案例的形式，分享一些常用的数学知识和应用技巧，帮助读者更好地应对信息学竞赛。

二、组合数学1. 问题描述：某城市有5个公园供市民休息，一天内每个公园只能容纳10人，那么一天内最多能容纳多少人？2. 解决方法：根据排列组合原理，假设每个公园能容纳的人数相互独立，那么一个公园容纳的人数可以有0人、1人、2人、...、10人，即在每个公园上都有11种情况。

而有5个公园，因此一天内最多能容纳的人数为11^5=161051个人。

三、数论1. 问题描述：小明的手机里有一个十进制整数，其各位数字之和是30，且这个整数的奇数位数字之和是偶数位数字之和的3倍，那么这个整数是多少？2. 解决方法：根据数论的知识，一个整数各位数字之和能被3整除，则这个整数也能被3整除。

由题意可知，奇数位数字之和是偶数位数字之和的3倍，那么这个整数只能是偶数位数字都为3的倍数，且各位数字之和是30。

结合题意，我们可以列出以下条件：- 十位数字是3的倍数；- 百位数字是3的倍数；- 千位数字是3的倍数；- 万位数字是3的倍数；- 万位数字加千位数字等于百位数字加十位数字。

通过以上条件，我们可以得到数值为63000的整数符合题意。

四、概率1. 问题描述：一副标准的扑克牌共有52张牌，抽取5张牌，那么抽到一对（两张相同的牌）的概率是多少？2. 解决方法：在一副标准扑克牌中，一共有13种牌面（A、2、3、4、5、6、7、8、9、10、J、Q、K），每种牌面有4张牌。

而抽取一对的条件是抽到2张相同的牌，即有13种牌面中选择1种牌面，再从4张牌中选择2张。

因此，抽到一对的概率为(13C1 * 4C2) / (52C5) ≈0.422569。

五、线性代数1. 问题描述：已知向量a=(1,2,3)和b=(4,5,6)，求向量a和b的数量积。

2. 解决方法：向量的数量积等于对应分量相乘之和。

2018年“TRULY ®信利杯”全国初中数学竞赛试题参考答案和评分标准一、选择题（共5小题，每小题6分，满分30分. 以下每道小题均给出了代号为A ，B ，C ，D 的四个选项，其中有且只有一个选项是正确的. 请将正确选项的代号填入题后的括号里. 不填、多填或错填得零分）1. 已知实数b a ≠，且满足)1(33)1(2+-=+a a ，2)1(3)1(3+-=+b b .则ba a ab b+的值为（ ）. （A ）23 （B ）23- （C ）2- （D ）13- 答：选（B ）∵ a 、b 是关于x 的方程()03)1(312=-+++x x的两个根，整理此方程，得0152=++x x ，∵ 0425>-=∆， ∴ 5-=+b a ，1=ab . 故a 、b 均为负数. 因此()232222-=-+-=+-=--=+abab b a ab abb a ab b a ab a b b a a a b b .2. 若直角三角形的两条直角边长为a 、b ，斜边长为c ，斜边上的高为h ，则有 （ ）.（A ）2h ab = （B ）h b a 111=+ （C ）222111hb a =+ （D ）2222h b a =+ 答：选（C ）∵ 0>>h a ，0>>h b ，∴ 2h ab >，222222h h h b a =+>+； 因此，结论（A ）、（D ）显然不正确.设斜边为c ，则有c b a >+，ab ch h b a 2121)(21=>+，即有 hb a 111>+， 因此，结论（B ）也不正确.由ab h b a 212122=+化简整理后，得222111h b a =+， 因此结论（C ）是正确的. 3．一条抛物线c bx ax y ++=2的顶点为（4，11-），且与x 轴的两个交点的横坐标为一正一负，则a 、b 、c 中为正数的（ ）. （A ）只有a （B ）只有b （C ）只有c （D ）只有a 和b 答：选（A ）由顶点为（4，11-），抛物线交x 轴于两点，知a >0. 设抛物线与x 轴的两个交点的横坐标为1x ，2x ，即为方程02=++c bx ax的两个根.由题设021<x x ，知0<ac，所以0<c . 根据对称轴x =4，即有02>-a b，知b <0.故知结论（A ）是正确的.4．如图所示，在△ABC 中，DE ∥AB ∥FG ，且FG 到DE 、AB 的距离之比为1:2. 若△ABC 的面积为32，△CDE 的面积为2，则△CFG的面积S等于（ ）.（A ）6 （B ）8 （C ）10 （D ）12 答：选（B ）由DE ∥AB ∥FG 知，△CDE ∽△CAB ，△CDE ∽△CFG ，所以41322===∆∆CAB CDE S S CACD， 又由题设知21=FA FD ，所以 31=AD FD ， AC AC AD FD 41433131=⨯==，故DC FD =，于是41212=⎪⎭⎫ ⎝⎛=∆∆CFG CDE S S ，8=∆CFG S . 因此，结论（B ）是正确的.（第4题图）5．如果x 和y 是非零实数，使得3=+y x 和03=+x y x ，那么x +y 等于（ ）.（A ）3 （B ）13 （C ）2131- （D ）134- 答：选（D ）将x y -=3代入03=+x y x ，得0323=+-x x x .（1）当x >0时，0323=+-x x x ，方程032=+-x x 无实根； （2）当x <0时，0323=--x x x ，得方程032=--x x 解得2131±=x ，正根舍去，从而2131-=x . 于是2137213133-=-+=-=x y . 故134-=+y x .因此，结论（D ）是在正确的.二、填空题（共5小题，每小题6分，满分30分） 6． 如图所示，在△ABC 中，AB =AC ，AD =AE ，︒=∠60BAD ，则=∠EDC （度）. 答：30°解：设α2=∠CAD ，由AB =AC 知αα-︒=-︒-︒=∠60)260180(21B ，α+︒=︒-∠-︒=∠6060180B ADB ， 由AD =AE 知，α-︒=∠90ADE ， 所以︒=∠-∠-︒=∠30180ADB ADE EDC .7．据有关资料统计，两个城市之间每天的电话通话次数T 与这两个城市的人口数m 、n （单位：万人）以及两城市间的距离d （单位：km ）有2d kmnT =的关系(k 为常数) . 现测得A 、B 、C 三个城市的人口及它们之间的距离如图所示，且已知A 、B 两个城市间每天的电话通话次数为t ，那么B 、C 两个城市间每天的电话通话次数为 次（用t 表示）.答：2t（第6题图）解：据题意，有k t 21608050⨯=， ∴t k 532=. 因此，B 、C 两个城市间每天的电话通话次数为2645532320100802tt k T BC =⨯=⨯⨯=. 8．已知实数a 、b 、x 、y 满足2=+=+y x b a ，5=+by ax ，则=+++)()(2222y x ab xy b a .答：5-解：由2=+=+y x b a ，得4))((=+++=++bx ay by ax y x b a ， ∵ 5=+by ax ， ∴ 1-=+bx ay .因而，5))(()()(2222-=++=+++by ax bx ay y x ab xy b a . 9． 如图所示，在梯形ABCD 中，AD ∥BC (BC >AD )，︒=∠90D ，BC =CD =12, ︒=∠45ABE ，若AE =10，则CE 的长为 . 答：4或6解：延长DA 至M ，使BM ⊥BE . 过B 作BG ⊥AM ，G 为垂足.易知四边形BCDG 为正方形， 所以BC =BG . 又GBM CBE ∠=∠， ∴ Rt △BEC ≌Rt △BMG .∴ BM =BE ，︒=∠=∠45ABM ABE ， ∴△ABE ≌△ABM ，AM =AE =10.设CE =x ，则AG =x -10，AD =x x -=--2)10(12，DE =x -12. 在Rt △ADE 中，222DE AD AE +=， ∴ 22)12()2(100x x -++=， 即024102=+-x x ， 解之，得41=x ，62=x .（第9题图）（第7题图）故CE 的长为4或6.10．实数x 、y 、z 满足x+y +z =5，xy +yz +zx =3，则z 的最大值是 .答：313解：∵ z y x -=+5，35)5(3)(32+-=--=+-=z z z z y x z xy ， ∴ x 、y 是关于t 的一元二次方程035)5(22=+-+--z z t z t的两实根.∵ 0)35(4)5(22≥+---=∆z z z ，即0131032≤--z z ，0)1)(133(≤+-z z .∴ 313≤z ，当31==y x 时，313=z . 故z 的最大值为313.三、解答题（共4题，每小题15分，满分60分）11．通过实验研究，专家们发现：初中学生听课的注意力指标数是随着老师讲课时间的变化而变化的，讲课开始时，学生的兴趣激增，中间有一段时间，学生的兴趣保持平稳的状态，随后开始分散. 学生注意力指标数y 随时间x （分钟）变化的函数图象如图所示（y 越大表示学生注意力越集中）. 当100≤≤x 时，图象是抛物线的一部分，当2010≤≤x 和4020≤≤x 时，图象是线段. （1）当100≤≤x 时，求注意力指标数y 与时间x 的函数关系式；（2）一道数学竞赛题需要讲解24分钟. 问老师能否经过适当安排，使学生在听这道题时，注意力的指标数都不低于36. 解：（1）当100≤≤x 时，设抛物线的函数关系式为c bx ax y ++=2，由于它的图象经过点（0，20），（5，39），（10，48），所以⎪⎩⎪⎨⎧=++=++=.4810100,39525,20c b a c b a c 解得，51-=a ，524=b ，20=c .所以20524512++-=x x y ，100≤≤x . …………………（5分）（第11（A ）题图）（2）当4020≤≤x 时，7657+-=x y .所以，当100≤≤x 时，令y =36，得2052451362++-=x x ，解得x =4，20=x （舍去）；当4020≤≤x 时，令 y =36，得765736+-=x ，解得74287200==x . ……………………（10分） 因为24742447428>=-，所以，老师可以经过适当的安排，在学生注意力指标数不低于36时，讲授完这道竞赛题. ……………………（15分） 12．已知a ，b 是实数，关于x ，y 的方程组⎩⎨⎧+=--=bax y bx ax x y ,23 有整数解),(y x ，求a ，b 满足的关系式.解：将b ax y +=代入bx ax x y --=23，消去a 、b ，得xy x y -=3， ………………………（5分）3)1(x y x =+.若x +1=0，即1-=x ，则上式左边为0，右边为1-不可能. 所以x +1≠0，于是111123+-+-=+=x x x x x y .因为x 、y 都是整数，所以11±=+x ，即2-=x 或=x 0，进而y =8或=y 0. 故⎩⎨⎧=-=82y x 或⎩⎨⎧==0y x ………………………（10分） 当⎩⎨⎧=-=82y x 时，代入b ax y +=得，082=+-b a ；当⎩⎨⎧==00y x 时，代入b ax y +=得，0=b . 综上所述，a 、b 满足关系式是082=+-b a ，或者0=b ，a 是任意实数.………………………（15分）13．D 是△ABC 的边AB 上的一点，使得AB =3AD ，P 是△ABC 外接圆上一点，使得ACB ADP ∠=∠，求PD PB的值.解：连结AP ，则ADP ACB APB ∠=∠=∠，所以，△APB ∽△ADP ， …………………………（5分） ∴AD AP AP AB =， 所以223AD AD AB AP =•=，∴AD AP 3=， …………………………（10分） 所以3==ADAPPD PB . …………………………（15分） 14．已知0<a ，0≤b ，0>c ，且ac b ac b 242-=-，求ac b 42-的最小值. 解：令c bx ax y ++=2，由0<a ，0≤b ，0>c ，判别式042>-=∆ac b ，所以这个二次函数的图象是一条开口向下的抛物线，且与x 轴有两个不同的交点)0,(1x A ，)0,(2x B ，因为021<=acx x ，不妨设21x x <，则210x x <<，对称轴02≤-=abx ，于是 c a ac b b a ac b b x =--=-+-=2424221， ………………（5分）所以aac b a ac b b c a b ac 242444222--≥--=≥-， …………………（10分） 故442≥-ac b ，当1-=a ，b =0，c =1时，等号成立.所以，ac b 42-的最小值为4. ………………………（15分）（第13（A ）题图）（第14（A ）题图）。