《程序员的数学》阅读笔记
2022年01月02日
- 对于一个问题的分析要注意每种情况的排他性和全体的完整性，也就是不能遗漏也不能重复。
- 逻辑蕴含
（A => B）: 若（存在）A，则（判断）B。A为真，整个式子的值由B决定，A为假，整个式子为真。A => B 与 ￢A v B 等价。
- 逆否命题的真值等价与原命题。
- 摩根定律：
(￢A) v (￢B) = ￢(A ^ B)
- 余数问题一般存在周期。比如今天是周日，问第
10^2，10^3，10^4 … 10**n天是星期几。只要将天数对7取余数，就可得知，余数为3、2、6、4、5、1不断循环
- 奇偶校验：就是判断奇数和偶数的个数是否符合一点的比例，比如相等。奇偶校验可以用于解决，草席是否能铺满房间的问题，信息传输过程中的完整性校验。
- 一笔画问题：其实用到了‘图’的数据结构，有n个点用线段互相连接，一个点有几根线连着，‘度’就为几。一笔画问题，如果终点和起点相同，则每个点的度都应该为偶数；如果终点和起点不同，则除起点和终点之外，每个点的度都应该为偶数；
- 排列组合中，不区分某些元素，即是除以这些元素的全排列。排列组合应该以有独一性的作为基准。
- 斐波那契数列： 今天的总数 = 昨天的所有 + 今天生的 = 昨天的所有 + 前天的所有。 鹦鹉螺内壁、葵花种子的摆法、植物叶子的长法、爬楼梯问题都可简化为斐波那契数列。
- 摆砖头问题： 由于每个砖头没有区别，所以它在哪个位置没有影响。
- 组合问题：
n 取 k = (n-1) 取 (k-1) + (n-1) 取 (k)。即是组合中不包含新元素、组合中包含新元素两种情况。
- 发现递归结构的要领：
从n层中隐去部分问题。
- 判断剩余部分是否是n-1层的问题。
- 不可解问题是原则上不能用程序解决的问题。
