《程序员的数学》第一册，读书笔记
前言
最近翻出了压箱底的程序员的数学第一册，里面的知识点都很基础，都是我们高中和本科学习的知识，但是书中理解的方法却很新奇。这挑选几个我印象比较深的记录一下。
程序员的数学1.png
脑图使用processon绘制，感兴趣可以去下载：https://www.processon.com/view/link/5ec9e0b11e08530a9b189b4d
0的故事
为什么计算机使用二进制
我们都知道计算机的底层是二进制表示的，就是0和1，那么为什么要选用二进制？因为这样表示对计算机比较“友好”，电路联通代表1，电路关闭代表0，两种状态就足以表示。如果强行设置10中状态可以吗？理论上是可行的，不过结构会非常复杂。
人们觉得 10 进制比2进制更容易处理，是因为 10 进制计数法的位数少，计算起来不
容易发生错误。此外，比起2进制，采用 10 进制能够简单地通过直觉判断出数值的大小。人的两手加起来共有 10 个指头，这也是 10 进制更容易理解的原因之一。
十进制加法表
二进制加法表
通过上图对比，可以很直观的感受2进制类型少，对于计算机的处理逻辑要友好很多，虽然相应计算的进制会变多，但是计算机的进制运算速度非常快，位数再多也没关系。
10的0次方是什么？
image.png
这个公式大家都知道，书本上是这么教的，但是10的2次方是 "2个10 相乘"，那么 10的0次方。不就是 "0个10 相乘"吗?这样的话，不应该是1而是0吧? 曾几何时我们好像也这么有过疑问，但是却从来没有更深一步的思考，这里书中给出了一个不错的理解方式。
首先，暂且抛却 "n个10 相乘"这样的想法。
image.png
指数没减1，数字变为原来的十分之一。同样可以将这个思想用在10的-1次方上面。
image.png
这和我高中时的理解方式完全不同，你们上学的时候是怎么教的呢？
逻辑
书中第二章是关于逻辑的，这里大部分都是概念的讲解，本章最后的一张图总结的很好。
image.png
在我们写程序的时候if else之类的判断逻辑很多，其实本质上都是本章讲解的思考内容。其中卡诺图推荐大家了解一下，未来遇到特别复杂的判断逻辑时这是一个很好的解决思想。
余数
周期性
这是一个利用周期性解答的例子。
image.png
首先这么大的数字，不管是手算还是用计算机都不可能得出结果。那么我们可以“简化”问题，首先能影响个位数的其实就是个位上的数字7，所以我们可以发现规律。
image.png
这里我们可以发现个位数字是1、7、9、3的循环，所以找到了“周期”是4。所以答案就是987654321 除以4余1 ，所以答案为 7。
运用余数，大数字问题就能简化成小数字的问题
奇偶性
有这样一个房间。使用图中右下角所示的草席能够正好铺满房间吗?
前提是不能使用半张草席。
image.png
这里有一个很好的方式，我们来看看有多少个“上半张”和“下半张”
涂上颜色
现在我们就来数一数分别有儿张黑色和白色的"半张草席"。
黑色的"半张草席”， 30张，白色的“半张草席”，32张。所以这里我们得出结论--不能铺满。
数学归纳法
这一章应该算是过去知识点的补充了，印象中好像是学过，但是肯定也是考试不考的内容了。
这里就记录一下书中描写的高斯求和的内容吧。
求 1+2+3+ …+ 100 的结果。以前你们是怎么教的，我记得我们当时教的是“首项加末项的和乘以项数除以二”。一直以来这类问题我都是在用这套公式，但是从来也没想过这是怎么来的。
我们来看看高斯小时候是怎么想的。
image.png
哇，当时看见这个图我真的觉得这么多年书白读了。以前还经常把公式记错，如果以前给我这个图让我理解的话，我怎么可能记错。
言归正常，我们用归纳法来证明一下高斯的公式。
高斯的断言
一，基底的证明
证明 G(O) 成立。
image.png
二，归纳的证明
证明当k为0 以上的任一整数时，"若 G(k) 成立，则叫G(k+ 1) 也成立"。
image.png
证明过程
证明完成。
排列组合
排列组合的公式我们都知道，本书却提出了几个我新见到的概念，重新解读了一下排列组合。
置换
如果将A,B,C三张牌按照 ABC ACB BAC......等顺序排列，那么共有多少种排法?
image.png
答案是6中，即3 * 2 * 1。
第1 张牌有3 种选法。第2张有2种，第三张有1种。
将n个事物按顺序进行排列称为置换 (substitution)。（其实就是全排列）
如果还是不能理解，可以通过下面这张树形图加深理解。
树形图表示法
排列
如果从5个中取3个呢？
第1张5中，第2张4种，第三张3种，所以答案就是 5 * 4 * 3。
用阶乘表示如下。感兴趣的可以用归纳法证明一下。
image.png
组合
上面都是考虑了顺序的情况，那么不考虑顺序呢？
比如从5张牌中取3张，不考虑顺序。
image.png
这里用了重复度的概念，反正我以前就是单纯的背公式，这种理解方式我印象中是第一次见。关于置换，排列，与组合的应用可以去书中阅读后面的分析。
指数爆炸
著名的折纸问题，如果一张纸能无限对折，那么39次，就可以从地球到月球了。因此现实生活中相似的情况，我们要清楚，不能认为“有限的”，就不假思索。那么利用指数爆炸的最实际的案例是什么呢？就是二分查找。判断 30 次就能在 21亿4748万3647 个数据中找到目标数据。这也是为什么二分查找重要的原因。
另一个应用就是密码学。
如果密钥的宇长只有3位，那么正确的密钥必是下列8种之一。
image.png
那么如果秘钥长度是512位的话，那么虽然理论上存在暴利破解的可能性，因为毕竟是“有限的”解，但是目前的计算机的能力是不可能在一个人的有生之年计算成功的。
最后
程序员通常不需要掌握很深奥的数学知识。不过，认清并简化问题结构，总结出具有一致性的规则等，对于程序员来说是家常便饭。结合自己的工作经历，读这本书确实发现了很多有趣的点，推荐给大家。全书大概200多页，用空闲时间一周左右就能读完。
欢迎大家支持正版，当然了，如果想“白嫖”的，可以在公众号后台给我留言。
