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

《信息竞赛中的简单数学类问题及其数学构造方法.ppt》由会员分享，可在线阅读，更多相关《信息竞赛中的简单数学类问题及其数学构造方法.ppt（53页珍藏版）》请在三一文库上搜索。

1、数学类问题,精度处理（高精度、实数处理） 组合数学问题（Fibonacci数列、第二类数、卡特兰数、POLYA原理、排列组合计数、加法原理与乘法原理） 进制问题（特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换）,数学类问题,递推与递归关系（递推关系式、通项公式、数列、博弈问题） 数位、数字、特定数值的查找、统计（数值处理、质因子分解、幂次分解、数值表达式、添加运算符、分式与实数运算） 数学杂题（回文数字、矩阵处理、约瑟夫与反约瑟夫问题） 数学剪枝（无解判定、解线性方程组、限定搜索范围）,数学类问题的思维过程,相关公式、定理、原理的应用 寻找规律、归纳整理递归与递推关系式

2、 按照数学方法构造、二进制转化等技巧性处理 注意事项： 规律准确（小数据手工推算、搜索程序验证） 数据类型是否合理、数据范围是否超界（大数据处理）,整数划分问题（一）,最优分解方案 将一个整数n分成若干个互不相同的数的和，使得这些数的乘积最大。其中1=n=1000。,分析,初看此题，最容易相到的算法是搜索，但此题的最大可以达到1000，搜索肯定会超时，而本题所给的限制条件也不多，即便是加上一些剪枝也起不到很好的效果。一般遇到这种情况我们可以从简单的数据分析起。,在解一些问题的时候（特别是用数学方法解的问题），当我们无从解决时，可以从简单的数据考虑起，以便发现其中的一些规律，这种作法对解题是很有

3、帮助的。 n 分解方案 MUL 5 2,3 6 6 2,4 8 7 3,4 12 8 3,5 15 9 2,3,4 24 10 2,3,5 30,观察这几组数据，不难发现所有的分解方案的数的个数都等于可以分出的最多个数，其实我们并不难想到，要想使乘积最大，应尽量使分得的数多。 另一方面，我们在初中数学中就已经证明过当数（正数）的和相等时，数的差越小，数的积也就越大，因此我们可以在分的数的个数最多的情况下使数之间的差尽量小，这样得出来的方案必定是最优的。,整数分划（二）,例题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。,分析,根据数学规律可知,若要使和固

4、定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律： 当N mod 31 时，N可分解为一个4和若干个3的和； 当N mod 32 时，N 可分解为一个2和若干个3的和； 当N mod 30 时，N 直接分解为若干个3的和。 按照这一分解方法，所有因数的乘积必定最大。 注意：因N 的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。,整数分划的方案总数,把一个正整数N表示成如下表达式的一系列正整数的和，叫做整数N的一个分划。某个正整数N的不同表达式的个数称做整数N的分划数。编程计算指定正整数的分划数。 Nn1n2nk Nj=1,j=1,2,，k,k=1 1=n1=

5、n2=nk 输入正整数N（N100），输出N的分划数。,分析,在求解整数N的分划数时，设分解方案（表达式）中最大可以分解的整数因子nj的值最大不超过m，用F（N，m）记录N被划分成不超过m的整数的方案总数，通过数学分析，容易得到一个递归定义的递推关系式：,1 (m=1) F（N，m）= F(N-m,m)+F(N,m-1) (m1,mN) 初始（边界条件）为F(0,m)=1 (m0) 目标状态为F（N，N）。,例题4：极值问题（最高时限15s） 已知m、n为整数，且满足下列两个条件： m、n1，2，K，（1K109） (n 2mnm2)21 编一程序，由键盘输入K，求一组满足上述两个条件的m、n

6、，并且使m2n2的值最大。例如，若K1995，则m987，n1597，则m、n满足条件，且可使m2n2的值最大。,【分析】方法一 从初等数学的角度考虑： 由条件（n 2mnm2）21得出： n 2mnm2 + 1 = 0 n 2mnm21 = 0 根据求根公式 N1,2（m1,2）/2 n3,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）为整数且

7、小于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； if（n2为整数）and（n2k） then begin 输出m和n2; halt; end end;then mml; end;while,上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件 1k109 。如果K值超过105，上

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

9、小于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。,组合计数,Catala

10、n数 定义：一个凸n边形通过不相交于n边形内部的对角线把n边形拆分成若干三角形的不同拆分数。,分析,设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1 Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，Pn-1点中找一个点Pk(1kn)，与P1、Pn 共同构成一个三角形的三个顶点，就将n边形分成了三个不相交的部分(如图3所示)，我们分别称之为区域、区域、区域，其中区域必定是一个三角形，区域是一个凸k边形，区域是一个凸n-k+1边形。,分析,区域的拆分方案总数是Ck，区域的拆分方案数为Cn-k+1，故包含

11、P1PkPn的n 边形的拆分方案数为CkCn-k+1种，而Pk可以是P2，P3，Pn-1种任一点，根据加法原理，凸n边形的三角拆分方案总数为 ， 同时考虑到计算的方便，约定边界条件C2=1。,分析,=C( 2n , n ) / ( n + 1),具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递推式,再进行递推计算，并且注意类型的定义要用comp型。,Catalan数的应用（部分和序列）,n个+1，n个-1构成2n项 a1,a2,a3,a4,a2n 其部分和满足 a1+a2+ak (k=1,2,3,.2n)=0的数列个数。,Catalan数的应用（加括号）,序列a1a2ak的

12、元素顺序保持不变，按不同结合方式插入合法圆括号对的方案数。 n=4 (a(bc)d) (a(b(cd) (ab)(cd) (ab)c)d) (a(bc)d),一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种操作：1将一个数，从操作数列的头端移至栈的头端（对应栈的push操作）2将一个数，从栈的头端移至输出序列的尾端（对应栈的pop操作）。使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下表为由1 2 3 生成序列2 3 1 的过程。,Catalan数的应用（栈 NOIp2003）,结合定义我们很容易能发现：如果进栈看成1，出栈看成0，在任何一位上累计的“0”的

13、个数不大于累计的“1”的个数，因为必须在栈里有数的情况下才能向外弹数。,原题转化为n个1和n个0组成一个2n位的二进制数，要求从左到右扫描，“0”的累计数不大于“1”的累计数，求满足条件的数有多少。,任务： 你的程序将对给定的n，计算并输出由操作数序列1，2，n经过操作可能得到的输出序列总数。,分析,n个数，分别为1n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个排列是一个错排。例如，n=3，则错排有2 3 1、3 1 2。编写程序，求n的错排个数。,错排问题（经典问题）,组合计数,我们设k个元素的错位全排列的个数记做：W(k)。,四个元素的错位排列W(4)我们用穷举法

14、可以找到如下9个： (4，3，2，1)(3，4，1，2)(2，1，4，3) (4，1，2，3)(3，4，2，1)(3，1，4，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) *

15、 W(k1)+W(k2),分析,构造法,“构造法”解题，就是构造数学模型解决问题。包括直接构造问题解答的模型，图论模型，网络流模型以及组合数学模型。,构造法解题的思路或步骤,构造法解题的类型： 直接构造问题解答。这只是构造法运用的一种简单类型。它只能针对问题本身，探索其独有性质，不具备可推广性。 数学建模。通过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、一幅几何图形，一个物理原理、一个化学方程式，等等。,无论是直接构造问题解答还是构造数学模型，都要通过算法实现。如何设计一个有较低编程复杂度和时空复杂度且结构清晰的算法，十分重要

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,y）A=(y,x+

17、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）。,这个题目初看上去，似乎无从下手。由于题目中所给的这种特殊的树以及顶点标号的约束条件都是我们以前没有见到过的，再加上数据的规模很大，最大可以达到

18、N=10000。使得我们不得不朝着贪心或者构造的方向去思考。 首先观察样例，再进行了一些尝试后，我们找到了对于样例的很多种合法的标号，其中有一种引起了我们的注意，如下图所示:,很容易发现，图中边的权值，也就是边的两端顶点标号差的绝对值，是从左向右依次递减的。这个发现使我们不由得想到，是不是对于所有的毛毛虫都存在一种这样的合法标号方式。,例题分析,一序列（见文本）,利用图论模型进行构造,例题3：圆桌吃饭问题 n个人围着一张圆桌吃饭，每个人都不愿意两天与同一人为邻，问最多能坐多少天，并给出一种排列方案？,转化为图论模型,设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，连结顶点的边

19、表示人之间的相邻关系。因此，每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=为G中的一条哈密尔顿回路，其中所含的边的集合记为e(L)。问题转化为： 求m与L1,L2,Lm，使得e(Li)e(Lj)=， 并且m达到最大值。,构造方法,作一圆，把圆周分成n-1等分，标上n-1个刻度，将顶点1至n-1依次排列在圆周上，顶点n放在圆心。先从圆心出发，向任意点连一条线，再从这点出发，沿圆周向左右两个方向迂回连线，直到连完圆周上所有的点，再连回圆心。这样就构造出一条哈密尔顿回路。保持所有的顶点位置不变，把所有连线围绕圆心逆时针方向旋转一个刻度，得到一条新的哈密尔顿回路。这样连续旋转(n-1)di

20、v 2次，就得到了(n-1)div 2条回路。,N=5,构造图象，充分展示各变量之间的关系,【例二】01串问题(NOI99) 给定N,L0,A0,B0,L1,A1,B1，设计一个长度为N的01串，使得对于任何连续的长度为L0的子串，0的个数大于等于A0,且小于等于B0,对于任何连续的长度为L1的子串，1的个数大于等于A1且小于B1。,【解题分析】 模式1 分析不等式,设hi为01子串s0si(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=hi-hi-l0

21、,当I=L0时，根据条件，Si-L0+1Si中0的个数(L0-(hi-hi-L0)在a0b0之间，即a0=L0-(hi-hi-L0)=b0,a0-L0=hi-L0-hi,-b1=hi-l1-hi,当I=L1时，根据条件，Si-L1+1 Si中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） 每个

22、不等式都是含两个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表示从顶点0到顶点I的最长路径长度。 对于图中 每条从点I指向点J的权为CI,J的边，有性质 DI+CI,J=DJ（注意：这与上述不等式的形式相似）,这样，令hi=DI，h完全符合所有限制条件，即为原不等式组的一组解 。,（2） G中含有环 可用反证法证明无解。,从s1出发，顺序确定每位二进制数。当hi=hi-1时，说明s1si-1中1的个数与s1si中1的个数相同，即si为0；否则si为1。,