CSP第一轮认证知识点总结

数列

数列是以正整数集(或它的有限子集)为定义域的函数,是一列有序的数。数列中的每一个数都叫做这个数列的项。排在第一位的数称为这个数列的第$1$项(通常也叫做首项),排在第二位的数称为这个数列的第$2$项,以此类推,排在第$n$位的数称为这个数列的第$n$项,通常用$a_n$表示。

常数数列

定义

若一个数列的每一项都为一个相等的常数,数列${a_n}$为常数数列。

公式

$$ a_n=a_1(n \in N_+) $$

递推数列

定义

递推数列是可以递推找出规律的数列,找出这个规律的通项式就是解递推数列。

等差数列

定义

一般地,如果一个数列从第$2$项起,每一项与它的前一项的差等于同一个常数,这个数列就叫做等差数列,这个常数叫做等差数列的公差,公差通常用字母$d$表示,前$n$项和用$S_n$表示。等差数列可以缩写为A.P.

该数列形如

$$ a,a + d,a + 2d,\cdots,a + (n - 1) \cdot d $$

特别地,由三个数$a,x,b$组成的等差数列是最简单的等差数列。这时,$x$叫做$a$与$b$的等差中项。有关系:

$$ x=\cfrac{a+b}{2}。 $$

公式

$$ a_n=a_1+(n-1) \cdot d $$

$$ S_n=\cfrac{n(a_1+a_n)}{2} $$

等比数列

定义

等比数列是指从第二项起,每一项与它的前一项的比值等于同一个常数的一种数列,常用$G,P$表示。这个常数叫做等比数列的公比,公比通常用字母$q$表示$(q \neq 0)$,等比数列$a_1\neq 0$。其中${a_n}$中的每一项均不为$0$。

特别地,当且仅当$q=1$时,${a_n}$为常数数列。

公式

$$ \cfrac{a_n}{a_{n-1}}=q(n \geq 2,a_{n-1}\neq 0,q\neq 0) $$

$$ a_{n+1}=a_1\cdot q^n $$

$$ f(x)= \begin{cases} na_1& ({q=1})\\ {\cfrac{a_1 \cdot (1-q^n)} {1-q}}& ({q\neq 1}) \end{cases} $$

斐波那契数列

递推公式

斐波那契数列是$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \cdots$。这是一个线性递推数列。

公式

如果设$F_n$该数列的第$n$项$(n \in N_+)$,则

$$ F_n=\begin{cases}{F_{n-1}+F_{n-2}}& (n \lt 2)\\1& (n=1 \lor n=2)\end{cases} $$

$$ S_n=\sum_{i=0}^{n}f_i=f_{n + 2} - 1 $$

示例

  • 楼梯有$n$阶台阶,上楼可以一步上$1$阶,也可以一步上$2$阶,共有多少种不同的走法。
  • 有一对雌雄兔,每两个月就繁殖雌雄各一对兔子,问$n$个月后共有多少对兔子。
  • 有$2n$的一个长方形方格,用一个$1\times2$的骨牌铺满方格,求铺法总数。

分平面的最大区域数

直线分平面的最大区域数的数列

$$ 2,4,7,11,\cdots $$

$$ f_n = f_{n - 1} + n = \cfrac{n(n + 1)}{ 2} + 1 $$

折线分平面的最大区域数的数列为

$$ 2,7,16,29\cdots $$

$$ f_n = f_{n - 1} + 4(n - 1) + 1 = (n - 1)(2n - 1) + 2n $$

封闭曲线(如一般位置上的圆)分平面的最大区域数

$$ 2,4,8,14,\cdots $$

$$ f_n = f_{n - 1} + 2(n - 1) = n ^ 2 - n + 2 $$

Catalan 数列

公式

$$ h_n = \cfrac{h_{n-1} \cdot (4n - 2)}{ n + 1} $$

$$ h_{n} = \cfrac {c_{2n,n}}{ n + 1} (n \geq 0) $$

$$ h_n = c_{2n,n} - c_{2n,n - 1} (n \geq 0) $$

$$ h_{n+1} =\sum_{i=0}^n h_i · h_{n-1}(n \geq 2) $$

运用

  • $n$个结点可够造多少个不同的二叉树。
  • 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数。
  • 在圆上选择$2n$个点,将这些点成对连接起来使得所得到的$n$条线段不相交的方法数。
  • 一个进栈顺序为$1,2,3 \cdots ,n$的栈的出栈数列的种数。

第二类斯特林数

第二类斯特林数实际上是集合的一个拆分,表示将n个不同的元素拆分成m个集合的方案数,记为
$S(n,m)$。和第一类斯特林数不同的是,集合内是不考虑次序的,而圆排列是有序的。常常用于解决组合数学中几类放球模型。

公式

$$ S(n,1) = 1 $$

$$ S(n,0) = 0 $$

$$ S(n,n) = 1 $$

$$ S(n,m) = m \cdot S(n-1,m) + S(n-1,m-1) $$

排列组合

球放进盒子

以下,均为$n$个球,$m$个盒子。

有标号的球放进有标号的盒子

相当于为每个球选一个盒子放,答案为$m ^ n$

无标号的球放进有标号的盒子,每个盒子至多放一个

选$n$个盒子放球,答案为$C_m^n$

有标号的球放进有标号的盒子,每个盒子至多放一个

就是”无标号的球放进有标号的盒子,每个盒子至多放一个“情况可以交换球,答案为 $A_m^n$

有标号的球放进无标号的盒子,每个盒子至多放一个

怎么放都是一样的,答案为$[n \leq m]$

无标号的球放进无标号的盒子,每个盒子至多放一个

怎么放都是一样的,答案为$[n \leq m]$

无标号的球放进有标号的盒子,不允许有空盒

隔板法,$n-1$个空,挑$m-1$个位置插板, 答案为$C_{n-1}^{m - 1}$

无标号的球放进有标号的盒子

虚拟$m$个球,间隔一个球时为空盒,答案为$C_{n+m-1}^{m - 1}$

有标号的球放进有标号的盒子,不允许有空盒

枚举$i$个盒子是空的,转化为"无标号的球放进有标号的盒子"问题,答案为

$$ \sum_{i=0}^m (( - 1) ^ i \times C_m^i \times (m - i) ^ n) $$

有标号的球放进无标号的盒子,不允许有空盒

答案为第二类斯特林数。

有标号的球放进无标号的盒子

枚举多少个盒子放了球,答案为

$$ \sum_{i=0}^m S(n,i) $$

无标号的球放进无标号的盒子,不允许有空盒

DP,有两种方式转移,新开一个盒子放一个球,或将现有每个盒子都放一个球
答案为

$$ P(n,m) = P(n - 1,m - 1) + P(n - m,m) $$

无标号的球放进无标号的盒子

隔板法扩展,答案为$P(n + m,m)$

圆周排列

答案为$\cfrac{A_n^m} m$

有重复元素的排列问题

第$i$种物品有$a_i$个,共计$n$种,排成一排,有

$$ \cfrac{\sum_{i=1}^na_i}{\prod_{i=1}^na_i!} $$

种排列方法。

错排

公式

$$ d_n= (n - 1) \cdot (d_{n - 1} + d_{n - 2}) (n \geq 3) $$

$$ d_n = n \cdot d_{n - 1} + ( - 1) ^ n $$

示例

胸口贴着编号为$1,2,\cdots,n$ 的$n$个球员分别住在编号为$1,2,\cdots,n$的$n$个房间里面,现规定每个人住一个房间,自己的编号不能和房间的编号一样。

信息常识

硬件

输入设备

输入设备是向计算机输入数据和信息的设备如鼠标、键盘、扫描仪、麦克风、写字板等。

输出设备

输出设备是用于接收计算机数据的输出显示、打印、声音、控制外围设备操作等的设备。

参数

字长
  • 早期微型计算机:8位或16位
  • 586微机(Pentium):32位
储存容量
  • Windows 95 或 98 : 16 M
  • Windows XP : 128 M
运算速度
  • Pentium 300 : 300 MHz
  • Pentium Ⅲ / 800 : 800 MHz
  • Pentium 4 / 1.5G : 1.5 GHz

计算机元件

  • 第一代:电子管(1946 ~ 1958)
  • 第二代:晶体管(1959 ~ 1964)
  • 第三代:集成电路(1965 ~ 1970)
  • 第四代:大规模集成电路(1971 至今)

软件

IP地址

  • A类:首字节0、网络号8位、主机号24位(1.0.0.0~127.255.255.255)
  • B类:首字节10、网络号16位、主机号16位(128.0.0.0~191.255.255.255)
  • C类:首字节110、网络号24位、主机号8位(192.0.0.0~223.255.255.255)
  • D类:首字节1110、多播地址(224.0.0.0~239.255.255.255)
  • E类:首字节11110、目前尚未使用(240.0.0.0~247.255.255.255)

域名

格式:主机名.组织机构名.网络名.顶级域名

位运算的优先级

  • 按位取反(~)2级
  • 位移运算(<<,>>)6级
  • 按位与(&)9级
  • 按位异或(^)10级
  • 按位或(|)11级

算法(不一定是在计算机上用某种语言实现)

  • 有穷性: 算法的有穷性是指算法必须能在执行有限个步骤之后终止。
  • 确切性:算法的每一步骤必须有确切的定义。
  • 输入项:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件。
  • 输出项: 一个算法有一个或多个输出,以反映对输入数据加工后的结果,没有输出的算法是毫无意义的。
  • 可行性:算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)

源码、反码、补码

原码(人脑最容易理解和计算的表示方式)

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值
e.g.

$$ [+1] 原 = 0000 0001 [-1] 原 = 1000 0001 $$

8位二进制中数的取值范围为:$[1111 1111,0111 1111] $即$ [ - 127,127]$

反码

正数的反码是其本身。负数的反码是在其原码的基础上,符号位不变,其余各个位取反。
e.g.

$$ [+1] = [00000001] 原 = [00000001] 反 [-1] = [10000001] 原 = [11111110] 反 $$

补码

正数的补码就是其本身
负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后+1,即在反码的基础上+1
e.g.

$$ [+1] = [00000001] 原 = [00000001] 反 = [00000001] 补 [-1] = [10000001] 原 = [11111110] 反 = [11111111] 补

Last modification:October 18th, 2019 at 09:17 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment