ACM竞赛之数学基础.ppt

《ACM竞赛之数学基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10讲:ACM竞赛之数学基础10.1组合数学1.存在性问题实际生活中的各种问题，有些可以当机立断判定其有解还是无解。但也有不少问题一时难以判定。例如，宴会上，奇数位客人能否在晚会上与他人握手奇数次竞赛时不可能出现专门判定某个问题有解或无解的试题。但往往会在测试数据中加入无解的数据。第10讲:ACM竞赛之数学基础10.1组合数学2.计数问题如果一个组合问题的解是存在的，自然会问有多少不同解例如，将8个“车”放在8×8的国际象棋棋盘上，如果他们两两不能互吃，那么称8个“车”处于一个安全状态。显然这种安全状态是存在的。问有多少种不同的安全状态。这就是一个计数问题。一般

2、分为两种类型：一种是计算某种特性的对象有多少；另一种是枚举类型，把所有具有某种特性的对象都列举出来。第10讲:ACM竞赛之数学基础10.1组合数学3.构造性算法一个组合问题，已经判定解是存在的，甚至已经推知有多少解，但关键还在于把解构造出来，有的哪怕出一个解也好。如魔方问题，正交拉丁问题。第10讲:ACM竞赛之数学基础10.1组合数学4.优化问题一个问题的构造性算法可能不止一种，自然面临如何择优，如何改进，使得答案尽快地解出来。比如动态规划和线性规划问题的解决方法。第10讲:ACM竞赛之数学基础10.1组合数学组合问题的基本解题方法1.从组合学基本概念基本原理出发

3、的常规方法容斥原理Polya原理鸽巢原理递归方法生成函数方法第10讲:ACM竞赛之数学基础10.1组合数学组合问题的基本解题方法2.通常与问题所涉及的组合数学概念无关的非常规方法。主要用于解那些需要独立思考见解独到和有所创新的问题。数学归纳法第10讲:ACM竞赛之数学基础10.1组合数学组合问题的基本解题方法3.殊途同归方法从不同的角度讨论计数问题，以建立组合等式例如，对没有三条对角线交于一点的凸多边形，计算各边及对角线所组成的互不重叠的区域个数。第10讲:ACM竞赛之数学基础10.1组合数学组合问题的基本解题方法4.数论方法运用奇偶性，整除性等数论性质进行存在性

4、问题的分析与推理。例子：设n位客人，在晚会上每人与他人握手d次，d是奇数，证明n是偶数。第10讲:ACM竞赛之数学基础10.3数论常见的数论问题1.数的幂运算2.欧拉定理的应用3.素数测试4.Pell方程5.其它第10讲:ACM竞赛之数学基础10.4计算几何基本概念点线（线段，直线）面（三角形，圆，多边形（凸，凹））体（空间几何）第10讲:ACM竞赛之数学基础10.4计算几何点PointtypedefstructTPoint{doublex;doubley;//doublez;}TPoint;第10讲:ACM竞赛之数学基础10.4计算几何线段Segmenttype

5、defstructTSegment{TPointt[2];}Tsegment;第10讲:ACM竞赛之数学基础10.4计算几何直线LinetypedefstructTLine{//直线方程的系数doublea,b,c;}TLine;ax+by+c=0第10讲:ACM竞赛之数学基础10.4计算几何射线radialtypedefstructTRadial{TPointp;TPointINF;(无穷远出一点)}TRadial;第10讲:ACM竞赛之数学基础10.4计算几何三角形TriangletypedefstructTTriangle{TPointt[3];}TTria

6、ngle;第10讲:ACM竞赛之数学基础10.4计算几何圆CircletypedefstructTCircle{doubler;TPointcentre;}TCircle;第10讲:ACM竞赛之数学基础10.4计算几何多边形PolygontypedefstructTPolygon{TPointp[MaxNode];intn;}TPolygon;第10讲:ACM竞赛之数学基础10.4计算几何点线面之间的关系点与点点与线点与面点与圆点与多边形线与线线与面面与面第10讲:ACM竞赛之数学基础10.4计算几何点与点（距离）doubledistance(TPointp1,T

7、Pointp2){//计算平面上两个点之间的距离TPointp;p.x=p1.x–p2.x;p.y=p1.y–p2.y;returnsqrt(p.x*p.x+p.y*p.y);}多维矢量（空间）点的距离与此类似第10讲:ACM竞赛之数学基础10.4计算几何点与线点是否在直线上点是否在线段上点到直线的距离点关于直线的对称点第10讲:ACM竞赛之数学基础10.4计算几何点与面点是否在平面点到平面的距离第10讲:ACM竞赛之数学基础10.4计算几何点与多边形点是否在圆内（到圆心的距离）点是否在多边形内第10讲:ACM竞赛之数学基础10.4计算几何线与线判断两条线段是否相

8、交判断线段