《程序员的数学》笔记

0

• 10进制计数法的数位全都是10^n的形式，这个10称作10进制计数法的基数 2503 = 2*10^3 + 5*10^2 + 0*10^1 + 3*10^0

• 10进制转换为2进制

• 为何 2^0 = 1？记住这种思维方式，以简化规则为目标去定义值

• 0的作用:占位符、统一标准，简化规则

逻辑

• 逻辑是消除歧义的工具

• 文氏图，表达复杂命题

• 通过真值表，可以推导出德摩根定律

1. !A || !B = !(A && B)

2. !A && !B = !(A || B)

• 卡诺图： 简化复杂逻辑表达式的有效工具

1. 把问题转为逻辑表达式

2. 通过逻辑表达式的变形和卡诺图实现简化





余数

• 余数就是做除法运算时剩下的数

• 余数是一种给整数分组方法（分库分表）



数学归纳法

• 概念

1. 步骤1：证明F(0)成立

2. 证明不论k为0以上的哪个整数，“若F(k)成立，则F(k+1)也成立”

• 数学归纳法并不像“推到多米诺骨牌”那样由数据规模带来的时间复杂度。数学归纳法和编程不同，往往使用的是忽略时间的方法，这就是数学和编程之间最大的差异

排列组合

• 关键在于认清问题的性质，通过缩小规模找出问题的本质，再将其抽象化，就能得到答案

• 3类

1. 置换，排列数量 n!

2. 排列 n!/(n-k)!

3. 组合，排列数量/重复度： (n!/(n-k)!) / k!

递归

• 推导递推公式

1. F(0) = 0, (n=0时)

2. F(n-1) = (n-1)!

3. F(n) = n * F(n-1), (n=1,2,3…)

• 发现递归结构的要领

1. 从n层的整体问题中隐去部分问题

2. 判断剩余部分是否是n-1层的问题

指数爆炸

• 数值急速增长的情况

• 处理庞大的指数数据的工具：对数,Log 8 = 3，2的几次方是8

• 二分查找就是利用了指数爆炸来对大量数据信息，进行高速查找的算法。利用对数能将乘法运算转换为加法运算，从而让时间复杂度从指数级降低到对数级。

程序

• “程序”（源代码）本质上是计算机存储设备上的数据

• “编译器”compiler就是读取人类能读懂的程序（源代码），再将它转换为方便计算机运行的机器语言（目标代码）的程序。所以编译器是转换程序的程序

• “源代码检查器”它能读取程序源代码，然后告诉你有关程序的建议，例如哪里使用了不正确的指令

• “调试器”debugger 也是程序，他能暂停运行中的程序，也能重新运行程序，还能告诉你程序运行中的状态，你也可以通过它来查看和雕饰程序



何为解决问题

• 认清模式，进行抽象化

* 在解答思考题时，经常会使用“先用较小的数试算”的方法。用较小的数进行尝试，可以发现规律、性质、结构、循环、一致性等，认清隐含在问题中的模式。否则，即使解决了问题，也只是一知半解。

* “对目前得到的结果进行抽象化”，通过抽象化，可以将结论运用到当前问题以外的其他问题中。如果问题的解法只能够运用于当前问题，那么这个解法就名不副实。只有同样能够运用于其他类似问题的方法，才能称为解法。

• 幻想法则