计算领域中的数学知识都有哪些？

怼烎@ 2022-11-18 01:23 282阅读 0赞

二进制是计算机系统的基础，余数被运用在很多常见的算法和数据结构中，而布尔代数是编程中控制逻辑的灵魂。

二进制、余数和布尔代数

# 1　二进制 #

许多专业人士都认为计算机的起源来自数学中的二进制计数法。这样的观点颇有道理。可以说，没有二进制，就没有如今的计算机系统。那么什么是二进制呢？为什么计算机要使用二进制而不是我们日常生活中的十进制呢？如何在代码中操作二进制呢？在这里我们将从计算机的起源——二进制出发，讲解它在计算机中的“玄机”。

# 2　余数 #

余数就是指整数除法中被除数未被除尽的部分，且余数的取值范围为0到除数之间（不包括除数自身）。例如，27除以11，商为2，余数为5。可能你会纳闷，小学生就能懂的内容，还需要在这里专门拿出来说吗？可不要小看余数，无论是在日常生活中，还是计算机领域中，它都发挥着重要的作用。

# 3　布尔代数 #

在实际生活中，需要遵守各种各样的规则。那么，如何将这些规则表述清楚并且没有异议呢？逻辑和集合就是我们最好的帮手。它们可以消除自然语言所产生的歧义，并严格准确地描述事物。对于以“严谨”而著称的计算机，逻辑命题及其相关的运算就更显得意义重大了。作为程序员，如果不能很好地理解这些概念，就会对计算机无从下手。所以，很有必要来讲一下逻辑和集合，以及它们的基础——布尔代数。

排列、组合和动态规划

# 1　排列 #

“田忌赛马”的故事大家都听过，田忌是齐国有名的将领，他常常和齐王赛马，可是总是败下阵来，心中非常不悦。孙膑想帮田忌。他将这些马分为上、中、下三等。他让田忌用自己的下等马来应战齐王的上等马，用上等马应战齐王的中等马，用中等马应战齐王的下等马。3场比赛结束后，田忌只输了第一场，赢了后面两场，最终赢得与齐王的整场比赛。孙膑每次都从田忌的马匹中挑选出一匹，一共进行3次，排列出战的顺序，这其实就是数学中的排列过程。从

![e4b7de84f05d4de5fd543db6287cab30.gif][]

个不同的元素中取出

![dc6c837c171e430ac54634bd15510925.gif][]

（1

![7b96402f552353ac682b541559a7acc8.gif][]

![060eb0a5583927f8b98cfc95532cb28d.gif][]

![8dd337edd04f55248509a04b33cfe76d.gif][]

![35663e374860b6e1f5638841b54b9a48.gif][]

）个不同的元素，按照一定的顺序排成一列，这个过程就叫**排列**（permutation）。当出现

![13981f498085fb0230e4d8c99b817a71.gif][]

这种特殊情况的时候，例如，在田忌赛马的故事中，田忌的3匹马必须全部出战，这就是**全排列**（all permutation）。如果选择出的这

![7df215589fb44534d2941210c560e3e4.gif][]

个元素可以有重复的，这样的排列就是**可重复排列**（permutation with repetition），否则就是**不可重复排列**（permutation without repetition）。

图3-1展示了田忌赛马案例中的排列情况。

![3c39898d664ba61394567acb3b9f2f88.png][]

图3-1　田忌赛马中的排列情况

从图3-1可以看出，所有可能性通过一个树状结构表达。从树的根结点到叶结点，每种路径都是一种排列。有多少个叶结点就有多少种全排列，最终叶结点的数量是

![10e35a8949c636e817abfef7ef036097.gif][]

，所以最终排列的数量为6。我们用

![b4002feaab38f4442231fdac7d2f0696.gif][]

、

![4a344c5c19ed07e9d1836468aef2c119.gif][]

和

![dd0b8adad8210b700d8d971ad12e930b.gif][]

分别表示田忌的上、中、下等马跑完全程所需的时间，用

![f247609c05cca69971184dcc02082c42.gif][]

、

![813d7507fa246d155d65d5e5d26fed52.gif][]

和

![36e122daadf0aa081177d6311be6cc08.gif][]

分别表示齐王的上、中、下等马跑完全程所需的时间，设定为

![43341ec7bcf31e6cab3323e932ea7ead.gif][]

。如果你将这些可能的排列，仔细地和齐王的上、中、下等马进行对比，只有\{下等, 上等, 中等\}这一种可能战胜齐王，也就是

![8ba0b54d9f509341e63129c36a0e94fb.gif][]

，

![ff0aff6f2721345c023bfcfea9639120.gif][]

，

![8dabf61c28068776df03bae59f28fc44.gif][]

。

对于通用案例中最终排列的数量，我们可以得到如下结论。

*  对于个元素的全排列，所有可能的排列数量就是，也就是；
 *  对于从个元素里取出（0＜）个元素的不重复排列数量是 ，也就是。

这两点都是可以用数学归纳法证明的，有兴趣的话你可以自己尝试一下。

我们刚才讨论了3匹马的情况，如果有30匹马、300匹马，会发生什么呢？30的阶乘已经是天文数字了。更糟糕的是，如果两组马之间的速度关系也是非常随机的，例如

![38ee9676b5b57e7eca8d4790b11177a5.gif][]

，那就不能再使用“己方最差的马和对方最好的马比赛”这种战术了。手工计算肯定是算不过来了，这个时候计算机可以帮大忙。我们将使用代码来展示如何生成所有的排列。如果你细心的话，就会发现在新版舍罕王赏麦的案例中，其实已经涉及了排列的思想，不过那个案例不是以“选取多少个元素”为终止条件，而是以“选取元素的总和”为终止条件。尽管这样，我们仍然可以使用递归的方式来快速地实现排列。

首先，在不同的选马阶段，我们都要保存已经有几匹马出战、它们的排列顺序以及还剩几匹马没有选择。我使用变量result来存储到当前函数操作之前已经出战的马匹及其排列顺序，而变量horses存储到当前函数操作之前还剩几匹马尚未出战。变量new\_result和rest\_horses分别从result和horses克隆而来，保证不会影响上一次的结果。其次，孙膑的方法之所以奏效，是因为他看到每一等马中，田忌的马只比齐王的差一点点。如果相差太多，可能就会有不同的胜负结果。所以，在设定马匹跑完全程的时间上，我特意设定为

![97e0abdb202f0172d9609a3721ccf183.gif][]

，只有这样才能保证计算机得出和孙膑相同的结论。基于这两点，代码清单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[i]], ' ', q_horses_time[q[i]])
            if t_horses_time[t[i]] < q_horses_time[q[i]]:
               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种顺序，所以一共的可能性是

![a288ae19ba606c7cac611561f018d96f.gif][]

种。代码清单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种选择，也就是大小写字母加在一起的数量。那么，生成

![7d2e1259b408b3b58f3798d46c8245c1.gif][]

位密码的可能数量就是

![48bbb59f1c91016c4292ddf12d88cc25.gif][]

种。也就是说，从

![3845a7cded4bb2e8fc624b140151ca2d.gif][]

（这里

![24900062df1a068847c469000a11c88f.gif][]

为52）个元素取出

![037cd83808114c1577f0253416671d11.gif][]

（0＜

![6d5293aa4a9a4e15986c450701c5e484.gif][]

![f402376d472dbe0a7209177d08bc5a92.gif][]

![415c09ce2b235ab1f388233cf82cabca.gif][]

）个元素的可重复全排列，总数量为

![7d1f7ae849bb651bff0d6148ab2cb059.gif][]

。如果你遍历并尝试所有的可能性，就能破解密码了。不过，即使存在这种暴力破解法，你也不用担心自己的密码很容易被人破解，因为我们平时需要使用密码登录的网站或者移动端App基本上都限定了一定时间内尝试密码的次数，例如1天之内只能尝试5次等。这些次数一定远远小于密码排列的可能数量。这也是有些网站或App要求你一定使用多种类型的字符来创建密码的原因，如字母加数字加特殊符号。因为类型越多，

![7c8f0e0cae18c0d5f20bcfe96ba9e98b.gif][]

中的

![afe01502982b21941ac701ed722d5fa3.gif][]

越大，可能数量就越多。如果使用英文字母的4位密码，就有

![ddb3237607448bf419ebbfa10f4b6e1a.gif][]

种，超过了730万种。如果在密码中再加入0～9这10个阿拉伯数字，那么可能数量就是

![f6394672c33d7798d8bd07d69665d759.gif][]

种，超过了1400万种。同理，也可以增加密码长度，也就是用

![ac82e0b4b8cea031711e4228eac9a7fe.gif][]

中的

![fcbad97d225ccc4712140ef4ecc13bfd.gif][]

来实现这一点。如果在英文字母和阿拉伯数字的基础上，将密码的长度增加到6位，就是

![525746a406ee8d7af6edfcf483b79301.gif][]

种，已经超过568亿种了！这还没有考虑键盘上的各种特殊符号。有人估

算了一下，如果用上全部256个ASCII码字符，设置长度为8的密码，那么一般的黑客需要10年左右的时间才能暴力破解这种密码。

# 2　组合 #

2018世界杯足球赛的激烈赛况大家现在还记忆犹新吧？你知道这场足球盛宴的比赛日程是怎么安排的吗？如果现在你是组委会成员，会怎么安排比赛日程呢？可以用上一节的排列思想，让全部的32支入围球队都和其他球队进行一次主客场的比赛。自己不可能和自己比赛，因此在这种不可重复的排列中，主场球队有32种选择，而客场球队有31种选择。那么一共要进行多少场比赛呢？很简单，就是

![7e292e4ea59568bc2a89b8643204fb37.gif][]

场！这个数字非常夸张，即使一天看2场，也要1年多才能看完。即使球迷开心了，可是每队球员要踢主客场共62场，早已累趴下了。既然这样，是否可以取消主客场制，让任意两个球队之间只踢1场呢？取消主客场，这就意味着两个球队之间的比赛由2场降为1场，那么所有比赛场数就是

![6ba6162fa1578d94ad4ee45345c11d8c.gif][]

场，还是很多。这就是要将所有32支球队分成8个小组先进行小组赛的原因。一旦分成小组，每个小组的比赛场数就是

![c224c5598ff71e52e51c847952419bf7.gif][]

场。所有小组赛就是

![4f32be92776d7cff449dfe60a84c2a2b.gif][]

场。再加上在16强阶段开始采取淘汰制，两两淘汰，所以需要

![24ee37913ea56610490c0f09f46cce5b.gif][]

场淘汰赛（最后一次加2是因为还有3、4名的比赛），那么整个世界杯决赛阶段就有

![ebf7a6a5af086b41d7f32c3ffe834ac5.gif][]

场比赛。当然，说了这么多，你可能会好奇，这两两配对比赛的场次，我是如何计算出来的？让我引出本节要讲的概念——**组合**（combination）。

组合可以说是排列的兄弟，两者类似但又有所不同，这两者的区别在于：组合是不考虑每个元素出现的顺序的。从定义上来说，组合是指，从

![966c1f7f2309f361e9b0c060dc065af4.gif][]

个不同元素中取出

![a145f575aa9407f6ea84eee3079fddec.gif][]

（1

![1790ac4cb1188a43653431fee5dfedca.gif][]

![36037662e2894e7da1f8d66d4abb9022.gif][]

![db99273c726fdb3fb52a0a42d3db96f3.gif][]

![9e4fb882de9d27a955dc39f265023618.gif][]

）个不同的元素。例如，前面说到的世界杯足球赛的例子，从32支球队里找出任意2支球队进行比赛，就是从32个元素中取出2个元素的组合。如果将上一讲中田忌赛马的规则改一下，改为从10匹马里挑出3匹比赛，但是并不关心这3匹马的出战顺序，那么这也是一个组合的问题。对于所有

![48be260fdce671cf003acac1ac6dae28.gif][]

取值的组合之全集合，可以叫作**全组合**（all combination）。例如，对集合\{1, 2, 3\}而言，全组合就是\{空集, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\} \{2, 3\}, \{1, 2, 3\}\}。

如果安排足球比赛时不考虑主客场，也就是不考虑两支球队的顺序，两支球队之间只要踢一场就行了。那么从

![df7e1af23f46f66b32c7f69fa96bf7d6.gif][]

个元素取出

![444ab7f947dfc4a218aad5654182efb0.gif][]

个的组合，有多少种可能数量呢？假设某项运动需要3支球队一起比赛，那么32支球队就有

![acd3deeac8ba6086c88783d63997790a.gif][]

种排列，如果3支球队在一起只要比一场，那么我们要抹除多余的比赛。3支球队按照任意顺序的比赛有

![1316e023d9e68322f3b38d6a0e473888.gif][]

场，所以从32支球队里取出3支球队的组合是

![ca8b239e4c39a50fe7439343535ad5e0.gif][]

。基于此，我们可以扩展成以下两种情况。

（1）

![a7316174ca10caab1d37baa04dd54adc.gif][]

个元素里取出

![94b9c201615688c8e48d6b6efab02b47.gif][]

个的组合，其可能数量就是从

![6665862d18dc1c646ffa8d42a9efe768.gif][]

个里取

![2888308152255344e1b97bb1fb6b1aa9.gif][]

个的排列数量除以

![e6a6754726bb19f7cc646bd893895f3e.gif][]

个全排列的数量，也就是

![2aa1cb3e1cbe4b9c225c79558449e155.gif][]

。

（2）对全组合而言，可能数量为

![e45ede12fe2699eb83a7b7e85ac9fa5d.gif][]

种。例如，当

![a4ffa4d634d74a34ddd6591bfb944281.gif][]

的时候，全组合包括了8种情况。

这两点都可以用数学归纳法证明，有兴趣的话你可以自己尝试一下。

在3.1节中我们用递归实现了全排列。全组合就是将所有元素列出来，没有太大意义，所以这里阐述如何使用递归从3个元素中选取2个元素的组合。我们假设有3支球队，即

![e00ce1e44deeda2df5146d783ee58a77.gif][]

、

![90946b5decf247bf336f233f5a168d3e.gif][]

和

![d9e514728067be40ed42ad71b8b75d97.gif][]

。从图3-2可以看出，对组合而言，\{

![d71914012d1029c349e6600bad4fe243.gif][]

![89d905b397ce0a6041c95a31360eea1a.gif][]

\}已经出现了，因此无需\{

![9af60d0d249e09a507f31e4bea3aa611.gif][]

![1e3c5fa9e431793f868d7486826aa42c.gif][]

\}。同理，\{

![f693e599c335b98e2de1361ff865d756.gif][]

![2f74fd3e4fdcc79710b20e3677eb5094.gif][]

\}已经出现了，因此无需\{

![aa1001450f1eb3c055efc55586ddcdee.gif][]

![bc7297fbe74014512f7332378eebd88d.gif][]

\}等。对于重复的组合，图3-2用叉划掉了。这样，最终只有3种组合了。

![edae0cd410b31b17dcb864dd6d0d467c.png][]

图3-2　田忌赛马中的组合情况

那么，如何使用代码来实现呢？下面是一种最简单粗暴的做法。

（1）先实现排列的代码，输出所有的排列。例如，\{

![45c9b58d0d36f79b07f1bc95cb634c7c.gif][]

![f1b15a280bff855107dea3d43913acb5.gif][]

\}, \{

![f1d450e2a2924a84444f96fd18b07880.gif][]

![e13b375220e2af09efb0240f8b8cfbde.gif][]

\}。

（2）针对每种排列，对其中的元素按照一定的规则排序。上述两种排列经过排序后就是\{

![b3c34c67f8e91f061e491f494c223baf.gif][]

![14f7ef44eb73b8d501900745a0133099.gif][]

\}, \{

![d5973be05b555dc926ae2af1661c8785.gif][]

![ce37774d032f4cc7599946c4288eb642.gif][]

\}。

（3）对排序后的排列，去掉重复的那些排列。上述两种排列最终只保留一个\{

![b29d74d5fc868ba931e11cb036718ec3.gif][]

![52898f6ea7751c009c53ece1c3ca49b0.gif][]

\}。

这样做效率就会比较低，很多排列生成之后，最终还是要被当作重复的结果去掉。显然，还有更好的做法。从图3-2可以看出，被划掉的那些元素都是那些出现顺序和原有顺序颠倒的元素。例如，在原有集合中，

![bd6d8fed364e14430170cd210234adeb.gif][]

在

![7502e125cb4911ecf0b0b09d517fd8b9.gif][]

的前面，所以我们划掉了\{

![16748d7e6df9bef4af57349b31ff5eb2.gif][]

![3cdb5ef1d49fb04b889972746de76fe4.gif][]

\}的组合。这是因为，我们知道

![27b9fdb6707da0c1099bf17feb4a79fb.gif][]

出现在

![c596089dd652cc4b30cf13ebc921b72d.gif][]

之前，

![f42c26169586bfaf5225cfcfea88ec5c.gif][]

的组合中一定已经包含了

![0c9d62a716a350994aa12dff1125b818.gif][]

，所以

![d41ea129075366230a9380ffbd6858f4.gif][]

的组合就无须再考虑

![dd66470743a1e095709633944df98e7e.gif][]

了。因此，我只需要在原有的排列代码上稍作修改，每次传入嵌套函数的剩余元素，即不再是所有的未选择元素，而是出现在当前被选元素之后的那些元素。具体如代码清单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[i])
    
           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”，自然两者就能匹配上了。我们所需要做的事情，就是在保存文章多元组和处理用户查询这两个阶段分别进行这种排序。这样既可以减少保存的数据量，同时又可以减少查询的耗时。这个问题很容易就解决了。

此外，组合思想还广泛应用在多维度的数据分析中。例如，我们要设计一个连锁店的销售业绩报表，这张报表含有若干属性，包括分店名称、所在城市、销售品类等。其中，最基本的汇总数据包括每个分店的销售额、每个城市的销售额、每个品类的销售额。除了这些最基本的数据，还可以利用组合的思想生成更多的筛选条件。

组合和排列有相似之处，都是从

![59528b7a48281efdb5bb670836676fc2.gif][]

个元素中取出若干元素。不过，排列考虑了取出的元素之间的顺序，而组合无须考虑这种顺序，这是排列和组合最大的区别。因此，组合适合找到多个元素之间的联系而并不在意它们之间的先后顺序，例如多元文法中的多元组，这有利于避免不必要的数据保存或操作。具体到编程，组合和排列两者的实现非常类似。区别在于，组合并不考虑挑选出来的元素是如何排序的。所以，在递归的时候，传入下一个嵌套调用函数的剩余元素中只需要包含当前被选元素之后的那些元素，以避免重复的组合。

# 3　动态规划 #

排列和组合会列举全部可能的情况，经常被用在穷举算法之中。不过，有的时候并不需要暴力地查找所有可能，而只要找到最优解，那么就可以考虑另一种数学思想——**动态规划**（dynamic programming）。本节我将通过文本搜索的话题来讲一下**查询推荐**（query suggestion）的实现过程，以及它所使用的动态规划思想。

树和图

# 1　图和树的概念 #

简单地说，图由边和结点组成。如果一个图里所有的边都是有向边，那么这个图就是有向图。如果一个图里所有的边都是无向边，那么这个图就是无向图。既包含有向边又包含无向边的图称为混合图。在有向图中，以结点

![3bbfff68fb4681abc50d6d19fdad6945.gif][]

为出发点的边的数量，叫作

![e349f3d85e9cd4c9d133f5934855fa96.gif][]

的出度；以

![dbdedb377a2227b78de0c0b336086f3d.gif][]

为终点的边的数量，叫作

![6d8ed76d74362920a4294fe09c9d78df.gif][]

的入度。在图4-1展示的有向图中，结点

![7d4528ee4052536eaeb215bab73827f0.gif][]

的入度是1，出度是2。

![8ff797a66b6d083f75f3fa41857acf0b.png][]

图4-1　结点、边、出度和入度

另外几个和图有关的概念是通路、回路和连通。结点和边交替组成的序列就是通路。所以，通路上的任意两个结点是互为连通的。如果一条通路的起始结点

![e815c978dc134579f8311280a05c8410.gif][]

和终止结点

![dea4e67b7c9e217a2d8e821b5d45a757.gif][]

相同，这种特殊的通路就叫作回路。从起始结点到终止结点所经过的边之数量，就是通路的长度。图4-2展示了一条通路和一条回路，第一条非回路通路的长度是3，第二条回路的长度是4。

![6001ecef4db0c5729b2b6de88f5c5496.png][]

图4-2　长度为3的通路和长度为4的回路

理解了图的基本概念，再来看树和有向树。树是一种特殊的图，它是没有简单回路的连通无向图。这里的简单回路其实就是指，除了第一个结点和最后一个结点相同外，其余结点不重复出现的回路。可以参考图4-3展示的几种树的结构。

![25d2af87f5962152a7db309081ba1cf9.png][]

图4-3　几种树的结构

接下来我们将重点介绍计算机领域中最常用的树结构——有向树。有向树是一种树，特殊的是，它的边是有方向的，并且满足以下几个条件。

（1）有且仅有一个结点的入度为0，这个结点称为根。

（2）除根以外的所有结点的入度都为1。从树根到任一结点有且仅有一条有向通路。

（3）除了这些基本定义，有向树还有几个重要的概念，包括父结点、子结点、兄弟结点、前辈结点、后辈结点、叶结点、结点的高度（或深度）、树的高度（或深度）。图4-4展示了这些概念，其中根结点的高度被设置为0，根据需要也可以将其设置为1。

![61245274a524c53ccd1d6fd4d7950f59.png][]

图4-4　有向树的基本概念

讲述了有向树的概念，你会发现它的应用是非常广泛的，包括前面在介绍递归和排列组合的章节中你都会发现树的身影。  
  
**本文截选自**[《程序员的数学基础课 从理论到Python实践》][_Python]

![ecd632aef92e62caa7b305ef6d53f08e.png][]

本书紧贴计算机领域，从程序员的需求出发，精心挑选了程序员真正用得上的数学知识，通过生动的案例来解读知识中的难点，使程序员更容易对实际问题进行数学建模，进而构建出更优化的算法和代码。

本书共分为三大模块：“基础思想”篇梳理编程中常用的数学概念和思想，既由浅入深地精讲数据结构与数学中基础、核心的数学知识，又阐明数学对编程和算法的真正意义；“概率统计”篇以概率统计中核心的贝叶斯公式为基点，向上讲解随机变量、概率分布等基础概念，向下讲解朴素贝叶斯，并分析其在生活和编程中的实际应用，使读者真正理解概率统计的本质，跨越概念和应用之间的鸿沟；“线性代数”篇从线性代数中的核心概念向量、矩阵、线性方程入手，逐步深入分析这些概念是如何与计算机融会贯通以解决实际问题的。除了理论知识的阐述，本书还通过Python语言，分享了通过大量实践积累下来的宝贵经验和编码，使读者学有所用。

本书的内容从概念到应用，再到本质，层层深入，不但注重培养读者养成良好的数学思维，而且努力使读者的编程技术实现进阶，非常适合希望从本质上提升编程质量的中级程序员阅读和学习。

[e4b7de84f05d4de5fd543db6287cab30.gif]: /images/20221022/29772f173ba2493d8d357cf3acb33d5e.png
[dc6c837c171e430ac54634bd15510925.gif]: /images/20221022/f1b48b98bd2f4b99b634f1ebf5431225.png
[7b96402f552353ac682b541559a7acc8.gif]: /images/20221022/a69fc0e36d294059841923497f58c14c.png
[060eb0a5583927f8b98cfc95532cb28d.gif]: /images/20221022/a309d402f760437185c5bf4f1345a92c.png
[8dd337edd04f55248509a04b33cfe76d.gif]: /images/20221022/22e08b65d6764928ab7a6edd98258e79.png
[35663e374860b6e1f5638841b54b9a48.gif]: /images/20221022/5e047e2855fa47109d524aa3fdf13fcd.png
[13981f498085fb0230e4d8c99b817a71.gif]: /images/20221022/12d3075aad8a43349bc3cfef47aa590f.png
[7df215589fb44534d2941210c560e3e4.gif]: /images/20221022/a40223764afd4d03a941f365eb9fd35e.png
[3c39898d664ba61394567acb3b9f2f88.png]: /images/20221022/21d816fae1364d549adcbb02f4ebfa38.png
[10e35a8949c636e817abfef7ef036097.gif]: /images/20221022/699be88b0a414b5fbdd51038b34e3ffc.png
[b4002feaab38f4442231fdac7d2f0696.gif]: /images/20221022/1e27ddfff03743aba0f0e5152490384d.png
[4a344c5c19ed07e9d1836468aef2c119.gif]: /images/20221022/809a4e8567604683a822fc8dbc06fa40.png
[dd0b8adad8210b700d8d971ad12e930b.gif]: /images/20221022/195ed8b476b64b78928322a8f47e7a84.png
[f247609c05cca69971184dcc02082c42.gif]: /images/20221022/42cd1c7d79dc4a1d8c31388842e44041.png
[813d7507fa246d155d65d5e5d26fed52.gif]: /images/20221022/417b98e128df432b865dbcf15fa7ba5c.png
[36e122daadf0aa081177d6311be6cc08.gif]: /images/20221022/f511002203e34fb9bc9ebeac6b5dae12.png
[43341ec7bcf31e6cab3323e932ea7ead.gif]: /images/20221022/74cd9b5f0a1747b28daf804e90e16dd6.png
[8ba0b54d9f509341e63129c36a0e94fb.gif]: /images/20221022/244ba81e6c8d4f289d45749de8a0b2f2.png
[ff0aff6f2721345c023bfcfea9639120.gif]: /images/20221022/b7e1f4253ce8441795f3927c27958aff.png
[8dabf61c28068776df03bae59f28fc44.gif]: /images/20221022/95bcd53c332e46c289899c44b1572a8c.png
[38ee9676b5b57e7eca8d4790b11177a5.gif]: /images/20221022/026b739b1197400695a6077ec473023e.png
[97e0abdb202f0172d9609a3721ccf183.gif]: /images/20221022/ec4af1b44bb74e69927ef8f6ff1d84b3.png
[a288ae19ba606c7cac611561f018d96f.gif]: /images/20221022/24966edf99ce4666bfaed68855c50cf4.png
[7d2e1259b408b3b58f3798d46c8245c1.gif]: /images/20221022/f0f6f4507a534dc2a772d0f24d5baf20.png
[48bbb59f1c91016c4292ddf12d88cc25.gif]: /images/20221022/250e814c68d04be7833f8c85313b8fc1.png
[3845a7cded4bb2e8fc624b140151ca2d.gif]: /images/20221022/13da59decead48bcb03c48c71b6c1be2.png
[24900062df1a068847c469000a11c88f.gif]: /images/20221022/a5f2433d7f444f25867549868c8239dd.png
[037cd83808114c1577f0253416671d11.gif]: /images/20221022/73dad81fcfd7445e819a80bc39485841.png
[6d5293aa4a9a4e15986c450701c5e484.gif]: /images/20221022/cef7f01cc5f94df082ecad648197aba0.png
[f402376d472dbe0a7209177d08bc5a92.gif]: /images/20221022/ce1f52969ce944c5a6bf8221d2ac4a51.png
[415c09ce2b235ab1f388233cf82cabca.gif]: /images/20221022/2dd5b12ea72444968ff46d923d84685b.png
[7d1f7ae849bb651bff0d6148ab2cb059.gif]: /images/20221022/d89f59efc61c4c269e623abd8a54164b.png
[7c8f0e0cae18c0d5f20bcfe96ba9e98b.gif]: /images/20221022/9ffe6ad251dc463092ac73a28bc19b45.png
[afe01502982b21941ac701ed722d5fa3.gif]: /images/20221022/45b91062022a4810a9635c794db3ec9b.png
[ddb3237607448bf419ebbfa10f4b6e1a.gif]: /images/20221022/2e7775b9d9df4ef590f662faffce3c71.png
[f6394672c33d7798d8bd07d69665d759.gif]: /images/20221022/f1d70462a7214c49b3e6baba3825d659.png
[ac82e0b4b8cea031711e4228eac9a7fe.gif]: /images/20221022/5bcfb5aa708b4d41ad1c1689f8d7733d.png
[fcbad97d225ccc4712140ef4ecc13bfd.gif]: /images/20221022/3857ceecf50f4317bec77f1a8e28dae3.png
[525746a406ee8d7af6edfcf483b79301.gif]: /images/20221022/3230259057824dc5bc7412b7dba8aaab.png
[7e292e4ea59568bc2a89b8643204fb37.gif]: /images/20221022/7a816d52c590456eb2975f6471585b8a.png
[6ba6162fa1578d94ad4ee45345c11d8c.gif]: /images/20221022/cddc5ce2f9ae478ea9633bbb676c5eaf.png
[c224c5598ff71e52e51c847952419bf7.gif]: /images/20221022/27a9ddb44c944af5b4adf396d7d100ac.png
[4f32be92776d7cff449dfe60a84c2a2b.gif]: /images/20221022/776ed3815e054df1b4dc5734885a5799.png
[24ee37913ea56610490c0f09f46cce5b.gif]: /images/20221022/257bf989db7249d8a6dd40061452f232.png
[ebf7a6a5af086b41d7f32c3ffe834ac5.gif]: /images/20221022/368e8ef99f264b7487c35f155c4debc2.png
[966c1f7f2309f361e9b0c060dc065af4.gif]: /images/20221022/3bcac4815ead4d8c905b872b81f7b217.png
[a145f575aa9407f6ea84eee3079fddec.gif]: /images/20221022/fc7dc0e04fba4254bc1850d548c79813.png
[1790ac4cb1188a43653431fee5dfedca.gif]: /images/20221022/d981127e93154df985f521a9ff3a6141.png
[36037662e2894e7da1f8d66d4abb9022.gif]: /images/20221022/5e4fc46dc00648ca820d6563ee0485b5.png
[db99273c726fdb3fb52a0a42d3db96f3.gif]: /images/20221022/6351ae75af594694acf4949d96946bbb.png
[9e4fb882de9d27a955dc39f265023618.gif]: /images/20221022/db2edf2d6bdd442b998c9a906c946ec0.png
[48be260fdce671cf003acac1ac6dae28.gif]: /images/20221022/3179504661064cd3b8c8703226de1067.png
[df7e1af23f46f66b32c7f69fa96bf7d6.gif]: /images/20221022/74f74b30d0e2480bbaf758d869c04ec2.png
[444ab7f947dfc4a218aad5654182efb0.gif]: /images/20221022/7d115e89058e40f792ef85d9f999d806.png
[acd3deeac8ba6086c88783d63997790a.gif]: /images/20221022/1d0a722b9d5e4e5b86b09c540c20cf04.png
[1316e023d9e68322f3b38d6a0e473888.gif]: /images/20221022/fb3b102e80bf4d7ba5a3b8cdfe5aff60.png
[ca8b239e4c39a50fe7439343535ad5e0.gif]: /images/20221022/adc11a2f93b744518f5b59ba4f76aa68.png
[a7316174ca10caab1d37baa04dd54adc.gif]: /images/20221022/3e76dc45c208474989ba3c40d544ae31.png
[94b9c201615688c8e48d6b6efab02b47.gif]: /images/20221022/0bbb2e8875a44e9da2fd140be44be61c.png
[6665862d18dc1c646ffa8d42a9efe768.gif]: /images/20221022/02f4ae0784ee4d8ca93e88117f3c6ff8.png
[2888308152255344e1b97bb1fb6b1aa9.gif]: /images/20221022/052c798e006641798102c8d24eb6a3f8.png
[e6a6754726bb19f7cc646bd893895f3e.gif]: /images/20221022/5abd7ee4527d41fd86b4504d57caefe4.png
[2aa1cb3e1cbe4b9c225c79558449e155.gif]: /images/20221022/8126677c3b204f7e9f82d6b3b53c093a.png
[e45ede12fe2699eb83a7b7e85ac9fa5d.gif]: /images/20221022/4b1cd01d4abb44b1ac3953a8e2363360.png
[a4ffa4d634d74a34ddd6591bfb944281.gif]: /images/20221022/81162a7932ea42fc97754a12020103d9.png
[e00ce1e44deeda2df5146d783ee58a77.gif]: /images/20221022/58b67a014ef34337a056cf3bdf175a85.png
[90946b5decf247bf336f233f5a168d3e.gif]: /images/20221022/2e75b90c6e4e43b888e4d5b50a15293a.png
[d9e514728067be40ed42ad71b8b75d97.gif]: /images/20221022/556665dbf6234a4ea5513625bd35ffbd.png
[d71914012d1029c349e6600bad4fe243.gif]: /images/20221022/4d8244c4e8084570b555c203df1a646a.png
[89d905b397ce0a6041c95a31360eea1a.gif]: /images/20221022/00ff0553c7a047b791978cada0a75de2.png
[9af60d0d249e09a507f31e4bea3aa611.gif]: /images/20221022/e8b32669f42342d7b1c6715db5f94e50.png
[1e3c5fa9e431793f868d7486826aa42c.gif]: /images/20221022/816b42a9699c4cfc8dd94e1d84d43f45.png
[f693e599c335b98e2de1361ff865d756.gif]: /images/20221022/4c516cf0e74f42288d79cd147ee90530.png
[2f74fd3e4fdcc79710b20e3677eb5094.gif]: /images/20221022/3efa0933ebb149318fb099fb6cec8d5b.png
[aa1001450f1eb3c055efc55586ddcdee.gif]: /images/20221022/d3cf3d3f70484f84b5d100ce8d23fc21.png
[bc7297fbe74014512f7332378eebd88d.gif]: /images/20221022/e81033489c8149e99beddb032d992588.png
[edae0cd410b31b17dcb864dd6d0d467c.png]: /images/20221022/8c7208c4bdce4b26bcc2653935c9263d.png
[45c9b58d0d36f79b07f1bc95cb634c7c.gif]: /images/20221022/85c06444a3f443e697287ddd4ae1a683.png
[f1b15a280bff855107dea3d43913acb5.gif]: /images/20221022/f7f70fa3472348158fcca96ff314e0e9.png
[f1d450e2a2924a84444f96fd18b07880.gif]: /images/20221022/dca6a94119b046d798efe9bfd94c3d16.png
[e13b375220e2af09efb0240f8b8cfbde.gif]: /images/20221022/49399f76759d461dbf3594ee598bb371.png
[b3c34c67f8e91f061e491f494c223baf.gif]: /images/20221022/5279a488dc0d4448937a8323fd0aa14f.png
[14f7ef44eb73b8d501900745a0133099.gif]: /images/20221022/69932156dfaf430a8128acff31e18c76.png
[d5973be05b555dc926ae2af1661c8785.gif]: /images/20221022/a8d96c4cbbea4929bf015f2a506d5b8f.png
[ce37774d032f4cc7599946c4288eb642.gif]: /images/20221022/a16a64a8b0024a6ca966e83e40a40d35.png
[b29d74d5fc868ba931e11cb036718ec3.gif]: /images/20221022/c70810d27c304ca98567a679590cd38d.png
[52898f6ea7751c009c53ece1c3ca49b0.gif]: /images/20221022/0b8834d6e0dd4ec5a75bb47d349084eb.png
[bd6d8fed364e14430170cd210234adeb.gif]: /images/20221022/247aec2220ad4569908976279db8fdcf.png
[7502e125cb4911ecf0b0b09d517fd8b9.gif]: /images/20221022/5a56cdc3835a496cb57294cb1e425c41.png
[16748d7e6df9bef4af57349b31ff5eb2.gif]: /images/20221022/e829fbc1291b47ca8c11ce5852fa2055.png
[3cdb5ef1d49fb04b889972746de76fe4.gif]: /images/20221022/5465ba97628947c7948da022362ba994.png
[27b9fdb6707da0c1099bf17feb4a79fb.gif]: /images/20221022/c77d4f4a1ee640bf8204b4ad3e7de15b.png
[c596089dd652cc4b30cf13ebc921b72d.gif]: /images/20221022/0c4f9ae082334026b337b4f174ab7a61.png
[f42c26169586bfaf5225cfcfea88ec5c.gif]: /images/20221022/a891394500df403eb9f5cdbe05af992e.png
[0c9d62a716a350994aa12dff1125b818.gif]: /images/20221022/3c514ff48382421db29ca3ee78ceee7e.png
[d41ea129075366230a9380ffbd6858f4.gif]: /images/20221022/a428eb5018794b789b2bf19e4e6bb685.png
[dd66470743a1e095709633944df98e7e.gif]: /images/20221022/0eac3d58ea0647a68c0310bcdf2e8160.png
[59528b7a48281efdb5bb670836676fc2.gif]: /images/20221022/a3e1e48c6b754a4ca579c98ec104abcd.png
[3bbfff68fb4681abc50d6d19fdad6945.gif]: /images/20221022/f65cbe490d7f42a3a86056cdb7682e09.png
[e349f3d85e9cd4c9d133f5934855fa96.gif]: /images/20221022/b8ebd75a17114c61a8ae40256299ef20.png
[dbdedb377a2227b78de0c0b336086f3d.gif]: /images/20221022/8cbab9786b5a4063a8537b63c22aa91b.png
[6d8ed76d74362920a4294fe09c9d78df.gif]: /images/20221022/ae330b56ef8e459cb50db2624cc3568c.png
[7d4528ee4052536eaeb215bab73827f0.gif]: /images/20221022/46c99b12498d49429f1891ca24feb9a3.png
[8ff797a66b6d083f75f3fa41857acf0b.png]: /images/20221022/4fc731aa58694e23ab6e800ca7acbb28.png
[e815c978dc134579f8311280a05c8410.gif]: /images/20221022/95248884044a4169b4a549ff4cde6671.png
[dea4e67b7c9e217a2d8e821b5d45a757.gif]: /images/20221022/9d06091cb4c942dfa7e7134bd034a5e4.png
[6001ecef4db0c5729b2b6de88f5c5496.png]: /images/20221022/415845cd2bb14b7991b0f31383bf176f.png
[25d2af87f5962152a7db309081ba1cf9.png]: /images/20221022/e377298728ae4aee979a49c9ee787a94.png
[61245274a524c53ccd1d6fd4d7950f59.png]: /images/20221022/b46d33a99f6d4cbcb8cdcaf202769d8e.png
[_Python]: https://item.jd.com/13143016.html
[ecd632aef92e62caa7b305ef6d53f08e.png]: /images/20221022/4b07b904567d4668ac0f994b78843a25.png