信息竞赛中的简单数学类问题及其数学构造方法.ppt

数学类问题,精度处理（高精度、实数处理）组合数学问题（Fibonacci数列、第二类数、卡特兰数、POLYA原理、排列组合计数、加法原理与乘法原理）进制问题（特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换）,数学类问题,递推与递归关系（递推关系式、通项公式、数列、博弈问题）数位、数字、特定数值的查找、统计（数值处理、质因子分解、幂次分解、数值表达式、添加运算符、分式与实数运算）数学杂题（回文数字、矩阵处理、约瑟夫与反约瑟夫问题）数学剪枝（无解判定、解线性方程组、限定搜索范围）,数学类问题的思维过程,相关公式、定理、原理的应用寻找规律、归纳整理递归与递推关系式按照数学方法构造、二进制转化等技巧性处理注意事项：规律准确（小数据手工推算、搜索程序验证）数据类型是否合理、数据范围是否超界（大数据处理）,整数划分问题（一）,最优分解方案将一个整数n分成若干个互不相同的数的和，使得这些数的乘积最大。其中1=n=11=n1=n20)目标状态为F（N，N）。,例题4：极值问题（最高时限15s）已知m、n为整数，且满足下列两个条件：m、n1，2，K，（1K109）(n2mnm2)21编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2n2的值最大。例如，若K1995，则m987，n1597，则m、n满足条件，且可使m2n2的值最大。,【分析】方法一从初等数学的角度考虑：由条件（n2mnm2）21得出：n2mnm2+1=0n2mnm21=0根据求根公式N1,2（m1,2）/2n3,4（m1,2）/2其中：1sqrt（5*m24）；2sqrt（5*m24）；,【分析】再考虑条件。由于n1，因此排除了n3和n4存在的可能性.又由于n和m是整数，因此1和2应为整数。由于m2n2单调递增，从mk出发，按递减方向将m值代入n的求根公式。只要1（或2）为整数、n1（或n2）为整数且小于k，则得出的一组m和n一定使m2n2的值最大。,【算法描述】mk；whilemidobegin求1if1为整数thenbegin求n1；if(n1为整数)and(n1k)Thenbegin输出m和n1；halt;endend;then求2；if2为整数thenbegin求n2；if（n2为整数）and（n2k）thenbegin输出m和n2;halt;endend;thenmml;end;while,上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件1k109。如果K值超过105，上述算法不可能在限定的15秒内出解。,【分析】方法二分析小数据会发现：m,n是Fibonacci数列的相邻两项。因为：（n2mnm2）21故：（m2+mnn2）21又：m2mnn2(mn)2mn2n2(mn)2(mn)nn2故：（m2mnn2）2(mn)2(mn)nn22即：（n2mnm2）2(mn)2(mn)nn22,【分析】由上述数学变换式可以得出，如果m和n为一组满足条件和条件的解，设nmn，mn那么n，m也是一组满足条件和条件的一组解。将所有满足条件和条件的m和n按递增顺序排成一个Fibomacci数列1，1，2，3，5，8，数列中小于k的最大两个相邻数即为试题所要求的一组m和n。算法：利用Fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2n2的值最大。,例题5：Kathy函数(HNCOI)Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的：,例题5：Kathy函数(HNCOI)Tiger对Kathy函数产生了浓厚的兴趣，他通过研究发现有很多的数n都满足f(n)=n,对于一个给定的数m，他希望你求出所有的满足f(n)=n(n=m)的自然数n的个数，其中m=10100。,组合计数,Catalan数定义：一个凸n边形通过不相交于n边形内部的对角线把n边形拆分成若干三角形的不同拆分数。,分析,设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，Pn-1点中找一个点Pk(1=2)。fi称为Fibonacci数列。输入n，求fnmodq。其中1=q=30000。n=109,【解题分析】简单的模拟显然不能满足题目的要求，我们考虑构造解答。,定义矩阵0111,为A,发现（x,y）A=(y,x+y),恰好与,数列性质相似。,于是有，有(1,1)A=(1,2),（Fi,Fi+1）A=(Fi+1,Fi+Fi+1)=(Fi+1,Fi+2),即(1,1)An=(Fn,Fn+1)在(n)的时间内即可出解。,例题2：毛毛虫是含N个节点的一棵树，它包含一条主链，所有点要么在链上，要么和主链上某点相邻。我们希望给毛毛虫的每个顶点标号1,2,3,N，使得所有边的两端节点标号差的绝对值恰好包含了1,2,3,N-1，每个数正好一次（N=10000）。,这个题目初看上去，似乎无从下手。由于题目中所给的这种特殊的树以及顶点标号的约束条件都是我们以前没有见到过的，再加上数据的规模很大，最大可以达到N=10000。使得我们不得不朝着贪心或者构造的方向去思考。首先观察样例，再进行了一些尝试后，我们找到了对于样例的很多种合法的标号，其中有一种引起了我们的注意，如下图所示:,很容易发现，图中边的权值，也就是边的两端顶点标号差的绝对值，是从左向右依次递减的。这个发现使我们不由得想到，是不是对于所有的毛毛虫都存在一种这样的合法标号方式。,例题分析,一序列（见文本）,利用图论模型进行构造,例题3：圆桌吃饭问题n个人围着一张圆桌吃饭，每个人都不愿意两天与同一人为邻，问最多能坐多少天，并给出一种排列方案？,转化为图论模型,设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，连结顶点的边表示人之间的相邻关系。因此，每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=为G中的一条哈密尔顿回路，其中所含的边的集合记为e(L)。问题转化为：求m与L1,L2,Lm，使得e(Li)e(Lj)=，并且m达到最大值。,构造方法,作一圆，把圆周分成n-1等分，标上n-1个刻度，将顶点1至n-1依次排列在圆周上，顶点n放在圆心。先从圆心出发，向任意点连一条线，再从这点出发，沿圆周向左右两个方向迂回连线，直到连完圆周上所有的点，再连回圆心。这样就构造出一条哈密尔顿回路。保持所有的顶点位置不变，把所有连线围绕圆心逆时针方向旋转一个刻度，得到一条新的哈密尔顿回路。这样连续旋转(n-1)div2次，就得到了(n-1)div2条回路。,N=5,构造图象，充分展示各变量之间的关系,【例二】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+1Si中1的个数(hi-hi-L1)在a1b1之间，即a1=hi-hi-L1=b1。,a1=hi-hi-L1,一旦有了h序列，我们可以由左至右构造s串：如果hi-1=hi，则说明si=0；否则si=1(1=I=n)。由此看来，问题的关键是如何计算h序列。,仔细观察上述推论条件，发现有以下特点：（1）除h0=0外，其余的条件都是由“=”连接的不等式（2）每个不等式都是含两个h未知数、一个常数的一次不等式；可见，所有不等式都整理成了k=hi-hj它给我们启示，上述不等式类似于连接两点的一条有向边。因此，我们联想到信息学解题中常用的图论知识。,模型2构造有向图G我们构造有向图G，如图：,其中vi代表s串中的第I位。若k,表明sisj中至少需增加k个1（k为正值）或减少k个1(k为负值)。由此得出构造有向图G的方法：,0=hi-hi-1,-1=hi-1-hi,a0-L0=hi-L0-hi,L0-b0=hi-hi-l0,a1=hi-hi-L1,-b1=hi-l1-hi,计算图G的最长路径：我们已构造了一个有n+1个顶点的有向图G。,（1）图G中无环令DI表