本文整理自《计算机科学精粹》一书的第一章：预备知识。主要阐述计算机科学通用的学前知识，而且要尽量精简并适用于日常使用场景。

整理想法

计算机科学的学习离不开实际的编程工作，而编程工作本质就是把程序员脑中的想法转化为可运行的代码。而编程第一步就是要整理脑中凌乱的想法，找出解决问题的思路，具体操作步骤如下所示。

流程草图

这一步的工作并不复杂，只要画出简单的流程图即可，目的是将解决办法划分大体的阶段，故而流程图大体类似“冷冻大象”的 3 步流程。这个阶段要绘制的流程图没必要特别严谨，以理清思路为宜。

数学建模

这一步的工作目标是：

• 提取问题中的数学关系
• 将各种实际条件细化为数字相关的逻辑判断、不等式

另外，要注意本阶段的操作要对上一个阶段的进行返工和修饰，使得流程图尽量严谨，在编码时有真正的参考价值。

编写伪代码

伪代码是细化流程图的进一步抽象，引入常见编程语言（通常为 Algol 系语言）的流程控制结构，并考虑使用何种 ADT，但无需关心数据具体的数据结构和储存类型。甚至，这个阶段的每一条伪代码在实际的编码过程中都可能展开为函数。

注意：即使已经确定实际要使用何种编程语言来解决当前问题，也不要纠结具体语言的实现细节，更不要考虑任何优化手段。不要有任何一步到位的想法！

理清逻辑

实际的编程工作中并不会常常碰到复杂的数学问题，甚至很少会使用复杂的算法，但是常常碰到逻辑纠缠不清的业务，其实绝大部分的编程工作更需要秉持清晰的逻辑而非掌握精深的数学知识。

使用布尔代数工具

常见的业务要求可以逐句“翻译”为布尔代数表达式，但是这样得到的表达式往往特别复杂，甚至常有重复判断的情况。如果程序判断中大量使用复杂且低效的布尔表达式，不仅运行效率极低，而且会极大增加编写和维护的难度，故而最好运用运算定律来化简。 布尔代数运算律有：

• 交换律

  1 2	A AND (B AND C) = (A AND B) AND C A OR (B OR C) = (A OR B) OR C

• 分配律

  1 2	A AND (B OR C) = (A AND B) OR (A AND C) A OR (B AND C) = (A OR B) OR (A OR C)

• 德摩根定律

  1 2	!(A AND B) = !A OR !B !A AND !B = !(A OR B)

另外，必须注意表示推出关系的 A -> B 成立并不代表 B -> A 也成立，只能确定 !B -> !A 必定成立。

画真值表

如果遇到业务问题极端复杂，逻辑模型难以确定，那么最好的办法就是使用“暴力”解法 —— 画真值表。 画真值表的通用步骤如下：

1. 每个变量可能的取值为一列，不同变量组成的实际状态为一行
2. 变量由少到多增加，从 1 个开始绘制表格，只需要两行数据分别为 True 和 False
3. 每增加一个变量时，先增加一列，但对应的值全部为空
4. 复制原有的各行数据，紧贴原有表格
5. 把新增列的数据上半部分填充 True，下半部分填充 False
6. 不断重复 3~5 的步骤，直到所有逻辑变量使用完毕，表格也就制作完毕了

注意：不难看出，真值表的行数和逻辑变量数量息息相关，n 个变量（n >= 1）的真值表要有 2^n 行数据，所以尽量只对少量逻辑变量绘制真值表。

个别情况下，可能仅仅需要不同的变量取几个固定的值即可，那么完全可以从真值表中抽取相应的行数据转换为二进制数，使用位运算来加速判断。当然，一定要加上详细的注释。

离散数学

编程过程中使用离散数学主要是为了计数，如：输出可能的运行步骤、待计算的数据量等。大部分时候并不设计太复杂的公式，甚至只需要高中的初级离散数学知识就可以了，常用的知识点有：

• n 个不同元素的全排列：n!
• n 个元素中有 m 个（m <= n）相同元素（其他各不相同）的全排列：n! / m!
• n 个不同元素挑出 m 个（m <= n）的方案数：n! / [m! * (n- m)!]

概率论

概率论常常用来预估程序运行情况，调整编程和优化方案等。同样不需要记忆太复杂的公式，主要要记住：

• 独立事件组合后的总概率为各个事件概率的乘积
• 互斥事件组合后的总概率为各个事件概率的和
• 两个对立事件的概率和为 1

**注意：

• 不要犯“赌徒谬误”，独立事件之间互补影响，即前 n-1 次骰子的结果不会影响第 n 次的结果
• 对立事件必须判断准确，例如：n 个互相独立的防空炮各自拦截空袭概率为 p1、p2 … pn，那么防空成功的概率为 1 - (1 - p1) * (1 - p2) * ... * (1 - pn)