《程序员的数学》读书笔记

编程的基础是计算机科学,而计算机科学的基础是数学。因此,学习数学有助于巩固编程的基础,写出健壮的程序。

第1章 0的故事

——无即是有

10进制计数法

10称为10进制计数法的基数或者底,基数10右上角的数字是指数(有规律的顺次排列)。

2进制计数法

计算机在表示数的时候,会使用两种状态:

  • 开关切断状态 … 0
  • 开关连通状态 … 1

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

计算机在执行人类发出的任务时,会进行10进制和2进制间的转换。计算机先将10进制转换为2进制,用2进制进行计算,再将所得的2进制计算结果转换为10进制。

按位计数法

2进制、8进制、10进制、16进制计数法等
不使用按位计数法的是罗马数字(罗马计数法,钟表表盘)

指数法则

10的0次方:指数每减1,数字就变为原来的10分之1。

0的作用:1.占位;2.统一标准、简化规则

第二章 逻辑

——真与假的二元世界

命题及其真假

能够判断对错的陈述句叫做命题。命题正确时,称该命题为“真”(true)。反之,命题不正确时,称该命题为“假”(false)。命题要么为true要么为false。

完整性和排他性

逻辑从根本上说是对完整性和排他性的组合表达。

  • 有没有“遗漏”:不管针对哪个条件,都能判定命题真假。(大于6岁,不到6岁:没有6岁)
  • 有没有“重复”:确认规则对于某个条件是否有两种标准。(6岁以上,6岁以下:都包含6岁)
  • 没有“遗漏”,即具备完整性,由此明确该规则无论在什么情况下都能适用;
  • 没有“重复”,即具备排他性,由此明确该规则不存在矛盾之处。

解决方法:

  • 画一根数轴辅助思考(注意边界值)
  • 使用if语句分解问题(兼具完整性和排他性的分解)
  • 真值表
  • 文氏图

复杂命题

  1. 逻辑非——不是A
  2. 逻辑与——A并且B
  3. 逻辑或——A或者B
  4. 异或——A或者B(但不都满足)
  5. 相等——A和B相等
  6. 蕴涵——若A则B

德.摩根定律

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

卡诺图

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

第三章 余数

——周期性和分组

  • 余数就是作除法运算时的剩下的数。
  • 余数就是分组:将较大的数字除一次就能分组(星期等循环规律)
  • 运用余数,大数字的问题就能简化成小数字的问题。(乘方问题)
  • 思考问题:黑白棋通信、奇偶校验、寻找恋人、铺设草席、一笔画(哥尼斯堡七桥)

一笔画问题

  • 将地图简化,用“图”表示(顶点和边)。
  • 一笔画需要满足:所有顶点都是偶点,或者有2个奇点(奇偶校验)

第四章 数学归纳法

——如何征服无穷数列

高斯求和

1+2+3+…+100 = 100*(100+1)/2
0+1+2+3+…+n = n(n+1)/2

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

数学归纳法是证明有关整数的断言对于0以上的所有整数(0、1、2、3……)是否成立时所用的方法。

“断言P(n)对于0以上的所有整数n都成立”,数学归纳法的两个步骤:

  1. 证明“P(0)成立”(称作基底)
  2. 证明不论k为0以上的哪个整数,“若P(k)成立,则P(k+1)也成立”(称作归纳)

第五章 排列组合

——解决计数问题的方法

计数与整数

对应关系:只要与整数正确对应,计数的结果就是正确的。(注意遗漏和重复)
植树问题:不要忘记0,最后的编号(第k个数据是k-1号)

加法法则

  • 加法法则就是将无“重复”元素的两个集合A、B相加,得到AUB的元素数=A的元素数+B的元素数
  • 加法法则只在集合中没有重复元素的条件下成立。
  • 容斥原理:考虑了重复元素的加法法则

乘法法则

集合进行“元素配对”的法则

置换

n个事物的所有排法。
将n个事物按顺序进行排列称为置换。(阶乘:乘数呈阶梯状递减)

排列

从n个事物中取出一部分进行“排列”。

组合

置换和排列都需要考虑顺序,组合不考虑顺序。

第六章 递归

——自己定义自己

汉诺塔

  • [使用递归来表示]找出借助“n-1层汉诺塔”来解“n层汉诺塔”的步骤。
  • [递推公式]使用“n-1层汉诺塔”的移动次数来表示“n层汉诺塔”的移动次数。
  • 重要的一环:找出递推结构并建立递推公式。

斐波那契数列

八宝粥 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!