《ACM竞赛之数学基础实用教案》由会员分享，可在线阅读，更多相关《ACM竞赛之数学基础实用教案（26页珍藏版）》请在金锄头文库上搜索。
1、第10讲:ACM竞赛之数学(shxu)基础10.1 组合(zh)数学2.计数问题如果一个组合问题的解是存在的，自然会问有多少不同解例如，将8个“车”放在88的国际象棋棋盘上，如果他们(tmen)两两不能互吃，那么称8个“车”处于一个安全状态。显然这种安全状态是存在的。问有多少种不同的安全状态。这就是一个计数问题。一般分为两种类型：一种是计算某种特性的对象有多少；另一种是枚举类型，把所有具有某种特性的对象都列举出来。第1页/共25页第一页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.1 组合(zh)数学3.构造性算法一个组合问题，已经(yjing)判定解是存在的，甚至已经(yjin
2、g)推知有多少解，但关键还在于把解构造出来，有的哪怕出一个解也好。如魔方问题，正交拉丁问题。第2页/共25页第二页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.1 组合(zh)数学4.优化问题一个问题的构造性算法可能不止一种，自然面临如何择优，如何改进，使得(shde)答案尽快地解出来。比如动态规划和线性规划问题的解决方法。第3页/共25页第三页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.1 组合(zh)数学组合(zh)问题的基本解题方法1.从组合(zh)学基本概念基本原理出发的常规方法容斥原理Polya原理鸽巢原理递归方法生成函数方法第4页/共25页第四页，共2
3、6页。第10讲:ACM竞赛(jngsi)之数学基础10.1 组合(zh)数学组合问题(wnt)的基本解题方法2.通常与问题(wnt)所涉及的组合数学概念无关的非常规方法。主要用于解那些需要独立思考见解独到和有所创新的问题(wnt)。数学归纳法第5页/共25页第五页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.1 组合(zh)数学组合问题(wnt)的基本解题方法3.殊途同归方法从不同的角度讨论计数问题(wnt)，以建立组合等式例如，对没有三条对角线交于一点的凸多边形，计算各边及对角线所组成的互不重叠的区域个数。第6页/共25页第六页，共26页。第10讲:ACM竞赛之数学(shxu)
4、基础10.1 组合(zh)数学组合问题的基本解题方法4.数论方法运用奇偶性，整除性等数论性质进行存在性问题的分析与推理。例子：设n位客人(krn)，在晚会上每人与他人握手d次，d是奇数，证明n是偶数。第7页/共25页第七页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.3 数论(shln)常见的数论问题1.数的幂运算2.欧拉定理的应用3.素数测试(csh)4.Pell方程5.其它第8页/共25页第八页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何基本概念n点点n线（线段，直线线（线段，直线(zhxin)）n面（三角形，圆，多边形（凸，凹）面（
5、三角形，圆，多边形（凸，凹）n体（空间几何）体（空间几何）第9页/共25页第九页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何点Pointtypedef struct TPoint double x; double y; /double z;TPoint;第10页/共25页第十页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何线段(xindun)Segmenttypedef struct TSegment TPoint t2; Tsegment;第11页/共25页第十一页，共26页。第10讲:ACM竞赛之数学(shx
6、u)基础10.4 计算(j sun)几何直线(zhxin)Linetypedef struct TLine /直线方程的系数 double a, b, c;TLine; ax + by + c = 0第12页/共25页第十二页，共26页。第10讲:ACM竞赛(jngsi)之数学基础10.4 计算(j sun)几何射线(shxin)radialtypedef struct TRadial TPoint p; TPoint INF;(无穷远出一点)TRadial;第13页/共25页第十三页，共26页。第10讲:ACM竞赛(jngsi)之数学基础10.4 计算(j sun)几何三角形Triangle
7、typedef struct TTriangle TPoint t3;TTriangle;第14页/共25页第十四页，共26页。第10讲:ACM竞赛(jngsi)之数学基础10.4 计算(j sun)几何圆Circletypedef struct TCircle double r; TPoint centre;TCircle;第15页/共25页第十五页，共26页。第10讲:ACM竞赛(jngsi)之数学基础10.4 计算(j sun)几何多边形Polygontypedef struct TPolygon TPoint pMaxNode; int n;TPolygon; 第16页/共25页第十六
8、页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何点线面之间的关系(gunx)n点与点n点与线n点与面n点与圆n点与多边形n线与线n线与面n面与面第17页/共25页第十七页，共26页。第10讲:ACM竞赛(jngsi)之数学基础10.4 计算(j sun)几何点与点（距离(jl)）double distance(TPoint p1, TPoint p2) /计算平面上两个点之间的距离TPoint p; p.x = p1.x p2.x; p.y = p1.y p2.y; return sqrt(p.x * p.x + p.y * p.y); 多维矢量（空间）
9、点的距离与此类似多维矢量（空间）点的距离与此类似第18页/共25页第十八页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何点与线n点是否在直线上n点是否在线段上n点到直线的距离(jl)n点关于直线的对称点第19页/共25页第十九页，共26页。第10讲:ACM竞赛(jngsi)之数学基础10.4 计算(j sun)几何点与面n点是否在平面(pngmin)n点到平面(pngmin)的距离第20页/共25页第二十页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何点与多边形n点是否(sh fu)在圆内（到圆心的距离）n点是否(
10、sh fu)在多边形内第21页/共25页第二十一页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何线与线n判断两条线段是否相交n判断线段与直线(zhxin)是否相交n判断直线(zhxin)与直线(zhxin)是否相交n若相交求交点第22页/共25页第二十二页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.4 计算(j sun)几何线与面n线与圆（线与圆的关系(gun x)）n直线划分多边形第23页/共25页第二十三页，共26页。第10讲:ACM竞赛之数学(shxu)基础10.5 概率论随机数&在现实计算机上无法产生真正的随机数，在概率算法在现实
11、计算机上无法产生真正的随机数，在概率算法(sun f)中使用的随机数都是一中使用的随机数都是一定程度上随机的，即伪随机数。定程度上随机的，即伪随机数。&线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,an满足满足其中其中b0，c0，dm。d称为该随机序列称为该随机序列(xli)的种子。从直观上看，的种子。从直观上看，m应取得充分大，因此可取应取得充分大，因此可取m为机器大数，另外应取为机器大数，另外应取gcd(m,b)=1，因此可，因此可取取b为一素数。为一素数。第24页/共25页第二十四页，共26页。谢谢(xi xie)大家观赏！第25页/共25页第二十五页，共26页。内容(nirng)总结第10讲:ACM竞赛之数学基础。如果一个组合问题的解是存在的，自然会问有多少不同解。如魔方问题，正交拉丁问题。2. 通常与问题所涉及的组合数学概念无关的非常规方法。第8页/共25页。/double z。/直线(zhxin)方程的系数。点与点。点与点（距离）。/计算平面上两个点之间的距离。判断直线(zhxin)与直线(zhxin)是否相交。由线性同余法产生的随机序列a0,a1,。第24页/共25页。谢谢大家观赏。第25页/共25页第二十六页，共26页。
