day1数学方法-曹立国-noip培训ppt课件

1、数学类问题精度处置高精度、实数处置 瓷片项链进制问题特定二进制串的统计、二分查找、利用二进制进展途径、形状描画、二进制转换 k进制数递推与递归关系递推关系式、通项公式、数列、博弈问题 整数分划问题.数学类问题数位、数字、特定数值的查找、统计数值处置与质因子分解 反素数数学杂题回文数字、约瑟夫与反约瑟夫问题 聪明的农民数学运用无解断定、解线性方程组、矩阵处置、限定搜索范围 Gauss消元组合数学问题Fibonacci数列、卡特兰数、POLYA原理、陈列组合计数、加法原理与乘法原理 极值问题 电子锁数学构造 .数学类问题的思想过程相关公式、定理、原理的运用寻觅规律、归纳整理递归与递推关系式按照数学

2、方法构造、二进制转化等技巧性处置本卷须知：规律准确小数据手工推算、搜索程序验证数据类型能否合理、数据范围能否超界大数据处置.瓷片项链给定泥土总体积V总和烧制时的损耗V0以及瓷片直径D和体积V的关系，求能获得最长项链的瓷片数。 D和V的关系是 D=0.3*SQR(V-V0) (VV0) D=0 (V=V0).分析完全按照标题的描画进展计算 repeat inc(i); each:=v/i; if v=v0*i then break; d:=0.3*sqrt(each-v0)*i;until false;.判别时去掉开方运算，即同时平方。repeat inc(i); each:=v/i; if v

3、=v0*i then break; d:=0.3*0.3*(each-v0)*i*i;until false;.判别时去掉开方运算和除法运算。d=03*0.3*(v/I-v0)*I*I=0.3*0.3*I*(v-v0*I),0.3为常数，判别时可以舍去。repeat inc(i); if v=v0*i then break; d:=0.3*0.3*i*(v-v0*i);until false;.K进制数Number一个合法的n位K进制数定义如下： 它是一个首位不为0的K进制数。 它不包含延续的两个0。义务：对于输入的K，n。求出满足上述条件的K进制数个数。输入(number.in)只需一行：N

4、, K输入(number.out)输出文件只需一个数字，即满足条件的N位K进制数总个数数听阐明2=K=50, 2=n第i-1位为0的情况应该等于i-2位不为0的情况总数，即fi-2第i-1位不为0的情况应该等于fi-1所以fi=(fi-1+fi-2)*(k-1).整数划分问题一最优分解方案 将一个整数n分成假设干个互不一样的数的和，使得这些数的乘积最大。其中1=n=1000。.分析初看此题，最容易相到的算法是搜索，但此题的最大可以到达1000，搜索一定会超时，而此题所给的限制条件也不多，即使是加上一些剪枝也起不到很好的效果。普通遇到这种情况我们可以从简单的数据分析起。.在解一些问题的时候特别是

5、用数学方法解的问题，当我们无从处理时，可以从简单的数据思索起，以便发现其中的一些规律，这种作法对解题是很有协助的。 n 分解方案 MUL 5 2,3 66 2,4 87 3,4 128 3,5 159 2,3,4 2410 2,3,5 30.察看这几组数据，不难发现一切的分解方案的数的个数都等于可以分出的最多个数，其实我们并不难想到，要想使乘积最大，应尽量使分得的数多。另一方面，我们在初中数学中就曾经证明过当数正数的和相等时，数的差越小，数的积也就越大，因此我们可以在分的数的个数最多的情况下使数之间的差尽量小，这样得出来的方案必定是最优的。.整数分划二例题2：假设干个正整数之和为n，其中：n=

6、1,j=1,2,，k,k=1 1=n1=n2=1,mN)初始边境条件为F(0,m)=1 (m0)目的形状为FN，N。.反素数 正整数 n是一个Antiprime数，假设这个数的约数个数超越比n小的任何数的约数个数。例如：以下Antiprime数1，2，4，6，12和24。编程求解不超越n的最大的Antiprime数。【输入】： 在输入文件ANT.IN有一个整数n。1n2000000000【输出】： 输出文件ANT.OUT应该有一个正整数：不超越n的最大Antiprime数。.分析见文档.极值问题最高时限15s知m、n为整数，且满足以下两个条件： m、n1，2，K，1K109 (n 2mnm2)

7、21编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2n2的值最大。例如，假设K1995，那么m987，n1597，那么m、n满足条件，且可使m2n2的值最大。.【分析】方法一从初等数学的角度思索：由条件n 2mnm221得出：n 2mnm2 + 1 = 0n 2mnm21 = 0根据求根公式N1,2m1,2/2 n3,4m1,2/2其中：1sqrt5*m24； 2sqrt5*m24；.【分析】再思索条件。由于n1，因此排除了n3和n4存在的能够性.又由于n和m是整数，因此1和2应为整数。由于m2n2单调递增，从mk出发，按递减方向将m值代入n的求根公式。只需1或2为整数、n1

8、或n2为整数且小于k，那么得出的一组m和n一定使 m2n2的值最大。.【算法描画】 mk；while mi do begin 求1 if 1为整数 then begin 求n1； if (n1为整数) and (n1k) Then begin 输出m和n1；halt; end end; then 求2； if 2为整数 then begin 求n2； ifn2为整数andn2k then begin 输出m和n2; halt; end end;then mml; end;while.上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件 1k109 。假设K值超越10

9、5，上述算法不能够在限定的15秒内出解。.【分析】方法二分析小数据会发现：m,n是Fibonacci数列的相邻两项。由于： n 2mnm22 1故： m2 + mn n 2 2 1又： m 2mnn2(mn)2mn2n2 (mn)2(mn)nn2 故： m2mnn22(mn)2(mn)nn22 即： n2mnm22(mn)2(mn)nn22.【分析】由上述数学变换式可以得出，假设m和n为一组满足条件和条件的解，设nmn，m n那么n，m 也是一组满足条件和条件的一组解。将一切满足条件和条件的m和n 按递增顺序排成一个Fibomacci数列 1，1，2，3，5，8， 数列中小于k的最大两个相邻数

10、即为试题所要求的一组m和n。算法：利用Fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2n2的值最大。.Gauss消元例如2x1+x2-x3=-1X1+x2+x3=2X1-x2+2x3=6.Kathy函数(HNCOI)Tiger非常喜欢数学，所以他参与了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，教师向Tiger引见了Kathy函数，Kathy函数是这样定义的：.Kathy函数(HNCOI)Tiger对Kathy函数产生了浓重的兴趣，他经过研讨发现有很多的数n都满足f(n)=n,对于一个给定的数m，他希望他求出一切的满足f(n)=n (n=m)的自然数n的个数，其

11、中m=10100。.组合计数Catalan数定义：一个凸n边形经过不相交于n边形内部的对角线把n边形拆分成假设干三角形的不同拆分数。.分析设Cn表示凸n边形的拆分方案总数。由标题中的要求可知一个凸n边形的恣意一条边都必然是一个三角形的一条边，边P1 Pn也不例外，再根据“不在同不断线上的三点可以确定一个三角形，只需在P2，P3，Pn-1点中找一个点Pk(1k=0的数列个数。 .Catalan数的运用加括号 序列a1a2.ak的元素顺序坚持不变，按不同结合方式插入合法圆括号对的方案数。n=4(a(bc)d)(a(b(cd)(ab)(cd)(ab)c)d)(a(bc)d) .一个操作数序列，从1，

12、2，不断到n，栈A的深度大于n。如今可以进展两种操作：1将一个数，从操作数列的头端移至栈的头端对应栈的push操作2将一个数，从栈的头端移至输出序列的尾端对应栈的pop操作。运用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下表为由1 2 3 生成序列2 3 1 的过程。步骤0123456操作数序列1232333 栈 1211311 输出序列 2223231Catalan数的运用栈 NOIp2003.结合定义我们很容易能发现：假设进栈看成1，出栈看成0，在任何一位上累计的“0的个数不大于累计的“1的个数，由于必需在栈里有数的情况下才干向外弹数。原题转化为n个1和n个0组成一个2n位的

13、二进制数，要求从左到右扫描，“0的累计数不大于“1的累计数，求满足条件的数有多少。义务： 他的程序将对给定的n，计算并输出由操作数序列1，2，n经过操作能够得到的输出序列总数。分析. n个数，分别为1n，排成一个长度为n的陈列。假设每一个数的位置都与数的本身不相等，那么称这个陈列是一个错排。例如，n=3，那么错排有2 3 1、3 1 2。编写程序，求n的错排个数。错排问题经典问题组合计数.我们设k个元素的错位全陈列的个数记做：W(k)。四个元素的错位陈列W(4)我们用穷举法可以找到如下9个： (4，3，2，1)(3，4，1，2)(2，1，4，3)(4，1，2，3)(3，4，2，1)(3，1，4

14、，2)(4，3，1，2)(2，4，1，3)(2，3，4，1)它们有什么规律呢？分析.经过反复的实验，我们发现现实上有两种方式产生错位陈列：A.将k与(1，2，k1)的某一个数互换，其他k2个数进展错排，这样可以得到(k1)W(k-2)个错位陈列。B.另一部分是将前k1个元素的每一个错位陈列有W(k-1)个中的每一个数与k互换，这样可以得到剩下的(k1)W(k-1) 个错位陈列。根据加法原理，我们得到求错位陈列的递推公式W(k):W(k) = (k1) * W(k1)+W(k2)分析.构造法 “构造法解题，就是构造数学模型处理问题。包括直接构造问题解答的模型，图论模型，网络流模型以及组合数学模型

15、。 .构造法解题的思绪或步骤构造法解题的类型：直接构造问题解答。这只是构造法运用的一种简单类型。它只能针对问题本身，探求其独有性质，不具备可推行性。数学建模。经过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、一幅几何图形，一个物理原理、一个化学方程式，等等。.无论是直接构造问题解答还是构造数学模型，都要经过算法实现。如何设计一个有较低编程复杂度和时空复杂度且构造明晰的算法，非常重要。通常思索的要素有选择的模型必需尽量多地表达问题的本质特征。但这并不意味着模型越复杂越好，累赘的信息会影响算法的效率。模型的建立不是一个一蹴而就的过程

16、，而是要经过反复地检验、修正，在实际中不断完善。数学模型通常有严厉的格式，但程序编写方式可不拘一格。.利用数学方法进展构造例1：求Fibonacci数列 定义：f0=f1=1, fn=fn-1+fn-2(n=2)。fi称为Fibonacci数列。 输入n，求fn mod q。其中1=q=30000。n=109 【解题分析】简单的模拟显然不能满足标题的要求，我们思索构造解答。 . 定义矩阵 0 1 1 1为A, 发现x,yA=(y,x+y),恰好与数列性质类似 。于是有，有(1,1)A=(1,2), Fi,Fi+1A=(Fi+1,Fi+Fi+1)=(Fi+1,Fi+2) ,即(1,1)An=(F

17、n,Fn+1) 在(n)的时间内即可出解。.例题2： 毛毛虫是含N个节点的一棵树，它包含一条主链，一切点要么在链上，要么和主链上某点相邻。我们希望给毛毛虫的每个顶点标号1,2,3,N，使得一切边的两端节点标号差的绝对值恰好包含了1,2,3,N-1，每个数正好一次N=10000。.815294863726358147.这个标题初看上去，似乎无从下手。由于标题中所给的这种特殊的树以及顶点标号的约束条件都是我们以前没有见到过的，再加上数据的规模很大，最大可以到达N=10000。使得我们不得不朝着贪婪或者构造的方向去思索。首先察看样例，再进展了一些尝试后，我们找到了对于样例的很多种合法的标号，其中有一

18、种引起了我们的留意，如以下图所示:.19234876512345678.很容易发现，图中边的权值，也就是边的两端顶点标号差的绝对值，是从左向右依次递减的。这个发现使我们不由得想到，是不是对于一切的毛毛虫都存在一种这样的合法标号方式。 .例题分析一序列见文本.利用图论模型进展构造例题3：圆桌吃饭问题 n个人围着一张圆桌吃饭，每个人都不情愿两天与同一人为邻，问最多能坐多少天，并给出一种陈列方案？.转化为图论模型 设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，连结顶点的边表示人之间的相邻关系。因此，每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=为G中的一条哈密尔顿回路

19、，其中所含的边的集合记为e(L)。问题转化为： 求m与L1,L2,Lm，使得e(Li)e(Lj)=， 并且m到达最大值。.构造方法 作一圆，把圆周分成n-1等分，标上n-1个刻度，将顶点1至n-1依次陈列在圆周上，顶点n放在圆心。先从圆心出发，向恣意点连一条线，再从这点出发，沿圆周向左右两个方向迂回连线，直到连完圆周上一切的点，再连回圆心。这样就构造出一条哈密尔顿回路。坚持一切的顶点位置不变，把一切连线围绕圆心逆时针方向旋转一个刻度，得到一条新的哈密尔顿回路。这样延续旋转(n-1)div 2次，就得到了(n-1)div 2条回路。.N=5当n=5时.构造图象，充分展现各变量之间的关系 【例二】

20、01串问题(NOI99) 给定N,L0,A0,B0,L1,A1,B1，设计一个长度为N的01串，使得对于任何延续的长度为L0的子串，0的个数大于等于A0,且小于等于B0,对于任何延续的长度为L1的子串，1的个数大于等于A1且小于B1。 .【解题分析】方式1 分析不等式 设hi为01子串s0.si(1=I=n)中1的个数，其中s0=0,h0=0。显然，由hi的定义可以得出不等式0=hi-1=hi,hi=hi-1+1, 移项即得： 0=hi-hi-1 -1=hi-1-hi .L0-b0=L0时，根据条件，Si-L0+1Si中0的个数(L0-(hi-hi-L0)在a0b0之间，即a0=L0-(hi-hi-L0)=b0 a0-L0=hi-L0-hi -b1=L1时，根据条件，Si-L1+1 Si中1的个数(hi-hi-L1)在a1b1之间，即a1=hi