数学与程序设计ppt课件.ppt

数学与程序设计 引例 问题描述 有一个自然数n 在他的首尾两端添上一个1 由于1是自然数之首 便形成一个 两头蛇数 1N1 如果 两头蛇 数1N1正好是原自然数N的k倍 问n是多少 现在请你编程解决 两头蛇数 程序设计中的数学 数论组合数学母函数计算几何 程序设计中的数学 基本数论组合数学计算几何容斥原理母函数 初等数论 整除同余素数 指数取余 输入整数m n k 求mnmodk的值 其中m n k为自然数 m n在长整形范围内 k 46340 次数压缩 同余 穷举 mmodk n 389mod7 89 64 16 8 131 3 mod7 32 32 mod7 2 mod7 34 32 2 mod7 22 mod7 438 34 2 mod7 42 mod7 2316 38 2 mod7 22 mod7 4332 316 2 mod7 42 mod7 2364 332 2 mod7 22 mod7 4389 364 316 38 31 mod7 5 mod7 质多项式 给定多项式f x an xn an 1 xn 1 a0 x0 如果an0 我们称f x 是一个n次多项式 类似自然数里质数的概念 也可以给出 质多项式 概念 给定多项式f x 如果找不到次数至少为1的多项式g x 和h x 满足f x g x h x 我们称f x 为质多项式 为了简化起见 我们规定多项式的系数只能取两个数 0或1 并且重新定义在 0 1 上的加法和乘法如下 0 0 00 1 11 0 11 1 00 0 00 1 01 0 01 1 1如 x2 x1 x1 1 x3 x2 x2 x1 x3 x1对于给定的正整数k 求出次数为k的质多项式 如 输入1输出x 1输入5输出x 5 x 2 1 质多项式解题思路 寻找质数 穷举穷举k次的多项式 检验能否被已经找到的质多项式整除 若不能则本身也是质多项式 多项式除法 0 0 00 1 11 0 11 1 00 0 00 1 01 0 01 1 1加法 XOR乘法 正常减法 XOR除法 正常 x3 x x 1 x2 x 程序设计中的数学 基本数论组合数学计算几何容斥原理母函数 平行四边形的个数 把三角形ABC的三边各n等分 过各等分点作各边的平行线 将三角形ABC分割成一些小平行四边形 计算这些小平行四边形的个数 就一类平行四边形进行讨论 方程的解 已知方程x1 x2 x3 xm n其中x1 a1 x2 a2 xm am且 求方程的非负整数解的组数 令x1 x1 a1 x2 x2 a2 xm xm am x1 x2 xm P 程序设计中的数学 基本数论组合数学计算几何容斥原理母函数 蜂族的旅行 和其他昆虫不同 为了不至于迷路 蜜蜂在蜂巢 紧密连接的正六边形 中行走必须遵守一定的路线 把一个正方形的中心看作原点 如果一只蜜蜂要从A x1 y1 点飞到B x2 y2 点 且AB不在同一六边形的话 那么它必须按照蜂族的飞行规则 首先飞到包含A点的正六边形的中心 然后每次都只能从一个正六边形的中心飞到和它相邻的六边形中心 直到它飞到包含B点的正六边形的中心为止 然后再飞往B点 知道正六边形的边长d与A B点的坐标 算出蜜蜂的飞行距离 A B都不会刚好落在某个六边形的边上 样例1 0 3 22 23 307 737 蜂族的旅行 A B在同一六边形 直接计算直线距离如何判断两点在同一正六边形 确定所在的六边形并计算到顶点的距离 从A B经过的六边形个数 程序设计中的数学 基本数论组合数学计算几何容斥原理母函数 小虫问题 在一个7 7的方格中 每个小方格内都有一条小虫 约定在同一个时刻方格中的小虫必须向周围 上下左右4个方向 爬一格 证明 在爬了一格之后 至少有一个小方格是空的 被绘坏的玉米地 哈姆 外星人又在那了 埃塞和哈姆他们的玉米地是长方形的 每年在丰收之前 他们的玉米地都会很奇怪的遭到毁坏 据埃塞说是外星人干的 所有破坏的地方都是以1米为半径的圆 哈姆发现 如果玉米地上建立一个适当的直角坐标系的话 那些圆心的坐标将都为整数 万幸的是 埃塞和哈姆有玉米保险 但必须把损坏的面积统计出来 程序设计中的数学 基本数论组合数学计算几何容斥原理 母函数 质数分解问题 任何大于1的自然数n 都可以写成若干个大于等于2 且小于等于n的质数之和表达式 包括只有一个数构成的和表达式的情况 并且可能有不止一种质数和的形式 例如9的质数和表达式就有四种本质不同的形式 9 2 2 5 2 2 2 3 3 3 3 2 7 自然数n 2 n 200 可以写成多少种本质不同的质数和表达式 母函数 给定数列a0 a1 an 构造一函数F x a0f0 x a1f1 x anfn x 称F x 为数列a0 a1 an 的母函数 序列f0 x f1 x fn x 称为标志函数 F x a0 x0 a1x1 anxn 普通型母函数 设从n元集合S a0 a1 an 中取个元素的组合为bk 若限定元素ai出现的次数不超过mi 则该组合数系列的母函数为 砝码称重 有重量为1 3 5克的砝码各两个 问 1 可以称出多少种不同重量的物品 2 若要称出重量为7克的物品 所使用的砝码有多少种本质不同的情况 G x 1 x x2 1 x3 x6 1 x5 x1