二进制是盘算机体系的底子，余数被应用在很多常见的算法和数据布局中，而布尔代数是编程中控制逻辑的魂魄。
二进制、余数和布尔代数
1 二进制
很多专业人士都以为盘算机的劈头来自数学中的二进制计数法。这样的观点颇有原理。可以说，没有二进制，就没有如今的盘算机体系。那么什么是二进制呢？为什么盘算机要使用二进制而不是我们日常生计中的十进制呢？如何在代码中操纵二进制呢？在这里我们将从盘算机的劈头——二进制动身，讲解它在盘算机中的“玄机”。
2 余数
余数就是指整数除法中被除数未被除尽的部门，且余数的取值范围为0到除数之间（不包罗除数自身）。例如，27除以11，商为2，余数为5。大概你会烦闷，小门生就能懂的内容，还必要在这里专门拿出来说吗？可不要小看余数，无论是在日常生计中，还是盘算机领域中，它都发挥着重要的作用。
3 布尔代数
在实际生计中，必要屈服各种各样的规则。那么，如何将这些规则表述清楚而且没有异议呢？逻辑和集合就是我们最好的帮忙。它们可以消除自然说话所发生的歧义，并严酷准确地形貌事物。对于以“严谨”而著称的盘算机，逻辑命题及其干系的运算就更显得意义巨大了。作为程序员，如果不能很好地明白这些概念，就会对盘算机无从下手。所以，很有必要来讲一下逻辑和集合，以及它们的底子——布尔代数。
排列、组合和动态规划
1 排列
“田忌跑马”的故事各人都听过，田忌是齐国有名的将领，他常常和齐王跑马，然则老是败下阵来，心中非常不悦。孙膑想帮田忌。他将这些马分为上、中、下三等。他让田忌用自己的下等马来应战齐王的上等马，用上等马应战齐王的中等马，用中等马应战齐王的下等马。3场比赛结束后，田忌只输了第一场，赢了后面两场，最终赢得与齐王的整场比赛。孙膑每次都从田忌的马匹中遴选出一匹，一共举行3次，排列出战的次序，这实在就是数学中的排列历程。从
个差其余元素中掏出
（1
）个差其余元素，按照肯定的次序排成一列，这个历程就叫排列（permutation）。当出现
这种特殊情况的时间，例如，在田忌跑马的故事中，田忌的3匹马必须全部出战，这就是全排列（all permutation）。如果选择出的这
个元素可以有反复的，这样的排列就是可反复排列（permutation with repetition），否则就是弗成反复排列（permutation without repetition）。
图3-1展现了田忌跑马案例中的排列情况。
图3-1 田忌跑马中的排列情况
从图3-1可以看出，所有大概性通过一个树状布局表达。从树的根结点到叶结点，每种路径都是一种排列。有多少个叶结点就有多少种全排列，最终叶结点的数量是
，所以最终排列的数量为6。我们用
、
和
分别体现田忌的上、中、下等马跑完整程所需的时间，用
、
和
分别体现齐王的上、中、下等马跑完整程所需的时间，设定为
。如果你将这些大概的排列，仔细地和齐王的上、中、下等马举行比较，只有{下等, 上等, 中等}这一种大概战胜齐王，也就是
，
，
。
对于通用案例中最终排列的数量，我们可以得到如下结论。
- 对于个元素的全排列，所有大概的排列数量就是，也就是；
- 对于从个元素里掏出（0＜）个元素的不反复排列数量是 ，也就是。
这两点都是可以用数学归纳法证明的，有兴趣的话你可以自己尝试一下。
我们刚才讨论了3匹马的情况，如果有30匹马、300匹马，会发生什么呢？30的阶乘已经是天文数字了。更糟糕的是，如果两组马之间的速度关系也黑白常随机的，例如
，那就不能再使用“己方最差的马和对方最好的马比赛”这种战术了。手工盘算肯定是算不过来了，这个时间盘算机可以帮大忙。我们将使用代码来展现如何天生所有的排列。如果你仔细的话，就会发如今新版舍罕王赏麦的案例中，实在已经涉及了排列的思想，不过谁人案例不是以“选取多少个元素”为终止前提，而是以“选取元素的总和”为终止前提。只管这样，我们仍旧可以使用递归的方法来快速地实现排列。
起首，在差其余选马阶段，我们都要生计已经有几匹马出战、它们的排列次序以及还剩几匹马没有选择。我使用变量result来存储到当前函数操纵之前已经出战的马匹及其排列次序，而变量horses存储到当前函数操纵之前还剩几匹马尚未出战。变量new_result和rest_horses分别从result和horses克隆而来，包管不会影响上一次的结果。其次，孙膑的办法之所以见效，是由于他看到每一等马中，田忌的马只比齐王的差一点点。如果相差太多，大概就会有差其余胜负结果。所以，在设定马匹跑完整程的时间上，我特意设定为
，只有这样才气包管盘算机得出和孙膑相同的结论。基于这两点，代码清单3-1展现了实现细节。
代码清单3-1 田忌跑马中排列的实现
# 齐王跑马及其跑完整程所需的时间q_horses = ['q1', 'q2', 'q3']q_horses_time = {'q1': 1.0, 'q2': 2.0, 'q3': 3.0}# 田忌跑马及其跑完整程所需的时间t_horses = ['t1', 't2', 't3']t_horses_time = {'t1': 1.5, 't2': 2.5, 't3': 3.5}# 找出所有的排列def permutate(horses, selection): # 没有过剩的马匹供选择 if len(horses) == 0: print(selection) # 比较田忌和齐王的马匹，看哪方得胜 compare(selection, q_horses) for each in horses: # 从残剩的未出战马匹中，选择一匹，参加结果 new_selection = selection.copy() new_selection.append(each) # 将已选择的马匹从未出战的列表中移出 rest_horses = horses.copy() rest_horses.remove(each) # 递归挪用，对于残剩的马匹继承天生排列 permutate(rest_horses, new_selection)# 比较田忌和齐王的马匹，看哪方得胜def compare(t, q): t_won_cnt = 0 for i in range(0, len(t)): print(t_horses_time[t], ' ', q_horses_time[q]) if t_horses_time[t] < q_horses_time[q]: t_won_cnt += 1 if t_won_cnt > (len(t) / 2): print('田忌得胜！') else: print('齐王得胜！')if __name__ == '__main__': # 下面是测试代码。固然你可以设置更多的马匹，并增加响应的马匹跑完整程的时间 permutate(t_horses, [])从最终的运行结果可以看出，6种排列中只有一种情况是田忌得胜的。如果田忌不听从孙膑的提议，而是随机支配马匹出战，那么他只有1/6的得胜概率。如果齐王也是随机支配他的马匹出战次序，又会是怎样的结果呢？如果手工来实现的话，大要思绪是为田忌和齐王双方都天生他们各自马匹的全排列，然后再做交错比较，看哪方得胜。这个交错比较的历程也是一个排列的题目，田忌这边有6种次序，而齐王这边也有6种次序，所以一共的大概性是
种。代码清单3-2对全部历程举行了模拟。
代码清单3-2 田忌和齐王都随机支配跑马的模拟
# 找出并生计所有的排列组合，selection生计一个排列，result_set生计所有大概的排列def permutate_and_save(horses, selection, result_set): # 没有过剩的马匹供选择，记载排列 if len(horses) == 0: result_set.append(selection) for each in horses: # 从残剩的未出战马匹中，选择一匹，参加结果 new_selection = selection.copy() new_selection.append(each) # 将已选择的马匹从未出战的列表中移出 rest_horses = horses.copy() rest_horses.remove(each) # 递归挪用，对于残剩的马匹继承天生排列 permutate_and_save(rest_horses, new_selection, result_set)if __name__ == '__main__': t_result_set = [] permutate_and_save(t_horses, [], t_result_set) q_result_set = [] permutate_and_save(q_horses, [], q_result_set) print(t_result_set) print(q_result_set) # 两两比较看输赢 for each_t in t_result_set: for each_q in q_result_set: compare(each_t, each_q)由于交错比较时只必要选择2个元素，分别是田忌的出战次序和齐王的出战次序，所以这里使用2层循环的嵌套来实现。从最后的结果可以看出，田忌得胜的概率仍旧是1/6。在概率中，排列有很大的作用，由于排列会帮助我们列举出随机变量取值的所有大概性，用于天生这个变量的概率分布，之后在第二篇“概率统计”中还会详细先容。其余，排列在盘算机领域中有着很多应用场景。这里讲讲最常见的暗码的暴力破解。先来看2017年网络安全界的两件大事。第一件发生在2017年5月，新型蠕虫式打单病毒WannaCry爆发。其时这个病毒蔓延得非常迅速，盘算机被感染后，其中的文件会被加密锁住，黑客以此会向用户打单比特币。第二件和美国的信用评级公司Equifax有关。仅在2017年内，这个公司就被黑客盗取了大约1.46亿用户的数据。黑客进击的方法多种多样，手段变得越来越高超，然则窃取体系暗码仍旧是最常用的进击方法。有时间，黑客们并不必要真的拿到你的暗码，而是通过“猜”，也就是列举各种大概的暗码，然后逐个地去尝试暗码的正确性。如果某个尝试的暗码正好和原先管理员设置的一样，那么体系就被破解了。这就是常说的暴力破解法。
假设一个暗码是由英文字母构成的，那么每位暗码有52种选择，也就是大小写字母加在一起的数量。那么，天生
位暗码的大概数量就是
种。也就是说，从
（这里
为52）个元素掏出
（0＜
）个元素的可反复全排列，总数量为
。如果你遍历并尝试所有的大概性，就能破解暗码了。不过，纵然存在这种暴力破解法，你也不用担心自己的暗码很轻易被人破解，由于我们平时必要使用暗码登录的网站大概移动端App根本上都限定了肯定时间内尝试暗码的次数，例如1天之内只能尝试5次等。这些次数肯定远远小于暗码排列的大概数量。这也是有些网站或App哀求你肯定使用多种类型的字符来创建暗码的原因，如字母加数字加特殊符号。由于类型越多，
中的
越大，大概数量就越多。如果使用英文字母的4位暗码，就有
种，超过了730万种。如果在暗码中再参加0～9这10个阿拉伯数字，那么大概数量就是
种，超过了1400万种。同理，也可以增加暗码长度，也就是用
中的
来实现这一点。如果在英文字母和阿拉伯数字的底子上，将暗码的长度增加到6位，就是
种，已经超过568亿种了！这还没有考虑键盘上的各种特殊符号。有人估
算了一下，如果用上全部256个ASCII码字符，设置长度为8的暗码，那么一般的黑客必要10年左右的时间才气暴力破解这种暗码。
2 组合
2018世界杯足球赛的激烈赛况各人如今还记忆犹新吧？你知道这场足球盛宴的比赛日程是怎么支配的吗？如果如今你是组委会成员，会怎么支配比赛日程呢？可以用上一节的排列思想，让全部的32支入围球队都和其他球队举行一次主客场的比赛。自己弗成能和自己比赛，是以在这种弗成反复的排列中，主场球队有32种选择，而客场球队有31种选择。那么一共要举行多少场比赛呢？很简朴，就是
场！这个数字非常夸张，纵然一天看2场，也要1年多才气看完。纵然球迷高兴了，然则每队球员要踢主客场共62场，早已累爬下了。既然这样，是否可以撤消主客场制，让恣意两个球队之间只踢1场呢？撤消主客场，这就意味着两个球队之间的比赛由2场降为1场，那么所有比赛场数就是
场，还是很多。这就是要将所有32支球队分成8个小组先举行小组赛的原因。一旦分成小组，每个小组的比赛场数就是
场。所有小组赛就是
场。再加上在16强阶段开始接纳淘汰制，两两淘汰，所以必要
场淘汰赛（最后一次加2是由于尚有3、4名的比赛），那么全部世界杯决赛阶段就有
场比赛。固然，说了这么多，你大概会好奇，这两两配比较赛的场次，我是如何盘算出来的？让我引出本节要讲的概念——组合（combination）。
组合可以说是排列的兄弟，两者类似但又有所差别，这两者的区别在于：组合是不考虑每个元素出现的次序的。从界说上来说，组合是指，从
个差别元素中掏出
（1
）个差其余元素。例如，前面说到的世界杯足球赛的例子，从32支球队里找出恣意2支球队举行比赛，就是从32个元素中掏出2个元素的组合。如果将上一讲中田忌跑马的规则改一下，改为从10匹马里挑出3匹比赛，然则并不关心这3匹马的出战次序，那么这也是一个组合的题目。对于所有
取值的组合之全集合，可以叫作全组合（all combination）。例如，对集合{1, 2, 3}而言，全组合就是{空集, {1}, {2}, {3}, {1, 2}, {1, 3} {2, 3}, {1, 2, 3}}。
如果支配足球比赛时不考虑主客场，也就是不考虑两支球队的次序，两支球队之间只要踢一场就行了。那么从
个元素掏出
个的组合，有多少种大概数量呢？假设某项运动必要3支球队一起比赛，那么32支球队就有
种排列，如果3支球队在一起只要比一场，那么我们要抹除过剩的比赛。3支球队按照恣意次序的比赛有
场，所以从32支球队里掏出3支球队的组合是
。基于此，我们可以扩展成以下两种情况。
（1）
个元素里掏出
个的组合，其大概数量就是从
个里取
个的排列数量除以
个全排列的数量，也就是
。
（2）对全组合而言，大概数量为
种。例如，当
的时间，全组合包罗了8种情况。
这两点都可以用数学归纳法证明，有兴趣的话你可以自己尝试一下。
在3.1节中我们用递归实现了全排列。全组合就是将所有元素列出来，没有太大意义，所以这里阐述如何使用递归从3个元素中选取2个元素的组合。我们假设有3支球队，即
、
和
。从图3-2可以看出，对组合而言，{
,
}已经出现了，是以无需{
,
}。同理，{
,
}已经出现了，是以无需{
,
}等。对于反复的组合，图3-2用叉划失落了。这样，最终只有3种组合了。
图3-2 田忌跑马中的组合情况
那么，如何使用代码来实现呢？下面是一种最简朴粗鲁的做法。
（1）先实现排列的代码，输出所有的排列。例如，{
,
}, {
,
}。
（2）针对每种排列，对其中的元素按照肯定的规则排序。上述两种排列颠末排序后就是{
,
}, {
,
}。
（3）对排序后的排列，去失落反复的那些排列。上述两种排列最终只生计一个{
,
}。
这样做效率就会比较低，很多排列天生之后，最终还是要被当作反复的结果去失落。显然，尚有更好的做法。从图3-2可以看出，被划失落的那些元素都是那些出现次序和原有次序倒置的元素。例如，在原有集合中，
在
的前面，所以我们划失落了{
,
}的组合。这是由于，我们知道
出如今
之前，
的组合中肯定已经包含了
，所以
的组合就无须再考虑
了。是以，我只必要在原有的排列代码上稍作修改，每次传入嵌套函数的残剩元素，即不再是所有的未选择元素，而是出如今当前被选元素之后的那些元素。详细如代码清单3-3所示。
代码清单3-3 球队组合的实现
# 使用函数的递归（嵌套）挪用，找出所有大概的组合# teams生计了如今还未参与组合的球队，selection生计了当前已经组合的球队，m体现要选择的球队数量def combine(teams, selection, m):# 遴选完了m个球队，输出结果 if len(selection) == m: print(selection) return for i in range(0, len(teams)): new_selection = selection.copy() new_selection.append(teams) rest_teams = teams[i + 1:len(teams)] combine(rest_teams, new_selection, m)if __name__ == '__main__': # 这段测试代码，从3个元素中选择2个元素的所有组合 teams = ['t1', 't2', 't3'] combine(teams, [], 2)组合在盘算机领域中也有很多的应用场景，例如大型比赛中赛程的自动支配、多维度的数据分析以及自然说话处置惩罚的优化等。这里用组合的思想来提升自然说话处置惩罚的机能。在搜索引擎中，平日会将每篇很长的文章朋分成一个个的单词，然后对每个单词举行索引，便于日后的查询。然则很多时间，光有单个的单词是不敷的，还要考虑多个单词所构成的词组。例如，“red bluetooth mouse”这样的词组。处置惩罚词组最常见的一种方法是多元文法，也就是将临近的几个单词合并起来，形成一个新的词组。例如，可以将“red”和“bluetooth”合并为“red bluetooth”，还可以将“bluetooth”和“mouse”合并为“bluetooth mouse”。设计多元文法只是为了方便盘算机的处置惩罚，而不考虑组合后的词组是不是有正确的语法和语义。例如“red bluetooth”，从语义的角度来看，这个词组就很希奇。然则毕竟还会天生很多公平的词组，例如“bluetooth mouse”。所以，如果不举行深入的语法分析，实在没办法区分哪些多元词组是有意义的，哪些是没有意义的，是以最简朴的做法就是生计所有词组。
普通的多元文法自己存在一个题目，那就是定逝世了每个元组内单词出现的次序。例如，原文中大概出现的是“red bluetooth mouse”，然则用户在查询的时间大概输入的是“bluetooth mouse red”。这么输入肯定不符合语法，但实际上互联网上的用户常常会这么做。在这种情况下，如果只生计原文的“red bluetooth mouse”，就无法将其和用户输入的“bluetooth red mouse”匹配了。如果不哀求查询词组中单词出现的次序和原文一致，那么该怎么办呢？一种做法是，将每个二元组或三元组举行全排列，得到所有的大概，然则这样的话，二元组的数量就会增加1倍，三元组的数量就会增加5倍，一篇文章的数据生计量就会增加3倍左右。另一种做法是，对用户查询做全排列，将原有的二元组查询变为2个差其余二元组查询，将原有的三元组查询变为6个差其余三元组查询，然则事实是，这样会增加及时查询的耗时。这时可以应用组合。多个单词出现时，我们并不关心它们的次序（也就是不关心排列），而只关心它们的组合。无须关心次序就意味着可以对多元组内的单词举行某种形式的标准化。纵然本来的单词出现次序有所差别，颠末这个标准化历程之后，也会变成唯一的次序。例如，“red bluetooth mouse”，这3个词排序后就是“bluetooth, mouse, red”，而“bluetooth red mouse”排序后也是“bluetooth, mouse, red”，自然两者就能匹配上了。我们所必要做的事情，就是在生计文章多元组和处置惩罚用户查询这两个阶段分别举行这种排序。这样既可以减少生计的数据量，同时又可以减少查询的耗时。这个题目很轻易就办理了。
其余，组合思想还广泛应用在多维度的数据分析中。例如，我们要设计一个连锁店的销售业绩报表，这张报表含有若干属性，包罗分店名称、地点都会、销售品类等。其中，最根本的汇总数据包罗每个分店的销售额、每个都会的销售额、每个品类的销售额。除了这些最根本的数据，还可以利用组合的思想天生更多的筛选前提。
组合和排列有类似之处，都是从
个元素中掏出若干元素。不过，排列考虑了掏出的元素之间的次序，而组合无须考虑这种次序，这是排列和组合最大的区别。是以，组符合合找到多个元素之间的联系而并不在意它们之间的先后次序，例如多元文法中的多元组，这有利于避免不必要的数据生计或操纵。详细到编程，组合和排列两者的实现非常类似。区别在于，组合并不考虑遴选出来的元素是如何排序的。所以，在递归的时间，传入下一个嵌套挪用函数的残剩元素中只必要包含当前被选元素之后的那些元素，以避免反复的组合。
3 动态规划
排列和组合会列举全部大概的情况，常常被用在穷举算法之中。不过，有的时间并不必要暴力地查找所有大概，而只要找到最优解，那么就可以考虑另一种数学思想——动态规划（dynamic programming）。本节我将通过文本搜索的话题来讲一下查询推荐（query suggestion）的实现历程，以及它所使用的动态规划思想。
树和图
1 图和树的概念
简朴地说，图由边和结点构成。如果一个图里所有的边都是有向边，那么这个图就是有向图。如果一个图里所有的边都是无向边，那么这个图就是无向图。既包含有向边又包含无向边的图称为混合图。在有向图中，以结点
为动身点的边的数量，叫作
的出度；以
为尽头的边的数量，叫作
的入度。在图4-1展现的有向图中，结点
的入度是1，出度是2。
图4-1 结点、边、出度和入度
别的几个和图有关的概念是通路、回路和连通。结点和边瓜代构成的序列就是通路。所以，通路上的恣意两个结点是互为连通的。如果一条通路的起始结点
和终止结点
相同，这种特殊的通路就叫作回路。从起始结点到终止结点所颠末的边之数量，就是通路的长度。图4-2展现了一条通路和一条回路，第一条非回路通路的长度是3，第二条回路的长度是4。
图4-2 长度为3的通路和长度为4的回路
明白了图的根本概念，再来看树和有向树。树是一种特殊的图，它是没有简朴回路的连通无向图。这里的简朴回路实在就是指，除了第一个结点和最后一个结点相同外，其余结点不反复出现的回路。可以参考图4-3展现的几种树的布局。
图4-3 几种树的布局
接下来我们将重点先容盘算机领域中最常用的树布局——有向树。有向树是一种树，特殊的是，它的边是有方向的，而且满意以下几个前提。
（1）有且仅有一个结点的入度为0，这个结点称为根。
（2）除根以外的所有结点的入度都为1。从树根到任一结点有且仅有一条有向通路。
（3）除了这些根本界说，有向树尚有几个重要的概念，包罗父结点、子结点、兄弟结点、前辈结点、子弟结点、叶结点、结点的高度（或深度）、树的高度（或深度）。图4-4展现了这些概念，其中根结点的高度被设置为0，依据必要也可以将其设置为1。
图4-4 有向树的根本概念
陈诉了有向树的概念，你会发现它的应用黑白常广泛的，包罗前面在先容递归和排列组合的章节中你都会发现树的身影。
本文截选自《程序员的数学底子课 从理论到Python实践》
本书紧贴盘算机领域，从程序员的需求动身，精心遴选了程序员真正用得上的数学常识，通过生动的案例来解读常识中的难点，使程序员更轻易对实际题目举行数学建模，进而构建出更优化的算法和代码。
本书共分为三大模块：“底子思想”篇梳理编程中常用的数学概念和思想，既由浅入深地精讲数据布局与数学中底子、焦点的数学常识，又分析数学对编程和算法的真正意义；“概率统计”篇以概率统计中焦点的贝叶斯公式为基点，向上讲解随机变量、概率分布等底子概念，向下讲解朴素贝叶斯，并分析其在生计和编程中的实际应用，使读者真正明白概率统计的本质，跨越概念和应用之间的鸿沟；“线性代数”篇从线性代数中的焦点概念向量、矩阵、线性方程入手，逐步深入分析这些概念是如何与盘算机领悟贯通以办理实际题目标。除了理论常识的阐述，本书还通过Python说话，分享了通过大量实践积聚下来的名贵经验和编码，使读者学有所用。
本书的内容从概念到应用，再到本质，层层深入，不但注意造就读者养成良好的数学头脑，而且积极使读者的编程技术实现进阶，非常适合希望从本质上提升编程质量的中级程序员浏览和进修。 |
