简单数学类问题及其数学构造方法.ppt

数学类问题 精度处理 高精度 实数处理 组合数学问题 Fibonacci数列 第二类数 卡特兰数 POLYA原理 排列组合计数 加法原理与乘法原理 进制问题 特定二进制串的统计 二分查找 利用二进制进行路径 状态描述 二进制转换 数学类问题 递推与递归关系 递推关系式 通项公式 数列 博弈问题 数位 数字 特定数值的查找 统计 数值处理 质因子分解 幂次分解 数值表达式 添加运算符 分式与实数运算 数学杂题 回文数字 矩阵处理 约瑟夫与反约瑟夫问题 数学剪枝 无解判定 解线性方程组 限定搜索范围 数学类问题的思维过程 相关公式 定理 原理的应用寻找规律 归纳整理递归与递推关系式按照数学方法构造 二进制转化等技巧性处理注意事项 规律准确 小数据手工推算 搜索程序验证 数据类型是否合理 数据范围是否超界 大数据处理 整数划分问题 一 最优分解方案将一个整数n分成若干个互不相同的数的和 使得这些数的乘积最大 其中1 n 1000 分析 初看此题 最容易相到的算法是搜索 但此题的 最大可以达到1000 搜索肯定会超时 而本题所给的限制条件也不多 即便是加上一些剪枝也起不到很好的效果 一般遇到这种情况我们可以从简单的数据分析起 在解一些问题的时候 特别是用数学方法解的问题 当我们无从解决时 可以从简单的数据考虑起 以便发现其中的一些规律 这种作法对解题是很有帮助的 n分解方案MUL52 3662 4873 41283 51592 3 424102 3 530 观察这几组数据 不难发现所有的分解方案的数的个数都等于 可以分出的最多个数 其实我们并不难想到 要想使乘积最大 应尽量使分得的数多 另一方面 我们在初中数学中就已经证明过当数 正数 的和相等时 数的差越小 数的积也就越大 因此我们可以在分的数的个数最多的情况下使数之间的差尽量小 这样得出来的方案必定是最优的 整数分划 二 例题2 若干个正整数之和为n 其中 n 2000 试求它们乘积的最大值以及该最大值的位数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 m 1 mN 初始 边界条件 为F 0 m 1 m 0 目标状态为F N N 例题4 极值问题 最高时限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 分析 再考虑条件 由于n 1 因此排除了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的值最大 例题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 k n 与P1 Pn共同构成一个三角形的三个顶点 就将n边形分成了三个不相交的部分 如图3所示 我们分别称之为区域 区域 区域 其中区域 必定是一个三角形 区域 是一个凸k边形 区域 是一个凸n k 1边形 分析 区域 的拆分方案总数是Ck 区域 的拆分方案数为Cn k 1 故包含 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数的应用 加括号 序列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的过程 Catalan数的应用 栈NOIp2003 结合定义我们很容易能发现 如果进栈看成1 出栈看成0 在任何一位上累计的 0 的个数不大于累计的 1 的个数 因为必须在栈里有数的情况下才能向外弹数 原题转化为 n个1和n个0组成一个2n位的二进制数 要求从左到右扫描 0 的累计数不大于 1 的累计数 求满足条件的数有多少 任务 你的程序将对给定的n 计算并输出由操作数序列1 2 n经过操作可能得到的输出序列总数 分析 n个数 分别为1 n 排成一个长度为n的排列 若每一个数的位置都与数的本身不相等 则称这个排列是一个错排 例如 n 3 则错排有231 312 编写程序 求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 k 1 的某一个数互换 其他k 2个数进行错排 这样可以得到 k 1 W k 2 个错位排列 B 另一部分是将前k 1个元素的每一个错位排列 有W k 1 个 中的每一个数与k互换 这样可以得到剩下的 k 1 W k 1 个错位排列 根据加法原理 我们得到求错位排列的递推公式W k W k k 1 W k 1 W k 2 分析 构造法 构造法 解题 就是构造数学模型解决问题 包括直接构造问题解答的模型 图论模型 网络流模型以及组合数学模型 构造法解题的思路或步骤 构造法解题的类型 直接构造问题解答 这只是构造法运用的一种简单类型 它只能针对问题本身 探索其独有性质 不具备可推广性 数学建模 通过沿用经典的数学思想建立起模型 或者提取现实世界中的有效信息 用简明的方式表达其规律 这种规律可以是一条代数公式 一幅几何图形 一个物理原理 一个化学方程式 等等 无论是直接构造问题解答还是构造数学模型 都要通过算法实现 如何设计一个有较低编程复杂度和时空复杂度且结构清晰的算法 十分重要 通常考虑的因素有选择的模型必须尽量多地体现问题的本质特征 但这并不意味着模型越复杂越好 累赘的信息会影响算法的效率 模型的建立不是一个一蹴而就的过程 而是要经过反复地检验 修改 在实践中不断完善 数学模型通常有严格的格式 但程序编写形式可不拘一格 利用数学方法进行构造 例1 求Fibonacci数列 定义 f0 f1 1 fn fn 1 fn 2 n 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 hi hi l0 当I L0时 根据条件 Si L0 1 Si中0的个数 L0 hi hi L0 在a0 b0之间 即a0 L0 hi hi L0 b0 a0 L0 hi L0 hi b1 hi l1 hi 当I L1时 根据条件 Si L1 1 Si中1的个数 hi