2022年常用数学知识.docx

《2022年常用数学知识.docx》由会员分享，可在线阅读，更多相关《2022年常用数学知识.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 细心整理 欢迎下载常用数学学问重要定理和公式一、常见递推关系1.Fibonacci 数列 A1=1; A2=1; An=An-1 + An-2; 2.Catalan数：前 16 个: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 在处理数据的过程中应当用到高精度）考虑具有 n 个结点不同形状的二叉树的个数 Hn H 0 = 1; H n = H 0 H n-1 + H 1 H n-2 + H 2 H n-+ H n-1 H 0 ; 通项公式为：

2、H n = 1/ n+1 * C n, 2n 可推导出：1长度为 n 的 0-1 串中最多含 k 个 1 的3 + H n-2 H 1 例 长度为 N N=31的 01 串中 1 的个数小于等于 L 的串组成的集合名师归纳总结 中找出按大小排序后的第I 个 01 串；C2n, n C2n,n+1. 第 1 页,共 7 页2 给定序列入栈出栈后可形成的情形总数为- - - - - - -精选学习资料 - - - - - - - - - 细心整理 欢迎下载例 fjoi2000 在一个列车调度站中, 2 条轨道连接到 2 条侧轨处,形成 2 个铁路转 轨站,如下图所示；其中左边轨道为车皮入口,右边轨

3、道为出口；编 号为 1,2, , n 的 N 个车皮从入口依次进入转轨站,由调度室 安 排 车 皮 进 出 栈 次 序 , 并 对 车 皮 按 其 出 栈 次 序 重 新 编 序 a1,a2, ,an；给定正整数 N（1=nk=1 *:求一个集合总的划分数即为 4数字划分模型 *NOIP2001 数的划分sigemak=1.n sn,k . 将整数 n 分成 k 份,且每份不能为空,任意两种分法不能相同 不考 虑次序 ；d0,0:=1; for p:=1 to n do 名师归纳总结 - - - - - - -第 2 页,共 7 页精选学习资料 - - - - - - - - - 细心整理 欢

4、迎下载for i:=p to n do for j:=k downto 1 do incdi,j,di-p,j-1; writelndn,k; *变形 1：考虑次序 d i, j : = d i-k, j-1 k=1.i *变形 2：如分解出来的每个数均有一个上限 m d i, j : = d i-k, j-1 k=1.m 5错位排列 d1 = 0; d2 = 1; dn = n-1 * dn-1 + dn-2 二、图论与运算几何1度边定理：sigema di = 2*E 图中全部结点的度数之和等于边数的 2 倍 任意一个图肯定有偶数个奇点 2三角形面积 已知三点坐标求面积 ,s仍要除以 2

5、|x1 y1 1| s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3 |x3 y3 1| *海伦公式：令 p=a+b+c/2, 就 S=sqrtp*p-a*p-b*p-c; 三、数论公式 1模取幂 ab mod n= .a mod b*a mod b*a. mod b; 2n 的约数的个数名师归纳总结 - - - - - - -第 3 页,共 7 页精选学习资料 - - - - - - - - - 细心整理 欢迎下载如 n 满意 n=a1n1 * a2n2 * a3n3 * . * amnm,就 n 约数的个数为n1+1n2+1n3+1.nm+1 例题： AP

6、 数正整数 n 是无穷的,但其中有些数有奇妙的性质,我们给他个名字AP 数；对于一个数字 i 他是 AP 数的充要条件是全部比他小的数的因数个数都没有 i 的因数个数多；比如6 的因数是 1 2 3 6 共计有 4个因数；他就是一个 AP 数（1-5 的因数个数不是 2 就是 3）；我们题目的任务就是找到一个最大的,且不超过 n 的 AP 数；四、代数1 带权中位数我国蒙古大草原上有N（N 是不大于 100 的自然数）个牧民定居点P1（X1,Y1）、P2（X2,Y2）、 Pn（Xn,Yn）,相应地有关权重为 Wi,现在要求你在大草原上找一点P（Xp,Yp）,使 P 点到任 一点 Pi 的距离

7、Di 与 Wi 之积之和为最小；即求 D=W1*D1+W2*D2+ +Wi*Di+ +Wn*Dn 有最小值 结论：对 x 与 y 两个方向分别求解带权中位数,转化为一维；设正确点 p 为点 k,就点 k 满意：令 W 为点 k 到其余各点的带权距离之和,就 sigema i=1 to k-1 Wi*Di = W/2 sigema i=k+1 to n Wi*Di = W/2 名师归纳总结 - - - - - - -第 4 页,共 7 页精选学习资料 - - - - - - - - - 细心整理 欢迎下载同时满意上述两式的点 k 即为带权中位数；带权中位数问题：我们都学过中位数问题,即给定了N

8、个数后,位于第 N/2 的数就是中位数；所谓带权中位数,就是给定的 N 个数都有一个权值,或者说相当于个数； 此时的中位数就不再是第 DI/2 个数；N/2 个数了,而是第 而在信息学竞赛中, 有这样一类题, 给出了如干个排列在一条直线上 的点,每个点有一个权值,比如说货物量、人数什么的,然后让我们 找出访全部点的货物、 人集合到一个点的总代价最小的位置；我们将 会发觉,这一类问题实际上就是带权中位数问题；1、 权值为 1 的各类例题 士兵站队问题 问题：在一个划分成网格的操场上,n 个士兵散乱地站在网格点上；网格点由整数坐标 x,y 表 示；士兵们可以沿网格边上、下、左、右移动一步,但在同一

9、时刻任一网格点上只能有一名士兵；根据军官的命令, 士兵们要整齐地列成一个水平队列,即排列成 x,y,x+1,y, ,x+n-1,y；如何挑选 x 和 y 的值才能使士兵们以最少的总移动步数排成一列；由于 x、y 方向的移动是相对独立的,所以可以各自运算两个方向的移动方 案 y 方向上,由于最终都要集合到一个点,可以直接求各个士兵到中间那个人 的位移,为 y 方向的最小移动步数；X 方向上,并非集合到一个点,而是最终排成一条线,所以不能直接看作求 中位数；0,1,2,3,4, . 由于最终必需排作一条直线, 可以先把他们看成最终排到 等横坐标上设他们之前坐标为 x1 x2 x3 x4 .那么他们

10、移动的步数为 c1=|x1-0| c2=|x2-1| c3=|x3-2| . 易知最优的方案肯定是某个士兵不动,其他人向他靠拢,假设我们固定士兵x, 那么其他人向他靠拢,排成一列所需的步数 ANS=|c1-cx|+|c2-cx|+|c3-cx| .这就又回到了中位数,选取移动步数为中位数的那个士兵固定就行了；2、 权值不为一的各类例题 抗震救灾（ save）名师归纳总结 - - - - - - -第 5 页,共 7 页精选学习资料 - - - - - - - - - 细心整理 欢迎下载输入文件： save.in 输出文件： save.out【问题描述】这场灾难发生后,国家打算设立讨论所讨论灾后

11、重建工作,由全国各地派技术人员来参与；由于每个地区所派的技术人员数目不同,出于节省经费的问题,所以目前仍没有打算究竟有在哪个地区设置讨论所进行讨论；假设全部地区都在一条直线上, 现在只知道每个地区与汶川的距离和该地派出技术人员的数目（激射汶川在最左端） ；请你编程帮忙他们确定在哪个地区建立讨论所可以使全部技术人员集中到该地区的费用总和最小；【输入文件】输入文件每一行描述一个地区的信息（地区数 =5000）；对于每一行,第一是该地区派出的技术人员数目,紧跟着是这个地区相对于汶川的距离,最终是该地区的名称；（技术人员数 =100,地区的相对距离 =1031, 地区名称长度 =20,数据保证有唯独的

12、解）；【输出文件】输出文件只需一行,即讨论所设定的地区名称；【样例输入】7 9289 shengyan 5 8523 beijing 3 5184 guilin 8 2213 chongqing 10 0 wuhan【样例输出】chongqing 第一将其按距离从左到右排序,把人数视为点的权值；找出中间那个人所在的城市就行了；program fdfgd; var n,i,j,x,tot:longint; a:array1.5000 of longint; b:array1.5000 of extended; na:array1.5000 of string; s:string; procedu

13、re qsortl,r:longint; var i1,j1,t1:longint; t,mid:extended; begin i1:=l; j1:=r; mid:=bl+rdiv 2 ; repeat while bi1mid do decj1; if i1j1; if lj1 then qsortl,j1; if i1=tot div 2 then /查找中间那个人所在的城市时,当累加的人数恰好大于等于一半时就是带权中位数点；begin writelnnai; closeinput; closeoutput; halt; end; end; closeinput; closeoutput; end.名师归纳总结 - - - - - - -第 7 页,共 7 页