Loading... ## 数列 数列是以正整数集（或它的有限子集）为定义域的函数，是一列有序的数。数列中的每一个数都叫做这个数列的项。排在第一位的数称为这个数列的第$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 至今） #### 存储设备 - 只读存储器（**R**ead **O**nly **M**emory）：存储的内容是固定不变的，只能读出而不能写入的**半导体**存储器，作用有固定存储数据、表格、固化程序，且在组合逻辑电路中有广泛用途。 - 随机存取存储器（**R**andom **A**ccess **M**emory ）：既能读出又能写入的半导体存储器，任何RAM中存储的信息在**断电**后均会**立即**丢失。 - 高速缓冲存储器（Cache）: 是位于CPU和主存储器之间的⾼速存储器，容量较小但速度很快。CPU的速度远大于内存，当CPU直接从内存中存取数据时要等待一定时间，高速缓冲存储器则可以保存CPU刚用过或循环使用的部分数据，如果CPU需要再次使用该部分数据时可从Cache中直接调用。 - 寄存器 （Register） ： 是[中央处理器内用来暂存指令、[数据](https://zh.wikipedia.org/wiki/數據)和地址。寄存器的存贮容量有限，读写速度非常快。在计算机体系结构里，寄存器存储在已知时间点所作计算的中间结果，通过快速地访问数据来加速计算机程序]的运行。   ### 软件 #### 网络通信 ##### 局域网分类 - 广域网（WAN）跨接很大范围，如一个国家。 - 城域网（MAN）覆盖1个城市 - 局域网（LAN） 范围在几百米到几十千米的网络 ##### 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]_{\text{origin}}= 0000 0001 $$ $$ [-1]_{\text{origin}}= 1000 0001 $$ 8位二进制中数的取值范围为：$[1111 1111,0111 1111] $即$ [ - 127,127]$ ###### 反码 正数的反码是其本身。负数的反码是在其原码的基础上，符号位不变，其余各个位取反。 e.g. $$ [+1] = [00000001]_{\text{origin}}= [00000001]_{\text{complement}} $$ $$ [-1] = [10000001]_{\text{origin}}= [11111110]_{\text{complement}} $$ ###### 补码 正数的补码就是其本身 负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1，即在反码的基础上+1 e.g. $$ [+1] = [00000001]_{\text{origin}}= [00000001]_{\text{complement}}= [00000001] $$ ### 计算机发展史与某知名协会 #### 某知名协会 中国计算机学会创办于1962年，创办全国青少年计算机程序设计竞赛时间：1984年。 #### 第一个计算机 - 第一台电子计算机： ENIAC； - 第一台具有存储程序功能的计算机：EDVAC - 图灵机： 通用计算机模型，是抽象的机器 <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/495.html">https://www.starroad.top/archives/495.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：September 19th, 2020 at 09:45 am © 允许付费转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
退役选手无能为力。
可惜呀
退役选手无能为力（o(////▽////)q
何不再试试呢？总不能没拿提一就退吧
你得让CCF让我试
高三？或者今年NOIP(非CSP
支持，真心不错！
写的不错,谢谢分享