ACM竞赛中的数学方法初步课件.ppt

1、ACM竞赛中的数学方法初步计算几何 所谓计算几何,一般就指向量方法来解几何问题.为什么用向量?因为解析几何方法在很多时候都显得复杂,而且计算可能比较复杂,有精度损失问题.坐标法基础 计算几何都是以坐标化为前提的 必须知道一些基本的解析几何的方法.例如:两点距离的公式等向量的点积 向量a,b点积(又称内积)的几何意义是a在b(或b在a)上的投影长度(标量,注意可能为负值).计算方法是ab=|a|b|cosC,其中,C是向量a,b的夹角(下同).若向量a=(x1,y1,z1),b=(x2,y2,z2),则 ab=x1x2+y1y2+z1z2 cosC可以由此计算出来应用 用于计算向量夹角.判断两向

2、量是否垂直 平面方程的向量形式:平面方程ax+by+cz=0(已通过移坐标轴去掉常数项),令平面法向量n=(a,b,c),点X(x,y,z),则平面方程记为nX=0,实际上,如果平面过点P,则方程为n(X-P)=0.应用(续)还可以计算点P(x0,y0,z0)到平面nX=0的距离.把n单位化,不妨仍记为n,把向量OP往n上投影,即可得距离d=|n OP|.判断P是否在平面的哪一边:n OP为正时P在n指向的一侧,否则与n的指向相反向量叉积 叉积又称外积,ab的结果是一个矢量,其数值是以a,b为边的平行四边形面积,即|a|b|sinC,其方向和a,b都垂直,并且,a,b,ab构成右手系.计算方法

3、:222111,zyxzyxkjiba应用 计算三角形或者平行四边形面积 计算点到直线(进一步,线段)的距离 判断向量(或者直线,线段)平行关系 内积和外积结合可以判断复杂的位置关系点的旋转变换 原来的点(x,y)和变换后的点(x,y)的坐标之间满足下面的公式:x=xcos-ysin y=xsin+ycos 其中,是逆时针旋转的角度,这个公式适用于旋转点在原点的情况.球面距离 已知球半径R,球面上两点A,B的坐标A(x1,y1,z1),B(x2,y2,z2),球心在原点O,球面距离2arccosROBOARRd 已知两点的极坐标 ,其中,为经度数,为纬度数,则可以证明球面距离为 极坐标与直角坐

4、标之间的换算关系:其中,是纬度,是经度 已知极坐标,也可以先用上面的公式计算直角坐标,然后算球面距离,但是会有精度损失coscoscos sinsinxRyRzR计算几何进一步的话题 内容很丰富,以上列举的是基本的武器 参加ACM竞赛至少还需要了解二维凸包的算法(比较复杂)例题 BOJ1012 The Circumference of the Circle 给出了三个点的坐标，请输出由这三个点所确定的圆的周长，结果保留二位小数 如图,关键是求出外接圆半径R ABC 可以由向量外积算出面积s,并得到sinA.由正弦定理,a/sinA=2R 由此可以计算外接圆面积ABCabcBOJ1062 Pol

5、ygon Programming with Ease 给了n边形的n条边的中点,求n个顶点的坐标,n是奇数 可以建立两个(x坐标和y坐标)联系n个顶点和n个中点的n元一次方程组,注意到n是奇数,这样的方程有唯一解另一种思路 可以证明以下事实:将一个n边形依次以其每边中点为对称中心做中心对称(反射)变换,n次变换之后,等价于对此多边形做了一个以第一个顶点为中心,180度的旋转变换.可以任意选定一个点p,依次对每个中心做反射变换,n次之后得到q,则第一个顶点是(p+q)/2,由此可以得到其它顶点BOJ1054 Equidistance 给定球面两点A,B的极坐标,再给定第三点P的极坐标,求球面上到

6、A,B两点距离相等的点(组成一个大圆O1)到P点的最短球面距离 首先,把极坐标转换成直角坐标.以a,b,p代表A,B,P对应的向量.到A,B距离相等的点集构成一个平面,法向量是a-b,过点(a+b)/2,圆O1在这个平面上 向量a-b和p之间的夹角theta可以比较容易计算出来(使用内积方法和反三角函数),用球半径乘以theta的余角即可以得出所求球面距离.注意特殊情况:如果AB两点重合,则整个球面上的点到AB的距离都是相等的,那么P点到AB的距离也是相等的,所以此时所求的球面距离为P到自身的距离,为零.需要单独处理BOJ1059 Balanced Food 给了扇形的桌子和其上的圆形pizz

7、a的位置和大小,pizza被切成若干块(第一刀是沿x轴正向来切的),求一个取pizza的顺序,使得pizza不从桌子上掉下来 如右图,左边的两块pizza先取下面的后取上面的,可以不掉下来,右边的pizza一定会掉下来扇形重心公式 如果剩下的pizza的重心不在桌子上,pizza会掉下来.剩下的pizza的重心就是所有pizza片的几何中心(坐标的算术平均值),pizza片的重心可以通过积分手算出来sin32cos0202RddrrddrrdsxdsxRRssC 由此可以算得每块pizza片的重心坐标,计算剩下来的这些pizza片的重心坐标的算术平均值就得到整块剩下的pizza的重心(记做C)

8、坐标.下面的问题是判断C是否在桌子上.判断重心是否在桌上 如图,tuv是桌子,c是pizza的重心坐标.注意到桌子不会比半圆更大,并且tuv是按照逆时针标号,于是得到c不在桌子上有以下情形:tutc0 dist(t,c)dist(t,u)ctuv 实际上,还有更初等的判断方法,就是通过内积计算utc+ctv与 utv是否相等,不等就说明c不在桌上.只是,此法需要计算反三角函数,可能会损失精度.下面的问题是,如何来取这些pizza片才能使得整块pizza不掉下去呢?吃pizza的顺序 如果注意到n的大小只有10,那么可以考虑最稳妥的方法:回溯搜索.就是把所有可能的排列情况按照字典顺序都搜索一遍,

9、找到第一个可行的顺序就退出搜索.如果搜索完成之后都没有找到可行的取法,说明没有可行方法存在.时间复杂度O(n!)具体方法,如果你曾写过求迷宫的所有可行路的程序,应该很容易实现.以上是深度优先搜索的策略 实际上,本题使用贪心策略也是可以AC的(未能证明)每次都选一块编号最小的可行的pizza片,如果某一步进行不下去,就退出报告无可行取法.时间复杂度O(n2).题外话 本题的操作比较复杂,使用标准C+的算法库配合复数类,可以简化操作,但是要求熟悉上述工具.BOJ1072 Global Roaming 给了卫星的极坐标,球面上一些点的极坐标,判断哪些点可以看到卫星 解法甚多,以下为一种可能是比较简单

10、的 考虑地球上一点的切平面,它的法向量从地心指向该点.下面只需要判断卫星位于切平面的那一侧即可,这是我们已经解决的问题.初等数论 初等数论的内容也是比较多的,本次主要介绍素数的测试,数的整除性和跟同余有关的一些知识.素数测试 这是数论里的一个基本问题,而且现代社会应用也很广泛,发展了很多算法.首先要知道下面的方法.给了一个数n,从i3开始到n的算术根以步长2进行循环，如果n都不能整除i，那么n就是一个素数 这种方法效率比较低,判断一个数需要O(n1/2)的时间复杂度Eratosthenes筛法筛法(续)筛法并不仅用于计算素数,它还用于很多其它类似机理的场合(如BOJ1074 Assistanc

11、e Required)例如,计算Euler函数时,可以利用筛法来标号概率型算法 注意到上述两种方法其实都是比较慢的,为了快速判断是否素数,出现了多种测试素数的方法 Miller-Rabin测试:基于Fermat小定理的测试,一次测试把一个合数判断成素数的概率小于1/4,多次测试使得犯错误的概率更小.参加ACM竞赛需要知道这个算法,具体细节可在网上找到唯一分解定理 每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现,换句话说,任意正整数n可以写成n=2a1*3a2*5a3*,其中a1,a2,a3等为非负整数,这称为n的素因子标准分解式数的整除性 令a和b是不全为0的两个整数，能

12、使d|a和d|b的最大整数称为a和b的最大公约数，用gcd(a,b)表示，或者记为(a,b)令a和b是不全为0的两个整数，能使a|d和b|d的最小整数称为a和b的最小公倍数，用lcm(a,b)表示，或者记为a,b 定理:ab=gcd(a,b)*lcm(a,b)GCD的计算 计算gcd(m,n),使用Euclid除法:while(mn?(m%=n):(n%=m);GCD为m,n中的非零数,也可以写为m+n.时间复杂度O(logn),若mn 上面为循环算法,可以写出递归算法.GCD的计算(2)如果(a,b)=d,则一定存在整数x,y,使得xa+yb=d.求x,y,仍然使用(扩展的)Euclid算法

13、(递归实现):int gcd(int a,int b,int&x,int&y)if(!b)x=1;y=0;return a;else int r=gcd(b,a%b,x,y);t=x;x=y;y=t a/b*y;return r;同余 设m是一个正整数,若a,b是整数,且m|(a-b),则称a和b模m同余,记做ab(mod m)整数的一种分类方法:给了一个整数m,则可以把整数按照除m的余数分为m类.特别地,m=2时,分为奇数和偶数同余性质 设m是正整数,则下面命题成立:(i)b1a1(mod m),b2a2(mod m),则:b1b2a1a2(mod m),b1b2a1a2(mod m)若ac

14、bd(mod m),cd(mod m),且(m,c)=1,则ab(mod m)Euler函数 定义:1n中和中和n互素的正整数个数互素的正整数个数记做(n),即为Euler函数 Euler函数的性质:(mn)=(m)(n),m,n是互素正整数.设正整数为n的素因子标准分解式,则:上述两条性质可以用于计算Euler函数的数值 涉及计算Euler函数值的ACM赛题,可以参见POJ2480 Longges problem,POJ2478 Farey Sequence kekeepppn2121)11()11)(11()(21kpppnnEuler定理 设k是与正整数m互素的整数,则k(m)1(mod

15、 m)推论(Fermat小定理):设p是素数,若p不能整除k,则kp-11(mod p)中国剩余定理(孙子定理)设m1,m2,mk是k个两两互素的正整数,任给k个整数a1,a2,ak,必存在整数x,使得xai(mod mi)(i=1,2,k),且在0=xM=m1m2mk内有唯一解 从此定理的证明过程我们可以得到求出x具体算法 记Mi=M/mi，则(Mi,mi)=1 存在pi,qi，Mipi+miqi=1 记录ei=Mipi，则 j=i时ei1(mod mj)Ji时ei0(mod mj)则e1a1+e2a2+ekak就是一个解,调整(加减M)得到0,m)内的唯一解.此算法用到先前的(扩展的)Eu

16、clid除法 此问题的一个实例可以参看POJ1006 Biorhythms BOJ1040 Goldbachs Conjecture 给了偶数n,求两个素数a,b,使得n=a+b,并且b-a的值最大.使用筛法选出一个到1000000的素数表,然后从i=3开始枚举素数,遇到合适的就停下来BOJ1074 Assistance Required 也是筛法的例子,把2的倍数筛掉,再把3的倍数筛掉,求剩下来的数中的第n个.在筛的过程中,把没有筛掉的放到一个数组中,可以直接输出第n个数.BOJ1008 Happy 2004 2004x的所有因数的和,除以29的余数是多少?首先,根据Fermat小定理,20

17、04281(mod 29),根据同余性质,200428n1(mod 29).又知(a+b)%c=(a%c+b%c)%c,(ab)%c=(a%c)(b%c)%c简化计算的因子 考虑2004x的因子,把它们分成以下几类:是2004x-28n的因子,当然也是2004x的因子 不是2004x-28n的因子,但是2004x的因子 首先说明,第二类因子的和模29等于0.2004=22*3*167,根据同余性质,只需要考虑4,3,22(=167%29)作为2004的因子.令y=x-28n,则第二类因子必然可以写为ay*2s*3r*22t的形式,其中a=22,3,22证明细节 在上述表达式中,2s*3r*22

18、t一定是200428n的因子.从而,s,r,t一定可以取遍128n(s到56n)的值.固定r,t的取值,对s求和,只需证明say*2s*3r*22t%29=0,其中y,r,t是常数.上式等价于证明s2s%29=0,s=1,56n,由等比数列求和公式得到s2s=256n-1.另一方面,根据Fermat小定理,2281(mod 29),从而256n-1%29=0,得证.求解 我们只需要考虑2004y的因子的和模29.其中y=x%28.2004y的素因子标准分解式为22y3y167y,只需考虑形如22s*3r*22t(s,r,t=y28)的因子.可以通过枚举法得出所有因子.进一步,这些因子的和模29

19、的结果就可以得出来了 优化建议 不用考虑所有因子,只分别考虑4,3,22的幂这部分因子的和模29的结果,相乘后再模29可得最后结果.依据:求余操作可以与加法和乘法交换次序.基于上面的结果,注意到这些幂的指数最大到27,可以做三个表,分别存放4,3,22的幂的和模29的结果.如p4i表示0=s=1 J(2n+1)=2J(n)+1,n=1 从上面的公式,可到下面的表 n12345678J(n)11313571n910111213141516J(n)35791113151猜测:J(2m+t)=2t+1,0=t2m(*)数学归纳法证明 m=0时,t=0,(*)式表明,J(1)=1,成立.假定m-1时成

20、立,往证m时成立 若t为偶数,J(2m+t)=2J(2m-1+t/2)-1=2(2*t/2+1)-1=2t+1,(*)成立 若t为奇数,J(2m+t)=2J(2m-1+t/2)+1=2(2*t/2+1)+1=2t+1,(因为t=2t/2+1).(*)成立进一步讨论 对于编程而言,给了n,我们需要知道m.2m提示我们考虑n二进制形式.事实上,n的二进制形式的最高位刚好是第m+1位(为什么?)把这一位1变成0,就得到t,然后把t左移一位,得到2t,最后加上1,就是最终的结果.问题 对于此问题的更一般的形式,大家可以自己试着讨论.可以参阅Concrete Mathematics1.3节BOJ1051 Let it bead 此题可以使用搜索来解,也可以使用组合计数的方法来解.使用后者需要牵涉到较多的数学知识(主要是置换群的知识),这里给出公式如下:这就是最后计算项链的穿法种数的公式,详细推导见另一个幻灯片121gcd(,)1022s1(,)s2()ssss issiscN G Ccscc当 为奇数当 为偶数2代数方法 代数方法在本次题目中几乎没有涉及 主要掌握高斯消去法解线性方程组,这次题目如BOJ1062即可以解方程组求解 注意有些赛题有意考察矩阵乘法及快速乘方,如ZOJ Monthly,October 2005 http:/