数学问题

除法取模快速计算

$$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 地址

计算机常识

伟人

冯·诺依曼是美籍匈牙利数学家，设计出了 EDVAC。

图灵是英国人，目前姚期智为唯一获得该奖的华人。

计算器的历史

第一台电子计算机：ENIAC

第一台具有储存程序功能（冯·诺依曼机）的计算机：EDVAC

计算机的结构

CPU 中，地址总线（AB）是 单向总线（由 CPU 指向内储存器和 I/O 接口）；其余的数据总线（DB）、控制总线（CB）都是 双向总线。

编程语言

Smalltalk、EIFFEL 都是纯面向对象的语言。

Haskell 是纯函数式编程语言。