程序员的数学-基础数学

发表于 2018-04-05 更新于 2024-09-08

买了本程序员的数学，记录一下笔记

前言

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

0 的故事

人类使用的是 10 进制，而计算机使用的是 2 进制(为什么使用二进制，这是一个比较有意思的事情)，一起思考 0 的作用，实际上 0 具有创建模式、简化并总结规则的重要作用

十进制计数法

十进制计数：
使用的数字右 0、1、2、3、4、 5、 6、 7、 8、 9 共计十种
数位有一定意义，从右向左分别表示个位、十位、百位、千位…

例如数字 2503 实际上可以使用下面的方法表示

$$2×1000+5×100+0×10+3$$

换成指数方法

$$2×10^3+5×10^2+0×10+3×1$$

二进制计数法

计算机在处理数据时候使用的是 2 进制计数法，从十进制计数法类推，可以比较快的掌握其中的规则

二进制计数法使用的数字只有 0、 1 两种
从右向左分别表示 1 位(0)、2 位(10)、4 位(100)、8 位(1000)

使用二进制计数法数数首先是 0，然后是 1，接下来不是 2，是 10，然后是 11，然后是 100,101

分解二进制 1100
和 10 进制计数法一样，并排的数字，各个数位都有不同的意义 1100 从左向右依次为：
1 表示 8 的位数
1 表示 4 的个数
0 表示 2 的个数
0 表示 1 的个数
也就是说二进制的 1100 表示如下意思

$$12^3+12^2+02^1+02^0$$

基数转换

接下来试着将 10 进制的 12 转换为 2 进制，这需要反复将 12 除以 2。
12/2 商为 6，6/2 商为 3…，并且换茬余数是 1 还是 0，余数 0 表示除完了随后再讲每步所得的余数列逆向排列，由此得到 2 进制

12/2 余 0
6/2 余 0
3/2 余 1
1/2 余 1

逆向组合就是 1100

计算机为什么使用 2 进制计数法

计算机采用二进制计数法的时候会采用以下两种状态：
开关切断状态
开关连通状态
ps 以前的计算机使用二极管，通电为 1 断电为 0，现代的机械磁盘也是正负极表示 1 和 0

因为计算机速度非常快，2 进制位数再多也没关系，而且计算机不会像人类一样计算错误，所以对于计算机而言，处理的数字种类少计算规则简单最好不过。

按位计数法

十进制二进制这种计数方法也称作按位计数法，除了 10 进制和 2 进制之外还有：
8 进制计数法：
使用数字有 0、 1、 2、 3、 4、 5、 6、 7、 8
从右向左表示 8 的 0 次方 8 的 1 次方 8 的 2 次方…

16 进制计数法
使用数字右 0、 1、 2、 3、 4、 5、 6、 7、 8、 9、 A、 B、 C、 D、 E、 F 十六种
从右向左表示 16 的 0 次方 16 的 1 次方

指数法则

在十进制说明中$$10^0 = 1$$

一般会想 10 的 0 次方不是 0 个 10 相乘应该等于 0 吗。

从目前掌握的知识来看看如何定义 10 的 0 次方比较妥当

$$10^3 = 1000, 10^2 = 100, 10^1 = 10, 10^0 = ?$$

从上述等式可以看出，数字的指数每减去 1，数字就变成原来的十分之一，因此 10 的 0 次方就是 1，在定义 10 的 n 次方的值时可以遵循一下规则

指数每减去一，数字就变成为原来的十分之一

10 的-1 次方是什么

使用上方的规则可以很明确的推导出一下等式

$$ 10^0 = 1, 10^{-1} = \frac{1}{10}, 10^{-2} = \frac{1}{100}$$

到这里给前面的规则取名为指数法则表达式为：

$$N^a*N^b = N^{a+b}$$

但是 N≠0

0 的作用

占位

例如使用 10 进制的 2503 中的 0 起到什么作用。2503 的 0 表示十位中没有数，没有但不能省略省略就变成了 253 称为另外一个数

所以在按位计数法中，位数具有很重要的意义，即使十位中的数没有，也不能不谢数字，这个时候就需要 0 出场，即 0 的作用就是占位，换而言之，0 占着一个位置以保证数位高于他的数字不会产生错位。

统一标准，简化规则

在按位计数中提到了 10 的 0 次方是 1，使用 0，能够将按位计数法中的各个数位对应的大小统一表示成
$$10^n$$
否则就必须单独处理 1 这个数字，0 在这里起到了标准化的作用。

人类的极限和构造的发现

时至今日十进制已融入生活，二漫长的文明中数学表示法有很长的历史：

古埃及人使用五进制和十进制混合的计数法，他们的计数不是按位计数所以不存在 0

巴比伦人在黏土板上使用记号表示计数，使用 1 和 10 两种菱形记号来表示 1 到 59，并通过记号位置来表示 60 的 n 次方的数位，一小时为 60 分钟的时间换算就来源于巴比伦的 60 进制计数法。

古希腊人不仅仅将数字当做工具，更融入生活的角落

玛雅人数数从 0 开始，使用 20 进制计数法

罗马人使用 5 进制和 10 进制混用的罗马数字。

印度人再引入巴比伦的按位计数法同时意识到 0 也是数字，而且他们采用的是 10 进制计数法，现在我们使用的 0123456789 被称为阿拉伯数字而不是印度数字，也许是因为将印度数字传入西欧的是阿拉伯学者的缘故。

逻辑

本章讲解为什么逻辑对于程序员很重要。

为何逻辑如此重要

逻辑是消除歧义的工具

在使用自然语言时，是很容易产生歧义，然而，规格说明书，记述如何编写程序的文件一般都是使用自然语言藐视，因此程序员必须走出自言语言歧义的迷宫，谨慎读懂规格说明书，确定其正确的意义。

很多人觉得逻辑冰冷且机械死板，的确但正因如此，他们才有用，人类容易被感情左右，计算机不同，正是因为如此，计算机才会一直稳定运行，为我们所用。

接下来看一些具体问题

兼顾完整性和排他性

下面以巴士车费为例，学习基本的逻辑思路：兼顾完整性和排他性

车费规则

费用规则一：

6 岁以上乘客车费 100 元
6 岁一下乘客车费 0 元

那么根据这个规则判断乘客需不需要付费只需要判断乘客年龄即可。没有什么难点

命题及真假

为了便于理解，先解释几个术语：

在规则中查询车费时候，应先判断乘客的年龄是否超过 6 岁，能够判断对错陈述句的叫做命题。

命题正确时，称该命题为真，反之为假，对应 true 和 false

有没有遗漏

在阅读上面的付费规则时候，需要确定一个重要问题，有没有遗漏。

有没有重复

在确定规则中没有遗漏的同时还需要一个童谣中的问题有没有重复

画一个根数轴辅助思考

确定没有遗漏和重复相当重要，在阅读前面的规则文字时候最好画一个数轴，并在数轴中检测是否有遗漏或者重复。

注意边界值

在数轴中，可以看到边界值是需要注意的，一般规格说明书错误或者程序员的错误，往往发生在边界上，因此在画数轴思考问题的时候，必须清除的明确的指出包含不包含边界值。

使用 if 语句分解问题

实际上根据这种命题的真假来分解问题，就是程序中常用的 if 语句

if (乘客年龄在 >= 6) {
    付费100元
} else {
    无需付费
}

建立复杂命题

并不是所有命题都是纯粹二简单的，有时候为了便是更为复杂的情况，需要建立复杂的命题。

例如：乘客的年龄不到 6 岁，并且乘车日期不是周末

这个命题是由乘客年龄不到6岁和乘车日期不是周末两个命题组成的，两个命题的正确与否是可以判定的，因此它确实可以称作命题。

逻辑非

以乘车日期是星期日这个命题作为基础，可以建立乘车日期不是星期日建立这种不是。。。的命题的运算称作非。英语中使用 not 表示

!乘车日期是周末

双重否定等于肯定

!!乘车日期是周末

逻辑与

通过组合年龄 6 岁以上和乘车日期是星期日这两个命题，可以得到年龄 6 岁以上并且乘车日期是星期日这一新命题，这种 A 并且 B 的命题运算称作逻辑与英语中 and 表示

A & B 表示A和B都为true时候这个命题才为true

逻辑或

假设超市对持有礼券A或持有礼券B的顾客实行打折优惠，同时持有礼券 A 和 B 没关系，持有礼券 A或持有礼券 B，是由持有礼券A和持有礼券B这两个命题组成的，将这种命题运算称为逻辑或。在英语中用 or

A || B A和B有一个为true时候这个命题就为true

异或

现在将假设命题他现在在东京和命题他现在在大阪醋和起来形成命题他现在在东京或者他现在在大阪，这里的或者和前面讲的逻辑或不同，因为他只能在大阪或者东京的其中一处，不可能同时在两地出现

A && B

相等

A = B

若 A 则 B

A 命题乘客的年龄10岁以上，B 命题为乘客的年龄6岁以上，那么若A则B的命题成立原因在于满足命题 A 的乘客必定满足 B

A=>B

余数

周期性和分组

余数就是作除法运算时的剩下的数，不过余数只在学习除法运算时略见其影，然而无论在数学，还是在编程中，余数都起着非常重要的作用。

星期数的思考

思考题：
如果今天是周末，那么 100 天之后是星期几

思考答案

一周七天，七天一个循环

运用余数思考

100/7 = 14 余 2

得到一百天之后是星期二

余数的力量-将较大的数字除一次就能分组

100 天之后是星期二，靠数数就能数过来，如果问题改为一亿天之后是星期几，那么靠数数就解决不了问题了。即使一秒一下的数也要数三年。
如果运用余数的话，一亿天之后的星期数很快就能算出来

100000000/7 = 14285714 余 2

发现规律

在星期数的问题中利用星期数的周期为 7，可以推断除 100 天后的星期树，利用任意天数除以 7 得到的余数就是星期几。

所以只要着眼于 0 的个数，处理超大的数字也会变得更为轻松，这个对数的概念也有密切的关系。

数学归纳法

如何征服无穷数列

数学归纳法是证明耨断言对于 0 以上的所有整数都成立的方法，整数右无穷个，若使用数学归纳法，只需要几个步骤，就能证明有关无穷的命题

高斯求和

有一个储钱罐从第一天开始，存入一元第二天两元第三天三元依次类推，那么 100 天以后储钱罐里面右多少钱

当年高斯大佬是如何解答的想必都知道。

高斯大佬的解答方案绝妙非凡
利用首尾相加等于 101 的规律得出了 5050 元

归纳

高斯运用了一下的等式

$$1+2+3+4+…+100 = \frac{(100+1)*100}{2}$$

这里使用变量 n 将 1 到 100 归纳到 1 到 n 这样上面的等式就变成了

$$ 0+1+2+3…+n = \frac{(n+1)*n}{2}$$

数学归纳法是证明断言对于0以上所有的整数n都成立的方法

数学归纳发-如何政府无穷数列

首先从 0 以上的整数的断言开始学，然后使用数学归纳法来证明高斯的断言

0 以上的整数的断言

0以上的整数n的断言，就是能够判定 0,1,2,3…等个整数为真或者假的断言

例如断言

n × 2 为偶数

又如断言

n × 3 为奇数

高斯的断言

在讨论了 0 以上的整数 n 的断言之后，返回看高斯的断言

断言 G(n)：0 到 n 的整数之和为：$$\frac{n×(n+1)}{2}$$

什么是数学归纳法

数学归纳法是证明有关整数的断言对于 0 以上的所有整数是否成立时候所使用的方法

数学归纳法要经过一下两个步骤进行证明，这是本章核心内容

步骤:

证明P(0)成立
证明不论 K 为 0 以上的哪个整数，若P(k)成立，则P(K+1)也成立

在步骤 1 中，要证明 k 为 0 是断言 P(0)成立，我们将步骤 1 称为基底
在步骤 2 中，要证明无论 k 为 0 以上的哪个整数若P(K)成立，则P(K+1)也成立
我们将步骤 2 称为归纳，该步骤证明断言若对于 0 以上的某个整数成立，则对于下一个整数也成立

求出奇数之和

使用数学归纳法来证明另一个断言

奇数之和

请证明以下断言 Q(n)对于 1 以上所有整数 n 都成立

断言 Q(n):

$$1+2+3+4…+(2×n-1) = n^2$$

按从小到大的顺序将 n 个奇数相加，得到 n²，在证明之前，先通过比较小的数 n = 1、 2、 3、 4、 5 判断 Q(n)的真假

断言 Q(1): 1 = 1²
断言 Q(2): 1 + 3 = 2²
断言 Q(3): 1 + 3 + 5 = 3²
断言 Q(4)：1 + 3 + 5 + 7 = 4²
断言 Q(5)：1 + 3 + 5 + 7 = 5²

通过以上计算发现断言确实是成立的

编程和数学归纳法

通过循环表示数学归纳法

function prove (n) {
    let k
    console.log("现在开始证明"+n+"成立")
    k = 0
    console.log("根据步骤1得出"+k+"成立")
    while (k < n) {
        console.log(`根据步骤2可以说若${k}成立则${k+1}也成立`)
        k = k + 1
    }
    console.log("证明结束")
}
prove(10)

/**
现在开始证明10成立
根据步骤1得出0成立
根据步骤2可以说若0成立则1也成立
根据步骤2可以说若1成立则2也成立
根据步骤2可以说若2成立则3也成立
根据步骤2可以说若3成立则4也成立
根据步骤2可以说若4成立则5也成立
根据步骤2可以说若5成立则6也成立
根据步骤2可以说若6成立则7也成立
根据步骤2可以说若7成立则8也成立
根据步骤2可以说若8成立则9也成立
根据步骤2可以说若9成立则10也成立
证明结束
*/

排列组合

解决计数问题的方法

无论在生活中还是编程中，准确无误计数都非常要，首先学习数数，与整数的对应关系

计数

数数对我们来说是家常便饭，然而数数是究竟是什么样的行为，例如要输出摆放的牌数时，便依次进行下述操作。

选出一张牌说 1
选出一张牌说 2
选出一张牌说 3
选出一张牌说…

重复上述动作，直到所有牌数完为止最后所报之数就是牌数。这是一个将计数对象与整数对应起来的过程，只要与整数正确的对应，计数的结果就是正确的。

加法法则

要数出分为两个集合的事物时，可以使用加法法则

加法法则就是将无重复元素的几个 A、B 相加得到 A+B 的元素数

乘法法则

A × B

置换

将 n 个事物按照顺序进行排列称为置换

递归

自己定义自己

递归是一种奇妙的思考方法，它使用自己来定义自己无论是数学还是编程都经常使用递归

几个例子不知道怎么怎么记，而且递归并不复杂，只要找出问题中隐含的递归结构就能由此到处递归定义和递归递推公式，以递归形式来描述具有递归结构的事物，一来显得比较自然，二来能够简洁的描述复杂的结构

指数爆炸

如何解决复杂的问题

指数是指数字呈爆炸式增长，一旦处理不好，该问题可能会膨胀到难以收拾的底部，相反，若能巧妙利用指数爆炸，它将称为解决问题的有力武器

假设有一张厚度为 1mm 的纸，非常柔软可以对折无数次，每对折一次厚度翻倍，已知地球距离月球 39 万公里，请问对折多少次之后能超过地球到月球距离

答案是 39 次

仅仅对折 39 次就让 1mm 纸的厚度达到了地球到月球的距离，仅仅反复折纸，数字不断翻倍，很快就得到了一个非常庞大的数字，我们把这种数字称为指数爆炸。

二分查找

二分查找也很简单。书上都是图，不好描述

对数

一旦发生指数爆炸，数字就会变得非常庞大，处理这种庞大数字的工具就是–对数

什么事对数

求数字 100000 中 0 的个数 5，就称作求 100000 的对数，也称取对数、计算对数。

再庞大的数，其对数也会相对比较小，因为对对数使用 0 的个数来表示数字，1000 的对数是 3 的表示更正确的写法是以10为底，1000的对数3这里说的底相当于什么的3次方为1000的什么底叶称为基数

$$10^5 = 100000$$
$$log_{10^{100000}} = 5$$

以 2 为底数

$$2^3=8$$
$$log_{2^8} = 3$$

指数法则和对数

$$10^2+10^3 = 10^{2+3}$$

可以得到

$$10^a+10^b = 10^{a+b}$$

而对应的指数运算法则如下

$$log_10(A×B) = log_{10^A}+log_{10^B}$$

密码

利用指数爆炸加密

暴力破解法

现在使用的密码，是用俗称秘钥的随机字节流来加密的，只有知道这个秘钥的人才能将密文还原为原来的消息

如果加密算法没有弱点，那就只能穷举的实验秘钥，即做出和秘钥长度相同的字节流，尝试破解密文，这种密码破解方法称为暴力破解法

字长和安全性的关系

被用作秘钥的字节流长度越长，暴力破解就越费时。
如果密码只有三位，那么正确的秘钥必然是下列八种之一

000 001 010 011 100 101 110 111

如果是四位，那么就有十六种情况，依次类推，尝试的次数是成倍增加的，现实中常用的秘钥都在 128 位以上

如果只考虑是否可以破解，那么几乎所有的密码都是可以使用暴力破解方法来破解的，但是可以破解和可以在现实时间内破解是两回事，一个 512 位的密码，是目前人类的时间和能力远远无法处理的

如何处理指数爆炸

理解空间的大小

比如在书架上找一本书，如果书架上的书没有规律那么查找起来就很复杂了
但是如果书是右规律的那么就很快就能找到，遇到任何问题，只要具备判断是否已有成功破解的方法和按顺序试解的步骤就可以使用暴力破解法。这种方法被称为解密原理

有四中处理方法

对于设计指数爆炸的问题，大体上右四中处理方法

极力求解

第一种方法是直到方法后极力求解，即增强计算机性能方法，但是问题规模稍微扩大之后就应付不了了，这就变成了规模和计算机性能之间的赛跑。

变相求解

第二种方法是转换成简单问题来解决，即寻找更好的解法和算法。但是遗憾的是，对于指数爆炸的问题，并非总能找到一个比一个不漏的反复实验更好的方法，这是一项极具难度的工作

近似求解

第三种方法是不求完全解答，而是找出近似解这是通过估算或者使用模拟器等求解的方法，虽然得出的结果在数学层面不够严谨，但是有助于实际应用

概率求解

第四种方法是概率求解这是求解时使用随机数的方法，好比掷筛子得到的数，靠运气，运气好就能解出来，运气差就。。不过在实际运用中确是非常重要的方法