ACM竞赛之数学基础

1、第10讲:ACM竞赛之数学基础10.1 组合数学研究对象 组合数学研究的主要内容是依据一定的规则来安排某些事务的有关数学问题。这些问题包括四个方面： 1. 这种安排是否存在，即存在性问题 2. 如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题 3. 怎样构造这种安排，即算法构造问题 4. 如果给出了最优化标准，又怎样得到得到最优安排第10讲:ACM竞赛之数学基础10.1 组合数学1. 存在性问题实际生活中的各种问题，有些可以当机立断判定其有解还是无解。但也有不少问题一时难以判定。例如，宴会上，奇数位客人能否在晚会上与他人握手奇数次竞赛时不可能出现专门判定某个问题有解或无解的试题。

2、但往往会在测试数据中加入无解的数据。第10讲:ACM竞赛之数学基础10.1 组合数学2. 计数问题如果一个组合问题的解是存在的，自然会问有多少不同解例如，将8个“车”放在88的国际象棋棋盘上，如果他们两两不能互吃，那么称8个“车”处于一个安全状态。显然这种安全状态是存在的。问有多少种不同的安全状态。 这就是一个计数问题。一般分为两种类型：一种是计算某种特性的对象有多少；另一种是枚举类型，把所有具有某种特性的对象都列举出来。第10讲:ACM竞赛之数学基础10.1 组合数学3. 构造性算法一个组合问题，已经判定解是存在的，甚至已经推知有多少解，但关键还在于把解构造出来，有的哪怕出一个解也好。如魔方

3、问题，正交拉丁问题。第10讲:ACM竞赛之数学基础10.1 组合数学4. 优化问题一个问题的构造性算法可能不止一种，自然面临如何择优，如何改进，使得答案尽快地解出来。比如动态规划和线性规划问题的解决方法。第10讲:ACM竞赛之数学基础10.1 组合数学组合问题的基本解题方法1. 从组合学基本概念基本原理出发的常规方法容斥原理Polya原理鸽巢原理递归方法生成函数方法第10讲:ACM竞赛之数学基础10.1 组合数学组合问题的基本解题方法2. 通常与问题所涉及的组合数学概念无关的非常规方法。主要用于解那些需要独立思考见解独到和有所创新的问题。 数学归纳法第10讲:ACM竞赛之数学基础10.1 组合

4、数学组合问题的基本解题方法3. 殊途同归方法 从不同的角度讨论计数问题，以建立组合等式 例如，对没有三条对角线交于一点的凸多边形，计算各边及对角线所组成的互不重叠的区域个数。第10讲:ACM竞赛之数学基础10.1 组合数学组合问题的基本解题方法4. 数论方法运用奇偶性，整除性等数论性质进行存在性问题的分析与推理。例子：设n位客人，在晚会上每人与他人握手d次，d是奇数，证明n是偶数。第10讲:ACM竞赛之数学基础10.3 数论常见的数论问题 1. 数的幂运算 2. 欧拉定理的应用 3. 素数测试4. Pell方程5. 其它 第10讲:ACM竞赛之数学基础10.4 计算几何基本概念点线（线段，直线

5、）面（三角形，圆，多边形（凸，凹）体（空间几何）第10讲:ACM竞赛之数学基础10.4 计算几何点 Pointtypedef struct TPoint double x; double y; /double z;TPoint;第10讲:ACM竞赛之数学基础10.4 计算几何线段 Segmenttypedef struct TSegment TPoint t2; Tsegment;第10讲:ACM竞赛之数学基础10.4 计算几何直线 Linetypedef struct TLine /直线方程的系数 double a, b, c;TLine; ax + by + c = 0第10讲:ACM竞赛

6、之数学基础10.4 计算几何射线 radialtypedef struct TRadial TPoint p; TPoint INF;(无穷远出一点)TRadial;第10讲:ACM竞赛之数学基础10.4 计算几何三角形 Triangletypedef struct TTriangle TPoint t3;TTriangle;第10讲:ACM竞赛之数学基础10.4 计算几何圆 Circletypedef struct TCircle double r; TPoint centre;TCircle;第10讲:ACM竞赛之数学基础10.4 计算几何多边形 Polygontypedef struct

7、 TPolygon TPoint pMaxNode; int n;TPolygon; 第10讲:ACM竞赛之数学基础10.4 计算几何点线面之间的关系点与点点与线点与面点与圆点与多边形线与线线与面面与面第10讲:ACM竞赛之数学基础10.4 计算几何点与点（距离）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); 多维矢量（空间）点的距离与此类似第10讲:ACM竞赛之数学基础10.4

8、计算几何点与线点是否在直线上点是否在线段上点到直线的距离点关于直线的对称点第10讲:ACM竞赛之数学基础10.4 计算几何点与面点是否在平面点到平面的距离第10讲:ACM竞赛之数学基础10.4 计算几何点与多边形点是否在圆内（到圆心的距离）点是否在多边形内第10讲:ACM竞赛之数学基础10.4 计算几何线与线判断两条线段是否相交判断线段与直线是否相交判断直线与直线是否相交若相交求交点第10讲:ACM竞赛之数学基础10.4 计算几何线与面线与圆（线与圆的关系）直线划分多边形第10讲:ACM竞赛之数学基础10.5 概率论随机数在现实计算机上无法产生真正的随机数，在概率算法中使用的随机数都是一定程度

9、上随机的，即伪随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,an满足其中b0，c0，dm。d称为该随机序列的种子。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。第10讲:ACM竞赛之数学基础10.5 概率论数值概率算法：用随机投点法计算值 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而 public static double darts(int n) / 用随机投点法计算值 int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+