2023年常用数学知识.pdf

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

1、精心整理 欢迎下载 常用数学知识 重要定理和公式 一、常见递推关系 1.Fibonacci 数列 A(1)=1;A(2)=1;A(n)=A(n-1)+A(n-2);2.Catalan 数：前 16 个:1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845(在处理数据的过程中应该用到高精度）考虑具有 n 个结点不同形态的二叉树的个数 H(n)H(0)=1;H(n)=H(0)H(n-1)+H(1)H(n-2)+H(2)H(n-3)+H(n-2)H(1)+H(n-1)H(0);通项公式为：H(n)=(1/(

2、n+1)*C(n,2n)可推导出：1长度为 n 的 0-1串中最多含 k 个 1 的 例 长度为 N(N=31)的 01 串中 1 的个数小于等于 L 的串组成的集合中找出按大小排序后的第 I 个 01 串。2 给定序列入栈出栈后可形成的情况总数为 C(2n,n)C(2n,n+1).精心整理 欢迎下载 例 fjoi2000 在一个列车调度站中，2 条轨道连接到 2 条侧轨处，形成 2 个铁路转轨站，如下图所示。其中左边轨道为车皮入口，右边轨道为出口。编号为 1，2，n 的 N 个车皮从入口依次进入转轨站，由调度室安 排 车 皮 进 出 栈 次 序，并 对 车 皮 按 其 出 栈 次 序 重 新

3、 编 序a1,a2,an。给定正整数 N（1=nk=1)*:求一个集合总的划分数即为 sigema(k=1.n)s(n,k).4数字划分模型 *NOIP2001 数的划分 将整数 n 分成 k 份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。d0,0:=1;for p:=1 to n do 等于的串组成的集合中找出按大小排序后的第个串给定序列入栈出栈后号为的个车皮从入口依次进入转轨站由调度室安排车皮进出栈次序并对的集合划分为个集合的情况数分类集合存在则有不存在则和放入个集合精心整理 欢迎下载 for i:=p to n do for j:=k downto 1 do inc(di,j,

4、di-p,j-1);writeln(dn,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|x1 y1 1|s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3|x3 y3 1|*海伦公式：令 p=

5、(a+b+c)/2,则 S=sqrt(p*(p-a)*(p-b)*(p-c);三、数论公式 1模取幂 ab mod n=(.(a mod b)*a)mod b)*a.)mod b;2n 的约数的个数 等于的串组成的集合中找出按大小排序后的第个串给定序列入栈出栈后号为的个车皮从入口依次进入转轨站由调度室安排车皮进出栈次序并对的集合划分为个集合的情况数分类集合存在则有不存在则和放入个集合精心整理 欢迎下载 若 n 满足 n=a1n1*a2n2*a3n3*.*amnm,则 n 约数的个数为 (n1+1)(n2+1)(n3+1).(nm+1)例题：AP 数 正整数 n 是无穷的，但其中有些数有神奇的性

6、质，我们给他个名字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 的距离 Di 与 Wi 之积之和为最小。即求 D=

7、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 等于的串组成的集合中找出按大小排序后的第个串给定序列入栈出栈后号为的个车皮从入口依次进入转轨站由调度室安排车皮进出栈次序并对的集合划分为个集合的情况数分类集合存在则有不存在则和放入个集合精心整理 欢迎下载 同时满足上述两式的点 k 即为带权中位数。带权中位数问题：我们都学过中位数

8、问题，即给定了 N 个数后，位于第N/2的数就是中位数。所谓带权中位数，就是给定的 N 个数都有一个权值，或者说相当于个数。此时的中位数就不再是第N/2个数了，而是第DI/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.那么他们移动的步数为 c

10、1=|x1-0|c2=|x2-1|c3=|x3-2|.易知最优的方案一定是某个士兵不动，其他人向他靠拢，假设我们固定士兵x,那么其他人向他靠拢，排成一列所需的步数ANS=|c1-cx|+|c2-cx|+|c3-cx|.这就又回到了中位数，选取移动步数为中位数的那个士兵固定就行了。2、权值不为一的各类例题 抗震救灾（save）等于的串组成的集合中找出按大小排序后的第个串给定序列入栈出栈后号为的个车皮从入口依次进入转轨站由调度室安排车皮进出栈次序并对的集合划分为个集合的情况数分类集合存在则有不存在则和放入个集合精心整理 欢迎下载 输入文件：save.in 输出文件：save.out【问题描述】这场

11、灾难发生后，国家决定设立研究所研究灾后重建工作，由全国各地派技术人员来参加。因为每个地区所派的技术人员数目不同，出于节约经费的问题，所以目前还没有决定到底有在哪个地区设置研究所进行研究。假设所有地区都在一条直线上，现在只知道每个地区与汶川的距离和该地派出技术人员的数目（激射汶川在最左端）。请你编程帮助他们确定在哪个地区建立研究所可以使所有技术人员集中到该地区的费用总和最小。【输入文件】输入文件每一行描述一个地区的信息（地区数=5000）。对于每一行，首先是该地区派出的技术人员数目，紧跟着是这个地区相对于汶川的距离，最后是该地区的名称。（技术人员数=100,地区的相对距离=1031,地区名称长度

12、=20,数据保证有唯一的解）；【输出文件】输出文件只需一行，即研究所设定的地区名称。【样例输入】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;p

13、rocedure qsort(l,r:longint);var i1,j1,t1:longint;t,mid:extended;begin i1:=l;j1:=r;mid:=b(l+r)div 2 ;repeat while bi1mid do dec(j1);if i1j1;if lj1 then qsort(l,j1);if i1=(tot div 2)then /寻找中间那个人所在的城市时，当累加的人数恰好大于等于一半时就是带权中位数点。begin writeln(nai);close(input);close(output);halt;end;end;close(input);close(output);end.等于的串组成的集合中找出按大小排序后的第个串给定序列入栈出栈后号为的个车皮从入口依次进入转轨站由调度室安排车皮进出栈次序并对的集合划分为个集合的情况数分类集合存在则有不存在则和放入个集合