《程序员的数学1》笔记

第一章:0 的故事

计数法

计数法分为两类:

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

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

指数法则

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

第二章:逻辑

常用逻辑

  • 逻辑非 ¬
  • 逻辑与
  • 逻辑或
  • 逻辑异或
  • 逻辑相等(同或)=
  • 逻辑蕴含

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

A B A ⟹ B
true true true
true false false
false true true
false false 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 步中取对角线元素来证明命题的方法,称为对角论证法。

不可解问题

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

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

停机问题

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

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

觉得有用可以请作者喝杯咖啡呀~
0%