【考试】初赛复习

# 数学问题 ## 除法取模快速计算 $$a/b\%c=(a\%(b*c))/b$$ ## 错排问题 **错排：** $\forall i,a[i]\not= i$的排列方案数。设为$f(n)$，则有： 1. 保持$n$不动，剩下的$n-1$个数错排，然后把$n$与$\forall i\in [1,i-1]$交换，获得$n-1$个合法序列； 2. 将$n$与$\forall i\in [1,i-1]$交换，然后把剩下的$n-2$个数错排，获得$n-1$个合法序列。 综上，错排问题的递推式为： $$f(n)=(n-1)\cdot(f(n-1)+f(n-2))$$ $$f(1)=0,f(2)=1.$$ ## 第二类斯特林数 将$n$个有区别的小球放到$m$个相同的盒子中，要求无一空盒，其方案数用$S_2(n,m)$表示。设这些小球用$b_i$表示，则有： 1. $b_n$单独放在一个盒子里，方案数为$S_2(n-1,m-1)$； 2. $b_n$与其他球放在一个盒子里，则可先把$b_1\sim b_{n-1}$放到$m$个盒子里，然后再把$b_n$放到其中的一个盒子中，方案数为$m\cdot S_2(n-1,m)$。 综上，$S_2(n,m)$的递推式为： $$S_2(n,m)=S_2(n-1,m-1)+m\cdot S_2(n-1,m)$$ $$S_2(n,1)=S_2(n,n)=1,S_2(n,k)=0(k>n).$$ ## 卡特兰数 $$C_n=\sum_{i=0}^n C_i\cdot C_{n-i}$$ $$C_n=\frac {C_{2n}^n}{n+1}=C_{2n}^n-C_{2n}^{n-1}.$$ ## IP 地址 |类型|开头|网络号码|主机号| |:-|:-|:-|:-|:-| |A|$0$|$1\sim8$|$9\sim31$| |B|$10$|$2\sim16$|$17\sim31$| |C|$110$|$3\sim24$|$25\sim31$| # 计算机常识 ## 伟人 冯·诺依曼是美籍匈牙利数学家，设计出了 EDVAC。 图灵是英国人，目前姚期智为唯一获得该奖的华人。 ## 计算器的历史 第一台电子计算机：**ENIAC** 第一台具有储存程序功能（冯·诺依曼机）的计算机：**EDVAC** ## 计算机的结构 CPU 中，地址总线（AB）是 **单向总线**（由 CPU 指向内储存器和 I/O 接口）；其余的数据总线（DB）、控制总线（CB）都是 **双向总线**。 ## 编程语言 Smalltalk、EIFFEL 都是纯面向对象的语言。 Haskell 是纯函数式编程语言。