《程序员的数学1》笔记

第一章：0 的故事

计数法

计数法分为两类：

• 按位计数法：按位计数法表示的数字每一位权重不同，例如我们常用的二进制、八进制、十进制和十六进制计数法；
• 其他：比如罗马数字计数法，数位没有权重，罗马数字的值是所有数位值的和。

按位计数法更有效率，有限的数字能表示更大的数值。

指数法则

1

N**a * N**b = N**(a+b)

第二章：逻辑

常用逻辑

• 逻辑非 ¬；
• 逻辑与 ∩；
• 逻辑或 ∪；
• 逻辑异或 ⊕；
• 逻辑相等（同或）=；
• 逻辑蕴含 ⟹；

逻辑蕴含的真值表如下，即只要前提条件 A 为 false，则不论 B 的真假，“若 A 则 B”的值恒为 true。

逻辑的表达方式

逻辑的几种表达方式：

• 逻辑表达式；
• 真值表；
• 文氏图（韦恩图）；
• 卡诺图；

如何解决逻辑问题

1. 由复杂的规则（现实）生成逻辑表达式（抽象）；
2. 通过卡诺图、德·摩根定律等，简化逻辑表达式；
3. 将简化的逻辑表达式（抽象）还原为简单的规则（现实）；

未定义逻辑

三值逻辑包含 true、false 和 undefined。计算时采用优先运算原则。

逻辑与：

• A 为 true 时，看 B；
• A 为 false 时，恒为 false；
• A 为 undefined 时，恒为 undefined；

逻辑或：

• A 为 true 时，恒为 true；
• A 为 false 时，看 B；
• A 为 undefined 时，恒为 undefined；

逻辑非：

• 值为 undefined 时，逻辑非也为 undefined；

第三章：余数

余数的作用

余数可以用来解决周期性和奇偶性的问题。

主要作用：

• 利用周期性和奇偶性简化计算，例如 10**N 天后星期数具有 1-3-2-6-4-5 循环的规律。
• 用于奇偶校验；

草席问题

在一个 8x8 的房间中，缺失左上角和右下角，问使用 1x2 的草席能够把房间铺满吗？

将整个房间看做一个棋盘，间隔涂上黑白两色，一张 1x2 的草席可以认为是由一个黑色块和一个白色块组成。 计算得到，黑色块和白色块数量并不相等，因此 1x2 的草席不能够将房间铺满。

注意，反过来讲，假设黑色块和白色块数量相等，也不一定能够铺满整个房间。

柯尼斯堡七桥问题

问题详情见维基，类似的还有一笔画问题等。

使用图论，能够不重复走完全程（能够一笔画完）的条件为：

• 要么起点和终点相同，此时要求所有节点都是偶点；
• 要么起点和终点不同，此时要求有且只有两个奇点，其他都为偶点。

柯尼斯堡七桥问题中，共有 4 个顶点，度数分别为 3、5、3、3，不满足以上的条件，在给定条件下不能走完全程。

第四章 数学归纳法

数学归纳法用于证明 “对于 0 以上的所有整数 n 都成立的断言”。

证明数学归纳法

数学归纳法证明的步骤：

1. 证明 p(0) 成立；
2. 证明无论 k 为 0 以上的任何整数，若 p(k) 成立，则 p(k+1) 成立。

循环不变式

在编写循环时，每次循环时都成立的逻辑表达式称为循环不变式。

编写循环时，有两个注意点：“达到目的” 和 “适时结束循环”。

第五章：排列组合

处理排列组合问题时，要注意 “遗漏” 和 “重复”。

排列和组合的区别是，排列需要考虑顺序，组合不考虑顺序。

排列组合的几个法则

• 加法法则：当两个集合中没有重复元素的时候，适用加法法则 |A∪B| = |A| + |B|；
• 容斥原理：|A∪B| = |A| + |B| - |A∩B|；
• 乘法法则：当两个集合的维度性质不同时，适用乘法法则 |AxB| = |A| x |B|；

排列

• 置换：集合中（n 个元素）所有元素进行排列，公式为 n!；
• 排列：从 n 个元素中取 m 个元素进行排列，公式为 P(n, m)；

可以看出，置换是 m = n 时排列的特殊情况。

可以通过树形图进行辅助排列。

组合

从 n 个元素中取 m 个元素进行组合，公式 C(n, m)。

排列与组合的关系

M 的置换 x N 取 M 的组合 = N 取 M 的排列

重复组合问题

有 A、B 和 C 三种药品，共取 100 粒，可重复，每种至少 1 粒，共有多少种组合？

组合很明显不考虑顺序，可以认为是在 100 个盘子中间插入 2 个隔板，将盘子分为 A、B 和 C 共 3 组， 所以共有 C(99, 2) 种组合。

排列有重复时可以先正常求解，最后除以重复度。也要善于使用逻辑进行求解。

第六章：递归

求解递归问题的方法：

• 找出递归结构；
• 建立递推公式；

斐波那契数列

一些问题可以使用斐波那契数列解决，注意初始值的取值。

摆砖头

将 1x2 的砖头摆放成纵长为 2，横长为 n 的长方形阵列，请问摆法有多少种。

分为两种情况：

• 左边竖立放置 1 块砖头时，右边砖头 n-1 块摆成 n-1 的长度；
• 左边横叠放置 2 块砖头时，右边砖头 n-2 块摆成 n-2 的长度；

即 F(n) = F(n-1) + F(n-2)

其他类似问题

使用 4 分音符和 2 分音符创作旋律，在 4分音符打 n 拍的时间内，可以创作出多少种旋律。

一次走 1 阶或 2 阶台阶，爬 n 层台阶共有多少种方法。

杨辉三角

杨辉三角又称帕斯卡三角，该三角形的第 n 行第 m 个元素的值即是 C(n, m) 的值（从 0 开始）。

另外从杨辉三角可以得出：

1

C(n, k) = C(n-1, k-1) + C(n-1, k)

可以从两种角度看：

• 从起点到终点的线路数量；
• 根据杨辉三角定义得出；

递归图形

分形图，谢尔平斯基三角形（用颜色区分杨辉三角形中的奇数和偶数即可得到）。

如何寻找递归结构

1. 从整体问题中隐去部分问题；
2. 判断剩余部分是否和整体问题是同一类问题；

第七章：指数爆炸

指数增长是迅猛的，二分法是利用了指数爆炸的一种有效查找方法。

对数

对数图表：帮助把握指数爆炸发生时的增长情况；

通过对数用加法实现乘法：

1

log(a*b, 10) = log(a, 10) + log(b, 10)

计算尺：使用对数进行乘法运算的工具。

• 等间距计算尺：指数相加；
• 非等间距计算尺：直接相乘。

密码

利用指数爆炸原理保护密码，使密码不能在现实时间内被暴力破解。

如何求解指数爆炸问题

• 极力求解：通过增强计算机性能，通过暴力方式求解；
• 变相求解：转换为简单问题，如柯尼斯堡七桥问题中，不需要列举出所有的线路，转而通过图论求解；
• 近似求解
• 概率求解

第八章：不可解问题

反证法

又称归谬法，分为两步：

1. 首先假设命题的否定形式成立；
2. 根据假设进行论证，推导出矛盾的结果；

注意，第二步中论证过程本身必须正确。

可数

“集合的元素是有限的，或者集合中的所有元素都与正整数一一对应” 时，这个集合就被定义为可数。 称为 countable 或 enumerable。

集合中所有元素都与正整数一一对应，即是元素可按一定规律既无遗漏也无重复地数出来。

可数集合举例

• 有限集合（满足集合中元素是有限的）；
• 0 以上的所有偶数的集合（满足一一对应）；
• 所有整数的集合（正负数交替编号，满足一一对应）；
• 所有有理数的集合（满足一一对应）；
• 程序的集合是可数的（编写程序的字符是有限的，其生成的排列组合有限）；

所有有理数的集合是可数的，是因为所有有理数都可以写成分数的形式，可以按照一定规律用正整数给它们编号。

不可数集合举例

• 所有实数的集合；
• 所有整数数列的集合；
• 所有函数的集合；

对角论证法

采用反证法论证“所有整数数列的集合是不可数的”。

1. 假设所有整数数列集合是可数的；
2. 列一张表列出所有整数数列，该表为二维整数表；
3. 取二维表左上角至右下角的对角线元素，组成新数列；
4. 新数列不在表中，与表为所有整数数列的集合相矛盾；

第 3 步中取对角线元素来证明命题的方法，称为对角论证法。

不可解问题

不可解问题即是原则上不能用程序来解决的问题，也即是不包含在 “程序可解决问题” 集合中的问题。

不能写成程序的函数是存在的。

停机问题

停机问题：判断某程序在给定数据下，是否会在有限时间内结束运行。

停机问题无解，可以通过反证法证明。