day1数学方法noip培训

数学类问题•精度处理（高精度、实数处理瓷片项链）•进制问题（特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换k进制数）•递推与递归关系（递推关系式、通项公式、数列、博弈问题整数分划问题）数学类问题•数位、数字、特定数值的查找、统计（数值处理与质因子分解反素数）•数学杂题（回文数字、约瑟夫与反约瑟夫问题聪明的农民）•数学应用（无解判定、解线性方程组、矩阵处理、限定搜索范围Gauss消元）•组合数学问题（Fibonacci数列、卡特兰数、POLYA原理、排列组合计数、加法原理与乘法原理极值问题电子锁）•数学构造数学类问题的思维过程–相关公式、定理、原理的应用–寻找规律、归纳整理递归与递推关系式–按照数学方法构造、二进制转化等技巧性处理–注意事项：•规律准确（小数据手工推算、搜索程序验证）•数据类型是否合理、数据范围是否超界（大数据处理）瓷片项链•给定泥土总体积V总和烧制时的损耗V0以及瓷片直径D和体积V的关系，求能获得最长项链的瓷片数。•D和V的关系是•D=0.3*SQR(V-V0)(VV0)•D=0(V=V0)分析•完全按照题目的描述进行计算•repeat•inc(i);•each:=v/i;•ifv=v0*ithenbreak;•d:=0.3*sqrt(each-v0)*i;•untilfalse;•判断时去掉开方运算，即同时平方。•repeat•inc(i);•each:=v/i;•ifv=v0*ithenbreak;•d:=0.3*0.3*(each-v0)*i*i;•untilfalse;•判断时去掉开方运算和除法运算。•d=03*0.3*(v/I-v0)*I*I=0.3*0.3*I*(v-v0*I),0.3为常数，判断时可以舍去。•repeat•inc(i);•ifv=v0*ithenbreak;•d:=0.3*0.3*i*(v-v0*i);•untilfalse;K进制数（Number）•一个合法的n位K进制数定义如下：它是一个首位不为0的K进制数。它不包含连续的两个0。•任务：对于输入的K，n。求出满足上述条件的K进制数个数。•输入(number.in)•只有一行：N,K•输入(number.out)•输出文件只有一个数字，即满足条件的N位K进制数总个数•数据说明•2=K=50,2=n=1800•输入输出示例：•Number.in•22•Number.out•2分析•用f[i]表示i位（最高位是第i位）K进制数的总数，那么就有：•f[i]=(f[i-1]+f[i-2])*(K-1)•怎么解释这个方程呢？•f[i]也就是i位K进制数的总数应该等于：第i-1位为0与第i-1位不为0的情况的和乘以第i位的情况数(1..k-1)•第i-1位为0的情况应该等于i-2位不为0的情况总数，即f[i-2]•第i-1位不为0的情况应该等于f[i-1]•所以f[i]=(f[i-1]+f[i-2])*(k-1)整数划分问题（一）最优分解方案将一个整数n分成若干个互不相同的数的和，使得这些数的乘积最大。其中1=n=1000。分析•初看此题，最容易相到的算法是搜索，但此题的ｎ最大可以达到1000，搜索肯定会超时，而本题所给的限制条件也不多，即便是加上一些剪枝也起不到很好的效果。一般遇到这种情况我们可以从简单的数据分析起。•在解一些问题的时候（特别是用数学方法解的问题），当我们无从解决时，可以从简单的数据考虑起，以便发现其中的一些规律，这种作法对解题是很有帮助的。•n分解方案MUL52,36•62,48•73,412•83,515•92,3,424•102,3,530•观察这几组数据，不难发现所有的分解方案的数的个数都等于ｎ可以分出的最多个数，其实我们并不难想到，要想使乘积最大，应尽量使分得的数多。•另一方面，我们在初中数学中就已经证明过当数（正数）的和相等时，数的差越小，数的积也就越大，因此我们可以在分的数的个数最多的情况下使数之间的差尽量小，这样得出来的方案必定是最优的。整数分划（二）例题2：若干个正整数之和为n，其中：n2000，试求它们乘积的最大值以及该最大值的位数k。分析根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：•当Nmod3＝1时，N可分解为一个4和若干个3的和；•当Nmod3＝2时，N可分解为一个2和若干个3的和；•当Nmod3＝0时，N直接分解为若干个3的和。按照这一分解方法，所有因数的乘积必定最大。注意：因N的最大值可达2000，乘积将超过长整型数据范围，所以需用高精度运算。整数分划的方案总数•把一个正整数N表示成如下表达式的一系列正整数的和，叫做整数N的一个分划。某个正整数N的不同表达式的个数称做整数N的分划数。编程计算指定正整数的分划数。•N＝n1＋n2＋…＋nkNj=1,j=1,2,……，k,k=11=n1=n2=…=nk•输入正整数N（N＜＝100），输出N的分划数。分析•在求解整数N的分划数时，设分解方案（表达式）中最大可以分解的整数因子nj的值最大不超过m，用F（N，m）记录N被划分成不超过m的整数的方案总数，通过数学分析，容易得到一个递归定义的递推关系式：•1(m=1)•F（N，m）=F(N-m,m)+F(N,m-1)(m1,m=N)•F(N,N)(mN)•初始（边界条件）为F(0,m)=1(m0)•目标状态为F（N，N）。反素数•正整数n是一个Antiprime数，如果这个数的约数个数超过比n小的任何数的约数个数。例如：下列Antiprime数1，2，4，6，12和24。编程求解不超过n的最大的Antiprime数。•【输入】：•在输入文件ANT.IN有一个整数n。1≤n≤2000000000•【输出】：•输出文件ANT.OUT应该有一个正整数：不超过n的最大Antiprime数。分析•见文档极值问题（最高时限15s）已知m、n为整数，且满足下列两个条件：①m、n∈1，2，…，K，（1≤K≤109）②(n2－mn－m2)2＝1编一程序，由键盘输入K，求一组满足上述两个条件的m、n，并且使m2＋n2的值最大。例如，若K＝1995，则m＝987，n＝1597，则m、n满足条件，且可使m2＋n2的值最大。【分析】方法一从初等数学的角度考虑：由条件②（n2－mn－m2）2＝1得出：n2－mn－m2+1=0n2－mn－m2－1=0根据求根公式N1,2＝（m＋△1,2）/2n3,4＝（m－△1,2）/2其中：△1＝sqrt（5*m2＋4）；△2＝sqrt（5*m2－4）；【分析】再考虑条件①。由于n1，因此排除了n3和n4存在的可能性.又由于n和m是整数，因此△1和△2应为整数。由于m2＋n2单调递增，从m＝k出发，按递减方向将m值代入n的求根公式。只要△1（或△2）为整数、n1（或n2）为整数且小于k，则得出的一组m和n一定使m2＋n2的值最大。【算法描述】m←k；whilem≥idobegin求△1if△1为整数thenbegin求n1；if(n1为整数)and(n1≤k)Thenbegin输出m和n1；halt;endend;｛then｝求△2；if△2为整数thenbegin求n2；if（n2为整数）and（n2≤k）thenbegin输出m和n2;halt;endend;{then}m←m－l;end;{while}上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件──1≤k≤109。如果K值超过105，上述算法不可能在限定的15秒内出解。【分析】方法二分析小数据会发现：m,n是Fibonacci数列的相邻两项。因为：（n2－mn－m2）2＝1故：（m2+mn－n2）2＝1又：m2＋mn－n2＝(m＋n)2－mn－2n2＝(m＋n)2－(m＋n)n－n2故：（m2＋mn－n2）2＝[(m＋n)2－(m＋n)n－n2]2即：（n2－mn－m2）2＝[(m＋n)2－(m＋n)n－n2]2【分析】由上述数学变换式可以得出，如果m和n为一组满足条件①和条件②的解，设n’＝m＋n，m’＝n那么n’，m’也是一组满足条件①和条件②的一组解。将所有满足条件①和条件②的m和n按递增顺序排成一个Fibomacci数列｛1，1，2，3，5，8，……｝数列中小于k的最大两个相邻数即为试题所要求的一组m和n。算法：利用Fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2＋n2的值最大。Gauss消元示例•2x1+x2-x3=-1•X1+x2+x3=2•X1-x2+2x3=6Kathy函数(HNCOI)•Tiger非常喜欢数学，所以他参加了学校组织的数学课外兴趣小组。在兴趣小组的学习当中，老师向Tiger介绍了Kathy函数，Kathy函数是这样定义的：•)(2)12(3)34()()12(2)14()()2(3)3(1)1(nfnfnfnfnfnfnfnfff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(1kn)，与P1、Pn共同构成一个三角形的三个顶点，就将n边形分成了三个不相交的部分(如图3所示)，我们分别称之为区域①、区域②、区域③，其中区域③必定是一个三角形，区域①是一个凸k边形，区域②是一个凸n-k+1边形。P1Pn①②③图3P2P3PkPn--1分析•区域①的拆分方案总数是Ck，区域②的拆分方案数为Cn-k+1，故包含△P1PkPn的n边形的拆分方案数为CkCn-k+1种，而Pk可以是P2，P3，……，Pn-1种任一点，根据加法原理，凸n边形的三角拆分方案总数为，同时考虑到计算的方便，约定边界条件C2=1。P1Pn①②③图4P2P3PkPn--1112inniiCC分析=C(2n,n)/(n+1)112inniiCC具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递推式)1(1)12(*2)(nfnnnf再进行递推计算，并且注意类型的定义要用comp型。Catalan数的应用（部分和序列）•n个+1，n个-1构成2n项•a1,a2,a3,a4,,,,,,a2n其部分和满足a1+a2+......ak(k=1,2,3,...2n)=0的数列个数。Catalan数的应用（加括号）序列a1a2..ak的元素顺序保持不变，按不同结合方式插入合法圆括号对的方案数。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操作）。使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下表为由123生成序列231的过程。步骤0123456操作数序列1232333栈1211311输出序列2223231Catalan数的应用（栈NOIp2003）结合定义我们很容易能发现：如果进栈看成1，出栈看成0，在任何一位上累计的“0”的个数不大于累计的“1”的个数，因为必须在栈里有数的情况下才能向外弹数。原题转化为——n个1和n个0组成一个2n位的二进制数，要求从左到右扫描，“0”的累计数不大于“1”的累计数，求满足条件的数有多少