程序员的数学 - 读书笔记

落日映苍穹つ 2022-06-03 03:58 190阅读 0赞

# 第一章 #

## 一、10进制记数法 ##

1，这里的`10 ^ n` 中的`10`，叫作`基数`或`底`。

![这里写图片描述][SouthEast]

2进制计算如下：  
![这里写图片描述][SouthEast 1]

2，与其把 10 ^ 0 值记作 0，还不如把它记作每个数的10分之一，所以 10 ^ 0 就是 10 ^ 1 的 10分之1，也就是`1`。  
![这里写图片描述][SouthEast 2]

> 注意：在这里想强调的是，不要将 2 ^ 0 的值作为一种知识去记忆，我们更需要考虑的的，如何对 2 ^ 0 进行适当的定义，让规则变得更简单。这不是记忆力的问题，而是想象力的问题。请记住这种思维方式：以简化规则为目标定义值。

## 二、0的作用 ##

**0的作用是：`统一标准，简化规则`。为什么这么说呢？**  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]

## 三、人类为什么要发明计数法呢？ ##

![这里写图片描述][SouthEast 5]

# 第五章 #

## 1，加法法则 ##

![这里写图片描述][SouthEast 6]

## 2，乘法法则 ##

![这里写图片描述][SouthEast 7]

![这里写图片描述][SouthEast 8]

## 3，置换 ##

![这里写图片描述][SouthEast 9]

## 4，排列 ##

![这里写图片描述][SouthEast 10]

## 5，组合 ##

![这里写图片描述][SouthEast 11]  
![这里写图片描述][SouthEast 12]

## 6，总结： ##

### 乘法 ###

是将两个集合的元素组合起来。  
扑克牌有4种花色，每种花色又分别有13张。遇到这种“分别有”的情况时，往往只需要乘法计算，便可以求出结果。

### 置换 ###

什么是转换？  
**有N个符号，按照“不同的顺序”排序，有多少种排法。**一般置换的个数为 N! 。  
置换和乘法是有关系的，例如：3张牌进行排列的话：

*  选第一张牌时，有3种选法
 *  选第二张牌时，因为少了一张，只有2种选法
 *  选第三张牌时，因为只剩下了一张牌，所以只有一种选法。

这种方式，可以利用股子的想法，看成：第一张牌有3种情况，第二张牌有2种情况，第三张牌有1种情况。这样，就可以用乘法规则：3 x 2 x 1 来解决置换问题了。

乘法例子中，扑克的例子和骰子的例子感觉有点不一样。其实不一样的点是，骰子例子中，每个骰子的集合内容是一样的，所以在2个骰子时，形成的数字从排列上看是没有重复的（不存在2个16这样的排列），但从数字相加的结果上来看，是有重复的（例如：16和61的最终相加都是7），所以容易和置换等形式搞蒙。这样，我们只要关注排列后的内容就可以了，不要关注数字相加的结果。

而扑克例子中，花色集合和牌集合的内容是不一样的，所以不存在最后排列内容相加，这种想法。

还有一点，为什么乘法是NxN，排列是3x2x1，因为排列里，拿走一种情况后，就少一个，乘法例子里没有少一个这种情况

### 排列 ###

什么是排列？  
**从N个符号里，选出K个，按“不同顺序”排序，看有多少种排法。**排列和置换不同的是，置换是“把N个数都拿出来进行排列”，而排列是“不是把 N 个数都拿出来排序，而是从 N 个数中取 K 个拿出来进行排序”。

### 组合 ###

和排列很像，只是不考虑排列顺序，只要元素相同，就算为一组

排列和组合的关系如下图所示：  
![这里写图片描述][SouthEast 13]

“5张牌中取3张的排列”的排列就是，先算出“5张牌中取3张的组合”（就是左边第一列），然后对于每一种组合，算出每种组合的排列（每一行的第二元素到最后一个元素，都是第一个元素的排列形式）。

变一种形式，当你已经有了“5张牌中取3张的排列”的排列数，想求出组合数的话，就要用总的排列数，除以“3张牌中取3张的排列”数，而不只是 3。即 C3,5 = P3,5/P3,3

### 思考题 ###

#### 药品调剂 ####

这个题的意义在于，如何把生活的中问题，转换成“排列组合”问题。  
转换问题的关键点在于，使用隔板方式，把药品分组转换成隔板旋转位置问题，这样隔板就可以使用排列组合方式解决问题。因为隔板没有顺序之分，即哪个隔板在前哪个在后，所以使用组合来解决问题。因为隔板只能放在药片中间，所以只能有99个位置。因为药品要分成3份，所以隔板的个数只能有2个。最后，就是求 C2,99 的解。

## 7，问题 ##

### （1） ###

![这里写图片描述][SouthEast 14]

### （2） ###

![这里写图片描述][SouthEast 15]

# 第六章 #

## 递归 ##

为了找出复杂结构中的递归结构，我们一般这样做：

*  从N层问题中隐去部分问题
 *  判断剩余部分是否是 N - 1 层的问题

即：

*  从整体部分中隐去部分问题
 *  判断部分问题是否和整体问题是同类问题

我理解的意思是，先把原来问题中的一部分先不看，看剩下那部分能不能转成同类问题（即：N-1的问题和 N 问题是类似结构）。然后再看隐去那部分，能不能再转成同类问题。

例如：  
![这里写图片描述][SouthEast 16]

上面的问题，分成“包含A”的部分，和“不包含A”的部分。

[SouthEast]: /images/20220603/5a7e73d564ce4c74a3c2bcf05aae4383.png
[SouthEast 1]: /images/20220603/a84091209abc40e99335923222bc4dae.png
[SouthEast 2]: /images/20220603/6d4ddfa1c2e0486d9d086b7c6290b7ff.png
[SouthEast 3]: /images/20220603/1035cb0d788c430e90187ef8a4f72929.png
[SouthEast 4]: /images/20220603/f6dd66a4a477496b8d9e072448c01648.png
[SouthEast 5]: /images/20220603/48b6e2ac0adc4f09a1bb1db32a57c83a.png
[SouthEast 6]: /images/20220603/0126acb51ebe41a9abe915124ff5b7ba.png
[SouthEast 7]: /images/20220603/3259264831bd4080828035ef6f893b77.png
[SouthEast 8]: /images/20220603/161609c3e1da43fb96e6fe0a00bb12cb.png
[SouthEast 9]: /images/20220603/fbae1c036fec452389740817b5900e50.png
[SouthEast 10]: /images/20220603/70c50febf88c4c38a335535cefd7545e.png
[SouthEast 11]: /images/20220603/103c6c0326864b63b221825391a70f76.png
[SouthEast 12]: /images/20220603/094a4fb0d70146899aced6dc40cc7a8c.png
[SouthEast 13]: /images/20220603/3306d5b637624ba1a4336d5bf6cb9f8f.png
[SouthEast 14]: /images/20220603/72f892df810241a3879c8495def99957.png
[SouthEast 15]: /images/20220603/14b3b17b696b47b399f8e82941092399.png
[SouthEast 16]: /images/20220603/288ff4459b0f4fb39cd2c2438c854d94.png