数学与程序设计.ppt
数学与程序设计数学与程序设计引例 问题描述问题描述有一个自然数有一个自然数n，在他的首尾两，在他的首尾两端添上一个端添上一个1，由于，由于1是自然数之首，便形是自然数之首，便形成一个成一个“两头蛇数两头蛇数”1N1。如果。如果“两头蛇两头蛇”数数1N1正好是原自然数正好是原自然数N的的k倍，问倍，问n是多少？是多少？ 现在请你编程解决。现在请你编程解决。两头蛇数100110.1.101000.1.10100.11.knNnkNnkNnk程序设计中的数学 数论 组合数学 母函数 计算几何 程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 初等数论 整除 同余 素数指数取余 输入整数输入整数m,n,k，求，求mn mod k的值。其中的值。其中m,n,k为为自然数（自然数（m,n在长整形范围内，在长整形范围内，k=46340）。）。ab (mod m)cd (mod m)acbd(mod m)次数压缩？次数压缩？同余同余 穷举穷举 (m mod k)n xkxxxn.321389 mod 7 89=64+16+8+1 313 (mod 7) 3232 (mod 7)2 (mod 7) 34(32)2 (mod 7)22 (mod 7)4 38(34)2 (mod 7)42 (mod 7)2 316(38)2 (mod 7)22 (mod 7)4 332(316)2 (mod 7)42 (mod 7)2 364(332)2 (mod 7)22 (mod 7)4 389(364)(316)(38)(31) (mod 7) 5 (mod 7) 质多项式 给定多项式 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+00 0+11 1+01 1+10 0*00 0*10 1*00 1*11 如：(x2+x1)(x1+1)=x3+x2+x2+x1=x3+x1 对于给定的正整数k，求出次数为k的质多项式。 如：输入 1 输出 x+1 输入 5 输出 x5+x2+1 质多项式解题思路 寻找质数 + 穷举 穷举k次的多项式，检验能否被已经找到的质多项式整除，若不能则本身也是质多项式。 多项式除法 * 0+00 0+11 1+01 1+10 0*00 0*10 1*00 1*11 加法：XOR 乘法：正常 减法：XOR 除法：正常x3+x 、 x+1 、 x2+x程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 平行四边形的个数平行四边形的个数 把三角形把三角形ABC的三边各的三边各n等分，过各等分点作等分，过各等分点作各边的平行线，将三角形各边的平行线，将三角形ABC分割成一些小平分割成一些小平行四边形，计算这些小平行四边形的个数。行四边形，计算这些小平行四边形的个数。就一类平行四边形进行讨论41nC31nC42nC方程的解方程的解 已知方程 x1+x2+x3+xm=n 其中x1=a1,x2=a2,xm=am 且miian1 求方程的非负整数解的组数 令x1= x1-a1, x2=x2-a2, xm= xm-am x1 + x2 + xm= P11mmpC程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 蜂族的旅行 和其他昆虫不同，为了不至于迷路，蜜蜂在蜂巢（紧密连接的正六边形）中行走必须遵守一定的路线。把一个正方形的中心看作原点。如果一只蜜蜂要从A(x1,y1)点飞到B(x2,y2)点，且AB不在同一六边形的话，那么它必须按照蜂族的飞行规则，首先飞到包含A点的正六边形的中心，然后每次都只能从一个正六边形的中心飞到和它相邻的六边形中心，直到它飞到包含B点的正六边形的中心为止，然后再飞往B点。 知道正六边形的边长d与A、B点的坐标，算出蜜蜂的飞行距离。（A、B都不会刚好落在某个六边形的边上）。 样例1.0 -3.2 2.2 3.3 07.737蜂族的旅行 A、B在同一六边形，直接计算直线距离 如何判断两点在同一正六边形？)3,0(kd pdypdx2323)233,23(pdkdpd12p3dy32233213232),(或或pdykdxdxpyx确定所在的六边形并计算到顶点的距离从AB经过的六边形个数程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 小虫问题 在一个7*7的方格中，每个小方格内都有一条小虫，约定在同一个时刻方格中的小虫必须向周围（上下左右4个方向）爬一格。 证明：在爬了一格之后，至少有一个小方格是空的。被绘坏的玉米地 “哈姆，外星人又在那了！”。埃塞和哈姆他们的玉米地是长方形的。每年在丰收之前，他们的玉米地都会很奇怪的遭到毁坏(据埃塞说是外星人干的)。所有破坏的地方都是以 1 米为半径的圆米为半径的圆。哈姆发现，如果玉米地上建立一个适当的直角坐标系的话，那些圆心的坐标将都为整数圆心的坐标将都为整数。万幸的是，埃塞和哈姆有玉米保险，但必须把损坏的面积统计出来。程序设计中的数学 基本数论 组合数学 计算几何 容斥原理 母函数 质数分解问题 任何大于 1 的自然数 n，都可以写成若干个大于等于 2 ，且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如9 的质数和表达式就有四种本质不同的形式： 9 = 2+2+5 = 2+2+2+3 = 3+3+3 = 2+7 。 自然数 n (2n200)可以写成多少种本质不同的质数和表达式。 母函数 给定数列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，则该组合数系列的母函数为：nimmmix10砝码称重 有重量为1，3，5克的砝码各两个，问 （1）可以称出多少种不同重量的物品？ （2）若要称出重量为7克的物品，所使用的砝码有多少种本质不同的情况？ G(x)=(1+x+x2)(1+x3+x6)(1+x5+x10)=1+x+x2+x3+x4+2x5+2x6+2x7+2x8+x9+2x10+2x11+2x12+2x13+x14+x15+x16+x17+x18 （1）19 （2）2
