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

数学类问题 精度处理（高精度、实数处理） 组合数学问题（Fibonacci数列、第二类数 、卡特兰数、POLYA原理、排列组合计数 、加法原理与乘法原理） 进制问题（特定二进制串的统计、二分查 找、利用二进制进行路径、状态描述、二 进制转换） 数学类问题 递推与递归关系（递推关系式、通项公式 、数列、博弈问题） 数位、数字、特定数值的查找、统计（数 值处理、质因子分解、幂次分解、数值表 达式、添加运算符、分式与实数运算） 数学杂题（回文数字、矩阵处理、约瑟夫 与反约瑟夫问题） 数学剪枝（无解判定、解线性方程组、限 定搜索范围） 数学类问题的思维过程 相关公式、定理、原理的应用 寻找规律、归纳整理递归与递推关系式 按照数学方法构造、二进制转化等技巧性处理 注意事项： 规律准确（小数据手工推算、搜索程序验证） 数据类型是否合理、数据范围是否超界（大数据处 理） 整数划分问题（一） 最优分解方案 将一个整数n分成若干个互不相同的数的和 ，使得这些数的乘积最大。其中 1=1,j=1,2,， k,k=1 11,mN) 初始（边界条件）为F(0,m)=1 (m0) 目标状态为F（N，N）。 例题例题4 4：极值问题（最高时限15s） 已知m、n为整数，且满足下列两个条件： m、n1，2，K ，（1K109） (n 2mnm2)21 编一程序，由键盘输入K，求一组满足上述两个条 件的m、n，并且使m2n2的值最大。例如，若K 1995，则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）为整数且小于 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 ，上述算法不可能在限定的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， 数列中小于k的最大两个相邻数即为试题所要求的一 组m和n。 算法：利用Fibomacci数列顺推m,n，求出在条件范围 内的m,n最大值，此时m2n2的值最大。 例题例题5 5：Kathy函数(HNCOI) Tiger非常喜欢数学，所以他参加了学校组织的 数学课外兴趣小组。在兴趣小组的学习当中，老师 向Tiger介绍了Kathy函数，Kathy函数是这样定义的 ： 例题例题5 5：Kathy函数(HNCOI) Tiger对Kathy函数产生了浓厚的兴趣，他通过 研究发现有很多的数n都满足f(n)=n,对于一个给定的 数m，他希望你求出所有的满足f(n)=n (n=0的数列个数 。 Catalan数的应用（加括号） 序列a1a2ak的元素顺序保持不变，按不同结 合方式插入合法圆括号对的方案数。 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 的过程。 步骤0123456 操作数序 列 1232333 栈 1211311 输出序列 2223231 Catalan数的应用（栈 NOIp2003 ） 结合定义我们很容易能发现：如果进栈看成1，出栈看成0，在任何一位上累计的“0” 的个数不大于累计的“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)我们用穷举法可以找到 如下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) * W(k1)+W(k2) 分析 构造法 “构造法”解题，就是构造数学模型解决 问题。包括直接构造问题解答的模型，图 论模型，网络流模型以及组合数学模型。 构造法解题的思路或步骤 构造法解题的类型： v直接构造问题解答。这只是构造法运用的一种简单类 型。它只能针对问题本身，探索其独有性质，不具备可 推广性。 v数学建模。通过沿用经典的数学思想建立起模型；或 者提取现实世界中的有效信息，用简明的方式表达其规 律，这种规律可以是一条代数公式、一幅几何图形，一 个物理原理、一个化学方程式，等等。 无论是直接构造问题解答还是构造数学模型，都要通 过算法实现。如何设计一个有较低编程复杂度和时空 复杂度且结构清晰的算法，十分重要。通常考虑的因 素有 v选择的模型必须尽量多地体现问题的本质特征。但 这并不意味着模型越复杂越好，累赘的信息会影响算 法的效率。 v模型的建立不是一个一蹴而就的过程，而是要经过 反复地检验、修改，在实践中不断完善。 v数学模型通常有严格的格式，但程序编写形式可不 拘一格。 利用数学方法进行构造 例1：求Fibonacci数列 定义：f0=f1=1, fn=fn-1+fn-2(n=2)。fi称为 Fibonacci数列。 输入n，求fn mod q。其中1为 G中的一条哈密尔顿回路，其中所含的边的集合 记为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时 构造图象，充分展示各变量之间的关系 【例二】01串问题(NOI99) 给定N,L0,A0,B0,L1,A1,B1，设计一个长度为 N的01串，使得对于任何连续的长度为L0的 子串，0的个数大于等于A0,且小于等于B0, 对于任何连续的长度为L1的子串，1的个数 大于等于A1且小于B1。 【解题分析】 模式1 分析不等式 设hi为01子串s0si(1=L0时，根据条件，Si-L0+1Si中0的个数 (L0-(hi-hi-L0)在a0b0之间，即a0=L1时，根据条件，Si-L1+1 Si中1的个数(hi-hi- L1)在a1b1之间，即a1,表明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。 （