acm 常用的数学公式

常用公式    2 划分问题：    3 Stirling公式    3 皮克定理    3 卡特兰数    4 错排公式    4 等比数列    5 等差数列    5 二次函数    6 二次方程    7 约瑟夫环    7 多边形面积    7 均值不等式的简介    8 均值不等式的变形    8 Lucas 定理    9 斐波那契数列    10 欧拉函数    11 蚂蚁爬绳    12 (a/b)%m    13 泰勒公式    13 乘法与因式分解公式    14 三角不等式    14 某些数列的前n项和    15 二项式展开公式    15 三角函数公式    16 常用公式 三角不等式 |a+b|≤|a|+|b| |a-b|≤|a|+|b| |a|≤b<=>-b≤a≤b |a-b|≥|a|-|b| -|a|≤a≤|a|   一元二次方程的解 -b+√(b2-4ac)/2a -b-√(b2-4ac)/2a 根与系数的关系 X1+X2=-b/a X1*X2=c/a 注：韦达定理 数列前n项和 1+2+3+4+5+6+7+8+9+…+n=n(n+1)/2 1+3+5+7+9+11+13+15+…+(2n-1)=n2 2+4+6+8+10+12+14+…+(2n)=n(n+1) 12+22+32+42+52+62+72+82+…+n2=n(n+1)(2n+1)/6 13+23+33+43+53+63+…n3=n2(n+1)2/4 1*2+2*3+3*4+4*5+5*6+6*7+…+n(n+1)=n(n+1)(n+2)/3 常用数学公式 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf :解析几何公式 圆的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 方程 (x-a)2+(y-b)2=r2 注：（a,b）是圆心坐标 圆的一般方程 x2+y2+Dx+Ey+F=0 注：D2+E2-4F>0 抛物线标准方程 y2=2px y2=-2px x2=2py x2=-2py 常用数学公式表:几何图形公式 直棱柱侧面积 S=c*h 斜棱柱侧面积 S=c'*h 正棱锥侧面积 S=1/2c*h' 正棱台侧面积 S=1/2(c+c')h' 圆台侧面积 S=1/2(c+c')l=pi(R+r)l 球的表面积 S=4pi*r2 圆柱侧面积 S=c*h=2pi*h 圆锥侧面积 S=1/2*c*l=pi*r*l 弧长公式 l=a*r (a是圆心角的弧度数r>0) 扇形面积公式 s=1/2*l*r 锥体体积公式 V=1/3*S*H 圆锥体体积公式 V=1/3*pi*r2h 柱体体积公式 V=s*h 圆柱体 V=pi*r2h 斜棱柱体积 V=S'L (S'是直截面面积，L是侧棱长) 注：pi=acos(-1.0); 划分问题： 1、 n个点最多把直线分成C(n,0)+C(n,1)份； 2、n条直线最多把平面分成C(n,0)+C(n,1)+C(n,2)份； 3、n个平面最多把空间分成C(n,0)+C(n,1)+C(n,2)+C(n,3)=(n³+5n+6)/6份； 4、n个空间最多把“时空”分成C(n,0)+C(n,1)+C(n,2)+C(n,3)+C(n,4)份. Stirling公式 lim(n→∞) √(2πn) * (n/e)^n  = n!   也就是说当n很大的时候,n!与√(2πn) * (n/e) ^ n的值十分接近 这就是Stirling公式. (2πn) ^0.5× n^ n × e^(-n) =n!; 皮克定理 一个多边形的顶点如果全是格点，这多边形就叫做格点多边形。有趣的是，这种格点多边形的面积计算起来很方便，只要数一下图形边线上的点的数目及图内的点的数目，就可用公式算出。   这个公式是皮克(Pick)在1899年给出的，被称为“皮克定理”，这是一个实用而有趣的定理。   给定顶点坐标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积S和内部格点数目a、边上格点数目b的关系：   S=a+ b/2 - 1。 (其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积) 卡特兰数 原理: 令h(1)＝1,h(0)=1，catalan 数满足递归式：   h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2) 另类递归式： h(n) = h(n-1)*(4*n-2)/(n+1);   该递推关系的解为：   h(n)=C(2n,n)/(n+1) (n=1,2,3,...)   卡特兰数的应用 （实质上都是递归等式的应用） 错排公式 当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.   第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法; 第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法; 综上得到递推公式：   M(n)=(n-1)[M(n-2)+M(n-1)]    特殊地，M(1)=0,M(2)=1 通项公式： M(n)=n![(-1)^2/2!+…+(-1)^(n-1)/(n-1)!+(-1)^n/n!] 优美的式子： Dn=[n!/e+0.5],[x]为取整函数．  公式证明较简单．观察一般 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 上的公式，可以发现e-1的前项与之相同，然后作比较可得/Dn-n!e-1/<1/(n+1)<0.5,于是就得到这个简单而优美的公式（此仅供参考） 等比数列 (1) 等比数列： a (n+1)/an=q  (n∈N)。 (2) 通项公式： an=a1×q^(n-1)； 推广式： an=am×q^(n-m)； (3) 求和公式： Sn=n*a1 (q=1) Sn=a1(1-q^n)/(1-q) =(a1-an*q)/(1-q)   (q≠1)  (q为比值，n为项数） (4)性质： ①若 m、n、p、q∈N，且m＋n=p＋q，则am*an=ap*aq； ②在等比数列中，依次每 k项之和仍成等比数列. ③若m、n、q∈N，且m+n=2q，则am*an=aq^2 (5)"G是a、b的等比中项""G^2=ab（G ≠ 0）". (6)在等比数列中，首项a1与公比q都不为零. 注意：上述公式中an表示等比数列的第n项。 等差数列 1、 Sn=n(a1+an)/2 2、 Sn=a1*n+n(n-1)d/2 an=a1+(n-1)d Sn＝（a1＋an）*n/2 项数＝（末项-首项）÷公差＋1 A1=2*S/n-an an=2*S/n-a1 an=a1+（n-1）*d; 性质： 若 m、n、p、q∈N ①若m＋n=p＋q，则am+an=ap+aq ②若m+n=2q，则am+an=2aq 注意：上述公式中an表示等差数列的第n项。 二次函数 定义与定义表达式 1：一般式： y=ax^2;+bx+c  (a≠0，a、b、c为常数) 对称轴为直线x = -b/2a，顶点坐标(-b/2a,(4ac-b^2)/4a)。 2：顶点式： y=a(x-h）^2+k  或  y=a(x+m)^2+k (两个式子实质一样,但初中课本上都是第一个式子)（若给出抛物线的顶点坐标或对称轴与最值，通常可设顶点式） 3：交点式（与x轴）： y=a(x-x1)(x-x2) （若给出抛物线与x轴的交点及对称轴与x轴的交点距离或其他一的条件，通常可设交点式） 重要概念： （a，b，c为常数，a≠0，且a决定函数的开口方向，a>0时，开口方向向上，a<0时，开口方向向下。a的绝对值还可以决定开口大小,a的绝对值越大开口就越小,a的绝对值越小开口就越大。）   y＝ax2＋bx＋c＝   ＝   ＝   ＝ 二次方程 a*x+b*y+c=0; 当△<0 ，方程无解； 当△=0 ，x1=x2= -b/(2*a)； 当△>0 ，x1= [-b-sqrt(b*b-4*a*c)]/(2*a)，x2=[-b+ sqrt(b*b-4*a*c)]/(2*a)。 约瑟夫环 令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]. 递推公式:   f[1]=0;   f=(f[i-1]+m)%i; (i>1) 　有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f，程序也是异常简单： 多边形面积 点顺序给出 S=0.5*abs(x1*y2-y1*x2+x2*y3-y2*x3+...+xn*y1-yn*x1) 均值不等式的简介 概念： 1、调和平均数： Hn=n/(1/a1+1/a2+...+1/an) 2、几何平均数： Gn=(a1a2...an)^(1/n)=n次√(a1*a2*a3*...*an) 3、算术平均数： An=(a1+a2+...+an)/n 4、 平方平均数： Qn=√ [(a1^2+a2^2+...+an^2)/n] 5、 这四种平均数满足: Hn≤Gn≤An≤Qn a1、a2、… 、an∈R +，当且仅当a1=a2= … =an时取“=”号 均值不等式的一般形式： 设函数D(r)=[（a1^r+a2^r+...an^r）/n]^(1/r)  (当r不等于0时); (a1a2...an)^(1/n)(当r=0时）（即D(0)=(a1a2...an)^(1/n)） 则有：当r0>-2ab   (2)对非负实数a,b，有a+b≥2√(a*b)≥0，即(a+b)/2≥√(a*b)≥0   (3)对负实数a,b，有a+b<0<2√(a*b)   (4)对实数a,b，有a(a-b)≥b(a-b)   (5)对非负数a,b，有a^2+b^2≥2ab≥0   (6)对非负数a,b，有a^2+b^2 ≥1/2*(a+b)^2≥ab   (7)对非负数a,b,c，有a^2+b^2+c^2≥1/3*(a+b+c)^2   (8)对非负数a,b,c，有a^2+b^2+c^2≥ab+bc+ac   (9)对非负数a,b，有a^2+ab+b^2≥3/4*(a+b)^2 (10)对实数a,b,c，有(a+b+c)/3>=(abc)^(1/3) (11) a^3+b^3+c^3>=3abc,a、b、c都是正数。 扩展：若有y=x1*x2*x3.....Xn 且x1+x2+x3+...+Xn=常数P,则Y的最大值为((x1+x2+x3+.....+Xn)/n)^n 1、| |a|-|b| |≤|a-b|≤|a|+|b|     2、| |a|-|b| |≤|a+b|≤|a|+|b| 设a1,a2,…an；b1,b2…bn均是实数，且a1≥a2≥a3≥…≥an,b1≥b2≥b3≥…≥bn;则有a1b1+a2b2+…+anbn（顺序和）≥a1b2+a2b1+a3b3+…+aibj+…+anbm（乱序和）≥a1bn+a2bn-1+a3bn-2+…+anb1（逆序和）,仅当a1=a2=a3=…an,b1=b2=b3=…=bn时等号成立。 Lucas 定理 斐波那契数列 欧拉函数 实际使用的时候是用下面这个式子： 在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素) (1) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a; (2) 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1); 欧拉函数的值 （小于等于1的正整数中唯一和1互质的数就是1本身）。 若n是质数p的k次幂，，因为除了p的倍数外，其他数都跟n互质。 欧拉函数是积性函数，即是说若m,n互质，。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，和C可建立双射(一一对应)的关系。因此的值使用算术基本定理便知， 若 则 。 例如 先看（2）式，N%a==0 && (N/a)%a!=0，因为a是质数，而N/a不能被a整除，说明N/a与a互质，由上面的可知E(N)=E(N/a)*E(a);而E(a)=a-1 （因为按照欧拉函数定义欧拉函数是小于或等于n的正整数中与n互质的数的数目，a为质数，从1到a-1都和a互质，所以E(a)=a-1）,故E(N)=E(N/a)*(a-1); 再看（1）式，由于a是N/a的质因数，不能像（2）一样用上面的积性函数的公式。那看这个式子 ，假设E(n)可以表示成a^k*(a-1)*C，C为后面的部分，则E(n/a)可以表示成a^(k-1)*(a-1)*C，比较两式的差别可以得到E(n)是E(n/a)的a倍，即E(N)=E(N/a)*a。 其实，（2）式也可以像（1）式一样证明，因为N/a与a互质，说明N的质因数有且只有一个a，则E(n)可表示为(a-1)*C，E(N/a)可表示为C，比较两式差别可以得到E(N)=E(N/a)*(a-1). 蚂蚁爬绳 一绳长L米，一蚂蚁从绳的一端爬向另一端，速度为每秒v m/s，同时，绳子以每秒u 米的速度均匀伸长，问：蚂蚁能否达到绳的另一端？如能，需多长时间？如不能，请说明理由。（假设绳子质量无限好，蚂蚁寿命无限长） T=[e(u/v)-1]*L/u; (a/b)%m 背景：a是b的倍数 1.如果m是质数，很简单，直接用扩展的欧几里德求b关于m的逆元 对于 a/b%m = ans, 求 ans。 a = a%m, b = b%m ans = (a % m)*(x % m) % m  （x为b的逆元） 求逆元则利用扩展欧几里德： 对于 b*x = 1(mod m) 可以求b*x + m*y = 1的解（ 用extennd_Euclid(b, m, x, y) )! 然后把 x 映射到 [0,m)区间，带入上式， 即得解。 2.如果m不是质数，把m质数分解成质数p1,p2,……,pk的积   然后把a分解成a1*a2，其中a1的质因数只能在p[]中，a2与p[]中的所有质数都互质，即a2与m互质   同理把b分解成b1*b2，其中b1的质因数只能在p[]中，b2与p[]中的所有质数都互质，即b2与m互质 3.现在问题变成了(a1*a2)/(b1*b2)%m，即(a1/b1)%m*(a2/b2)%m。   问题分解成了两个问题:   对于a1/b1%m，可以化为: (p1^m1*p2^m2*……*pk^mk)/(p1^n1*p2^n2*……*pk^nk)%m，  即:p1^(m1-n1)*p2^(m2-n2)*……*pk^(mk-nk)%m 对于a2/b2%m，b2与m互质，则可以直接求出b2关于m的逆元化为a2*b2^(-1)%m. 4.于是，问题解决，时间复杂度约为O(sqrt(m) + log(m)) 泰勒公式 乘法与因式分解公式 1.2 1.4   三角不等式 2.1 2.2 2.3 2.4 2.6   某些数列的前n项和   4.2    4.3        4.7     二项式展开公式 三角函数公式 1  两角和公式 2  倍角公式 6.5 6.6 3  半角公式    4  和差化积