0 的故事——无即是有

在 10 进制计数法中，位数少，但是数字的种类多。 → 对人类来说，这种比较易用

在 2 进制计数法中，数字的种类少，但是位数多。 → 对计算机来说，这种比较易用

0 给计数法带来的好处是：统一标准，简化规则。

不要将 $n^0$ 的值作为一种知识去记忆，更值得去考虑的是，如何对 $n^0$ 进行合适的定义，以期让规则变得简单。这不是记忆里的问题，而是想象力的问题。请记住这种思维方式：以简化规则为目标去定义值。

计数法出现的本质是：数越大越难处理。 比如罗马人不把数字 V 写作 IIIII；再向后人们处理的数字又变大了，人们使用按位计数法的罗马数字；到了今天，人们处理的数字更庞大了，便使用指数表示法。 这里面我们可以获得一个启发：将大问题分解为小的“单元”。

逻辑——真与假的二元世界

为何逻辑如此重要？ 逻辑是消除歧义的工具。 人们平时使用的语言——自然语言，是极易产生歧义的。而逻辑是消除自然语言的歧义、严密精准地记述事物的工具。

程序员处于人类和计算机的分界线上。只要做到逻辑性的思考和表达，就不会为常识和感情所困，从而写出符合要求的规格说明和程序。

命题 ，能够判断对错的陈述句叫命题。一个完成的命题应该没有“遗漏”和“重复”，即具有 完备性 和 排他性 。由此，为了确认一句话是否是命题，需要特别注意 边界值 。

有很多工具可以帮助完成逻辑：数轴、真值表、文氏图。

复合型逻辑表达式：

1. $\lnot A$
2. $A \land B$
3. $A \lor B$
4. $A \oplus B$
5. $A = B$
6. $A \Rightarrow B$

得·摩根定律：

“非A” 或者 “非B”，和，非“A与B”，是等价的 “非A” 并且 “非B”，和，非“A或B”，是等价的

对偶性：

在逻辑表达式中分别将 true 和 false、 $A$ 和 $\lnot A$ 、 $\land$ 和 $\lor$ 进行互换，就能够得到该逻辑表达式的否定式。 （注意是 否定式 而不是 否定，即转换前后的逻辑表达式是等价的）

卡诺图（Karnaugh Map）

将所有命题的真假组合以二维表的形式表示的图

其意义是可以将复杂的逻辑简单化

二灯游戏、三灯游戏。

Tips:

1. 尽可能使打勾的区域在一起；
2. 当条件过多时，如果有分离部分，可以多次使用卡诺图；

三值逻辑

true, false, undefined

余数——周期性和分组

余数可以分组，解决周期性问题。

奇偶数，兼具整数中的完备性与排他性，奇偶校验也因此可以用作通信校验

例子：

1. 星期数
2. 星期数（指数版）
3. 大数乘方后的个位数
4. 通过黑白棋通信（奇偶校验）
5. 寻找恋人
6. 房间里铺满草席
7. 哥尼斯堡七桥问题（图）

图中的基本概念：

• 顶点
• 边
• 度数

一笔画问题： 如果能一笔画成，必须满足所有顶点都是偶点或者只有两个奇点。

欧拉的论断重点在于：不反复试验也能证明不能一笔画成。不用频繁地试走各种路径，只要观察各顶点的度数就行了。

另外，欧拉的证明中蕴含着很重要的思维方法。那就是在观察各个顶点的度数时，着眼点不在“数的本身”，而是“数的奇偶性”。并不1条、3条、5条、这样分散地思考路径，而是概括为“奇数条”来整体考虑。在一笔画的问题中，这个“奇偶性”是解题的关键。这又是奇偶校验的一个例子。

感想：这是计算机难以超越人的地方

数学归纳法——如何征服无穷数列

多米诺骨牌就是数学归纳法的类比的绝佳例子之一

1. 把多米诺骨牌排列成其中第一个倒下就能顺次带倒下一个的样子；
2. 推倒第一个；

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

？？？什么是断言？断言和命题有啥区别？假设某命题为真？

使用数学归纳法来证明“断言 $P(n)$ 对于 0 以上的所有整数 $n$ 都成立”

归纳法的两个步骤：

步骤1: 证明“$P(0)$ 成立”。

步骤2: 证明不论 $k$ 为 0 以上的哪个整数，“若 $P(k)$ 成立，则 $P(k+1)$ 也成立”。

步骤1 被称为 基底(base) 步骤2 被称为 归纳(induction)

数学归纳法并不像“推到多米诺骨牌”那样关注所用的时间。

数学归纳法和编程不同，往往使用的是忽略时间的方法。这就是数学和编程之间最大的差异

步骤2 的主要证明过程是：先假设 $P(k)$ 成立，然后证明 $P(k+1)$ 成立。

其中的技巧是使用 $P(k)$ 的公式去替换 $P(k+1)$ 中相同的那部分。

⚠️注意：要证明的是 $P(n)$ 成立，假设的是 $P(k)$ 成立。这里的 $n$ 和 $k$ 是不同的两个东西。

循环不变式

编写循环时，找到让每次循环都成立的逻辑表达式很重要。这种逻辑表达式称为 循环不变式(loop invariant) 。循环不变式相当于用数学归纳法证明的“断言”。

循环不变式可用于验证程序的正确性。在编写循环时，思考一下“这个循环的循环不变式是什么”就能减少错误。

例子：sum函数

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

循环不变式确保了“达到目的”，而计数器的递增确保了“适时结束循环”。

排列组合——解决计数问题的方法

准确无误地计数的关键是：不遗漏、不重复地去计数

"计数对象的本质"是找到"将计数对象与整数对应"

将集合 $A$ 的元素个数写作 $|A|$

容斥原理

A～K 13张扑克牌，抽出一张，如果是 2 的倍数或者3的倍数亮灯，其他情况不亮灯，问亮灯的情况有多少种。

乘法法则

假设 $A \cap B = \emptyset$

扑克牌有 A～K 13个等级，♥️♠️♦️♣️ 4个花色，问可以组合出多少张不重复的卡牌。

置换（Substitution）

将 $n$ 个事物按顺序进行排列 称为 置换

例如 3 张卡片 A、B、C ，问它们的置换总数是多少。

阶乘（Factorial）

将递减的正整数相乘的运算被称为阶乘。特别规定 $0! = 1$ 因为其是“第一块多米诺骨牌”

因为其乘数呈阶梯状而得名。

$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \\ 4! = 4 \times 3 \times 2 \times 1 = 24 \\ 3! = 3 \times 2 \times 1 = 6 \\ 2! = 2 \times 1 = 2 \\ 1! = 1 = 1 \\ 0! = 1$

排列（Permutation）

证明方式：类推法

结论：第 $k$ 张的取法，有 $n-k+1$ 种

书写格式：

$^nP_k = P_n^k = P(n, k)$

计算式推导：

$^nP_k = n \times (n-1) \times (n-2) \times ... \times (n-k+1) \\ ^nP_k = \frac{ n \times (n-1) \times (n-2) \times ... \times (n-k+1) \times (n-k) \times ... \times 1 }{ (n - k) \times ... \times 1 } \\ ^nP_k = \frac{n!}{(n - k)!}$

组合（Combination）

证明思路：考虑顺序得出排列数，随后去重，得出组合数

书写格式：

$^nC_k = C_n^k = C(n, k) = \binom{n}{k}$

计算式推导：

$^nC_k = \frac{考虑顺序排列的数量}{重复度} \\ ^nC_k = \frac{n\ 数量中取出\ k\ 数量的排列总数}{k\ 数量的置换总数} \\ ^nC_k = \frac{^nP_k}{^kP_k} \\ ^nC_k = \frac{\frac{n!}{(n - k)!}}{k!} \\ ^nC_k = \frac{n!}{(n - k)!k!} \\ ^nC_k = \frac{n!}{(n - k)!k!} \\ ^nC_k = \frac{n!}{(n - k)!k!}$

一些公式

$^nC_k = ^nC_{(n-k)}$

递归——自己定义自己

GUN is Not UNIX

一些例子：

• 汉诺塔
• 阶乘的递归定义
• 不断繁殖的动物（斐波那契数列）
• 帕斯卡三角形
• 画一棵树
• 谢尔平斯基三角形

编程中：

• 源代码缩紧
• 树形数据结构
• XML语法
• 快速排序

事实上递归是数学归纳发的一种延伸，在具体编程中的一种实现

无论是数学归纳，还是递归，对于两者最重要的是找出 递推公式

递归本身也是一种分治思想的体现，将复杂思考简化

指数爆炸——如何解决复杂问题

指数爆炸会有哪些问题

由于指数爆炸

要一个不漏地测试设定选项的所有可能性是不现实的

在软件开发中不进行“一个不漏”的全覆盖测试，而是只挑选出可能对功能有影响的选项进行测试。 如何选出要测试的设定选项是很重要的。

选多了，非但测试没有意义，而且测试量也将呈指数式增长

“有限的”不代表可以不假思索（国际象棋棋盘放米粒）

有倍数游戏的地方，就有指数爆炸。一旦发生指数爆炸，就完全不能像预想的那样“通过几步就解决”了。因此在解题前，要先判断其中是否隐含着倍数游戏

如何利用指数爆炸

二分搜索：

利用指数爆炸排除不合条件的

对数——掌握指数爆炸的工具

对数与乘方是互逆关系，如果感到对数怪怪的，那么就把把乘方逆向思考试试

附录：递推公式求解析式

两个大方法：累加法、累乘法

注意点是总共多少个式子累加或者累乘

累加法

$f(x) - f(x-1) = g(x)$

$f(x-1) - f(x-2) = g(x-1)$

$...$

$f(2) - f(1) = g(2)$

$f(1) - f(0) = g(1)$

共 $n$ 项，左右分别相加可得

$f(x) - f(0) = \sum_{k=1}^{n} g(x)$

累乘法

与累加法同理，左右变为了累乘而不是累加

若共 $n$ 项式子，左右分别相乘可得

$\frac{f(x)}{f(0)} = \prod_{k=1}^{n} g(x)$

特殊情况

递推公式中 $f(x)$ 与 $f(x-1)$ 的系数不一致

一般来说解出下式与原式对比即可

$f(x)+X = A(f(x)+X) + B$

附录：专业术语一览表