NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【考试】初赛复习

posted on 2019-10-18 13:30:14 | under 考试 |

数学问题

除法取模快速计算

$$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 是纯函数式编程语言。