第 1 章 预备知识

第 1 章 预备知识

计算机科学并非一门研究机器的学科,如同天文学并非研究望远镜一样。从本质上讲,数学与计算机科学具有统一性。

——艾兹赫尔 • 戴克斯特拉1

1艾兹赫尔 • 戴克斯特拉(Edsger Dijkstra,1930—2002),荷兰计算机科学家,其贡献涵盖编译器、操作系统、分布式系统、软件工程、编程语言、图论等多个领域,数据结构中的最短路径算法——戴克斯特拉算法就是以他的名字命名的。1972 年,戴克斯特拉因在编程语言方面的贡献而获得图灵奖。——译者注

计算机只能处理分解成块的问题,因此我们需要具备一定的数学知识。不过无须紧张,数学并非高深莫测,编写优秀的代码也很少要用到复杂的方程。这一章将介绍求解问题所需的基本知识,包括:

采用流程图与伪代码对想法进行建模

根据逻辑判断对错

对事物进行计数

安全地计算概率

掌握这些知识后,我们就能将自己的想法转换为可供计算机执行的解决方案。

1.1 想法

面对复杂的问题时,请让大脑保持最佳状态,将所有重要内容写下来。我们的大脑很容易被各种事实和想法所淹没,“好记性不如烂笔头”在众多组织方法中占有重要地位。为此,这一节将讨论几种实现方法。首先介绍用于表示进程的流程图,然后利用伪代码编写可供实际编程使用的进程,并尝试通过数学工具对一个简单的问题进行建模。

1.1.1 流程图

在讨论相互之间的协作过程时,维基人 2 创建了一种随着讨论的进行而更新的流程图。对所提出的内容了然于心有助于讨论。

2维基人指在维基百科上编写条目的贡献者,女性维基人有时候也被称为“薇姬人”。——译者注

图 1-1 维基百科编辑流程

与上面的编辑流程类似,计算机代码本质上是一种进程。程序员通常使用流程图来编写计算进程。为便于他人理解,绘制流程图时应遵循以下原则 3

3国际标准化组织甚至专门制定了一项称为 UML(统一建模语言)的标准来定义软件系统图的绘制。

  • 将状态步骤和指令步骤置于矩形框内;
  • 将决策步骤(对给定的条件进行判断)置于菱形框内;
  • 不要将指令步骤与决策步骤放在一起;
  • 使用箭头连接各个顺序步骤;
  • 标明进程的开始和结束。

我们以查找 3 个数中的最大值为例,来看看如何绘制流程图。

图 1-2 查找 3 个变量中的最大值

1.1.2 伪代码

与流程图类似,伪代码也可以用来表示计算进程。它是一种符合人类阅读习惯的代码,但无法被机器理解。下面这个示例与图 1-2 的含义相同,读者不妨花些时间,选取若干样本值作为 A、B、C 尝试一下。4

4在本例中,←表示赋值运算符。因此,x ← 1 的含义是“将 x 设置为 1”。

function maximum(A, B, C)
    if A > B
        if A > C
            max ← A
        else
            max ← C
    else
        if B > C
            max ← B
        else
            max ← C
    print max

读者是否注意到,上述代码完全没有遵循编程语言的语法规则?我们甚至可以在伪代码中使用某些口语!如同利用流程图绘制一般性思维导图那样,就让我们的创造力在编写伪代码时得到充分释放吧(如图 1-3 所示)!

图 1-3 “现实生活中的伪代码”(取自 http://ctp200.com

1.1.3 数学模型

模型是一组表示问题及其特征的概念,有助于更好地推断与处理问题。创建模型的重要性毋庸置疑,我们从小就受过这方面的训练。中学数学的思路是(或应该是)将问题建模为若干数字和方程,然后应用各种工具进行求解。

采用数学语言描述的模型具有一个无可比拟的优势:它们能在使用完备数学工具的计算机上运行。如果模型中包含图,可以使用图论;如果包含方程,代数将派上用场。利用前人创造的这些工具,问题就能迎刃而解。接下来,我们讨论一个经常在中学数学中出现的问题。

家畜围栏  农场里饲养了两种家畜。我们利用 100 个单位长度的铁丝网制作一个矩形围栏,中间用直线将两种动物隔开。那么应该如何设计围栏,才能让牧场的面积最大化?

我们从需要求解的值入手分析。如果 wl 为牧场的边长,那么二者的乘积就是牧场的面积。面积最大化意味着使用所有铁丝网,因此 wl 与 100 之间具有以下关系。

\begin{aligned}A&=w\times l\\100&=2w+3l\end{aligned}

现在,问题变成了 wl 取何值,才能使面积 A 最大。

{%}

根据第二个方程求出 ll=\frac{100-2w}{3} ),然后代入第一个方程:

A=\frac{100}{3}w-\frac{2}{3}w^2

由此得到一个二次方程,利用中学时学过的二次公式很容易就能求出它的最大值。设 A=0 并求解方程,最大值为两个根之间的中点。二次方程之于我们,如同高压锅之于厨师,两种工具的共同点是可以节省时间。二次方程能加快许多问题的求解速度,而我们的任务就是解决问题,这一点请谨记在心。厨师需要了解他的工具,我们同样需要掌握自己的工具,数学模型就是我们手中的有力工具。除此之外,逻辑也是解决问题的法宝。

1.2 逻辑

程序员与逻辑打交道太频繁,思维都被逻辑搞得一团糟。尽管如此,不少程序员其实并未真正掌握逻辑的知识,只是凭借“本能”在使用它。理解形式逻辑的概念之后,我们就可以用它来审慎地解决问题。

图 1-4 “程序员的逻辑”(取自 http://programmers.life

在这一节,我们首先采用特殊的运算符和代数来处理逻辑陈述,然后学习利用真值表解决问题,并探讨计算机是如何依靠逻辑来工作的。

1.2.1 运算符

普通数学使用变量与运算符(+、-、×等)对数值问题进行建模。在数理逻辑中,变量与运算符表示事物的有效性,它们代表的是真(True)或假(False)而非数字。例如,表达式“如果泳池很暖和,我就去游泳”的有效性基于两件事的有效性,二者可以被映射到逻辑变量 AB

 A :泳池很暖和。
B :我去游泳。

AB 要么为 True,要么为 False5A= True 表示“泳池很暖和”,B= False 表示“我不去游泳”。B 不可能为半真,因为“我”不可能一半去游泳,一半不去游泳。变量之间的依赖关系通过条件运算符→表示,A\to B 意味着“当 A= True 时,B= True”。

5在模糊逻辑中,值也可以介于两者之间,但本书不会涉及这方面的内容。

A\to B:如果泳池很暖和,我就去游泳。

借由其他运算符,我们能表示更多的含义。例如,取反运算符 ! 表示否定,!A 的含义是对 A 取反。

!A:泳池很凉。
 !B:我不去游泳。

换质位法 当给定“A\to B”与“我不去游泳”时,能否推断出泳池的情况呢?由于“泳池很暖和”会强制“我去游泳”,如果“我不去游泳”,就说明“泳池不暖和”。每个条件表达式都有相应的换质位形式。

对于任意两个变量 ABA\to B!B\to~!A 的含义相同。

我们再来看一个例子。“如果你写不出好代码,那么还没有读过本书”的换质位形式为“如果你读过本书,就能写出好代码”。换言之,两句话采用不同的方式表达了相同的意思。6

6其实,这两句话说得一点也没错。

双条件 请注意,“如果泳池很暖和,我就去游泳”不代表“我只在温水中游泳”,这一陈述并未对泳池冷暖做出承诺。也就是说,A\to B 不意味着 B\to A 。如果希望两个条件都成立,需要使用双条件

A\leftrightarrow B:当且仅当泳池很暖和,我才去游泳。

此时,“泳池很暖和”和“我才去游泳”是等价的:只要了解泳池的冷暖,就能了解是否去游泳,反之亦然。需要再次强调的是,应谨防反向错误,不要认为从 A\to B 可以推断出 B\to A

逻辑与、逻辑或、逻辑异或 三者通常是显式编码的,它们是最知名的逻辑运算符。逻辑与(AND)表示全部条件为真时结果为真,逻辑或(OR)表示任意条件为真时结果为真,逻辑异或(XOR)表示条件相反时结果为真。考虑一个提供伏特加与葡萄酒的聚会。

读者应掌握目前介绍的各种运算符的工作原理。表 1-1 列出了两个变量所有可能的组合。请注意,A\to B 等价于 !A~{\rm OR}~B,而 A~{\rm XOR}~B 等价于 !(A\leftrightarrow B)

表 1-1 逻辑运算:AB 的 4 种可能情况

1.2.2 布尔代数

与初等代数可以化简数值表达式类似,布尔代数 7 可以化简逻辑表达式。

7得名于英国数学家乔治 • 布尔(1815—1864)。他在 1854 年出版的著作中引入了逻辑学与数学,布尔代数由此诞生。

结合律 括号不影响 AND 或 OR 运算的顺序。与初等代数中的求和与乘法运算类似,可以采用任意顺序进行计算。

\begin{aligned}A~{\rm AND}~(B~{\rm AND}~C)&=(A~{\rm AND}~B){\rm AND}~C\\A~{\rm OR}(B~{\rm OR}~C)&=(A~{\rm OR}~B){\rm OR}~C\end{aligned}

分配律 在初等代数中,我们可以将乘法项从和中提取出来:a\times(b+c)=(a\times b)+(a\times c)。逻辑运算与之类似,两个变量进行 OR 运算后再与第三个变量进行 AND 运算,相当于两个变量分别与第三个变量进行 AND 运算后再进行 OR 运算,反之亦然。

\begin{aligned}A~{\rm AND}~(B~{\rm OR}~C)&=(A~{\rm AND}~B)~{\rm OR}~(A~{\rm AND}~C)\\A~{\rm OR}~(B~{\rm AND}~C)&=(A~{\rm OR}~B)~{\rm AND}~(A~{\rm OR}~C)\end{aligned}

德摩根定律 8 夏天冬天不可能同时出现,因此要么不是夏天,要么不是冬天。当且仅当不满足要么是夏天要么是冬天的条件时,说明既不是夏天,也不是冬天。根据上述推理,可以将 AND 运算转换为 OR 运算,反之亦然。

8德摩根(1806—1871)是布尔的好友。他曾辅导过年轻的埃达 • 洛夫莱斯——历史上首位程序员,比第一台计算机问世还早一个世纪。

\begin{aligned}&!(A~{\rm AND}~B)=!A~{\rm OR}~!B\\&!A~{\rm AND}~!B=!(A~{\rm OR}~B)\end{aligned}

利用上述规则可以转换逻辑模型、揭示属性并化简表达式。接下来,我们考虑如何解决以下问题。

过热的服务器 如果服务器过热且空调关闭,会导致服务器崩溃;如果服务器过热且机箱冷却器失效,同样会导致服务器崩溃。那么服务器需要满足哪些条件才能正常工作?

利用逻辑变量对问题建模,服务器崩溃的条件可以用一个表达式来表示。

A :服务器过热。

B :空调关闭。

C :机箱冷却器失效。

D :服务器崩溃。

(A~{\rm AND}~B)~{\rm OR}~(A~{\rm AND}~C)\to D

采用分配律对上式进行因式分解:

A~{\rm AND}~(B~{\rm OR}~C)\to D

当满足条件 !D 时,服务器可以正常工作。相应的换质位形式为:

!D\to!(A~{\rm AND}~(B~{\rm OR}~C))

采用德摩根定律去除括号:

!D\to!A~{\rm OR}~!(B~{\rm OR}~C)

然后再次应用德摩根定律:

!D\to!A~{\rm OR}~(!B~{\rm AND}~!C)

从上式可知,只要满足条件 !A(服务器没有过热)或 !B~{\rm AND}~!C(空调机箱冷却器均正常工作),服务器就能正常工作。

1.2.3 真值表

分析逻辑模型的另一种方法是检查所有可能的变量组合。真值表采用列表示变量,行表示变量状态的可能组合。

每个变量需要两行,变量在一行中设置为 True,在另一行中设置为 False。如果需要增加变量,则对行进行复制,并在原来的行中将新变量设置为 True,在复制的行中将新变量设置为 False(如图 1-5 所示)。每增加一个变量,真值表的大小将增加一倍,因此只能为少量变量构建真值表。9

9一张由 30 个变量构成的真值表,所包含的行数将超过 10 亿。(即对于 n 个变量(n\geqslant 1),真值表包含 2^n 行。——译者注)

图 1-5 由 1 到 5 个逻辑变量构成的真值表,包括所有可能的变量组合

接下来讨论如何利用真值表分析问题。

脆弱的系统  我们需要创建一个满足以下要求的数据库系统。

I:如果数据库锁定,则可以保存数据。

II:不会出现写队列已满且数据库锁定的情况。

III:要么写队列已满,要么缓存已加载。

IV:如果缓存已加载,则无法锁定数据库。

是否可以创建满足上述要求的数据库系统?它需要满足哪些条件才能工作?

首先,我们将每项要求转换为一个逻辑表达式。可以使用 4 个变量对数据库系统建模。

接下来,我们根据所有可能的组合创建真值表。为检查是否满足上述要求,真值表添加了额外的列。

表 1-2 真值表:探索 4 个表达式的有效性

可以看到,在状态 2 到 4 以及状态 6 到 8 中,所有要求均得到满足。在这些状态中,A= False,表示数据库永远不会锁定。只有在状态 3 和状态 7 中,缓存不会加载。

为检验所学的知识,请读者尝试解答斑马难题 10。这是一个著名的逻辑问题,但并非由爱因斯坦提出。据说只有 2% 的人能解决这个问题,不过我对此表示怀疑。使用一张较大的真值表,并采用正确的方式化简与合并逻辑陈述,相信读者会找出答案。

10参见 https://code.energy/solving-zebra-puzzle/

每当处理假定为两种可能性之一的问题时,可以采用逻辑变量对其进行建模,借此不难推导出表达式并进行化简,进而得出结论。接下来,开始讨论最令人印象深刻的逻辑应用——电子计算机设计。

1.2.4 逻辑在计算中的应用

一组逻辑变量可以表示二进制形式的数字 11,针对二进制数字的逻辑运算也可以合并以执行一般性计算。逻辑门对电流执行逻辑运算,电路中使用的逻辑门能以极高的速度进行计算。

11True = 1,False = 0。如果读者不清楚为何二进制数 101 表示十进制数 5,请参考附录中有关数制的解释。

逻辑门从输入线接收值并进行运算,然后将结果置于输出线。逻辑门包括与门(AND)、或门(OR)、异或门(XOR)等多个种类,高低电平分别代表 TrueFalse。借由逻辑门,复杂逻辑表达式的计算几乎可以在瞬时完成。例如,图 1-6 所示的电路用于对两数求和。

图 1-6 对两个逻辑变量(A_1A_0B_1B_0)给出的 2 位数字求和,结果是一个 3 位数字(S_2S_1S_0

请读者思考上述电路的工作原理,并花些时间观察电路的计算过程(图 1-7)。

图 1-7 计算 2 + 3 = 5(二进制为 10 + 11 = 101)

为利用这种快速的计算形式,我们将数值问题转换为相应的二进制或逻辑形式。真值表有助于电路的建模与测试。布尔代数可以化简表达式,电路也因此得以简化。

逻辑门最初采用笨重、低效且昂贵的电动阀制造。在晶体管取代电动阀之后,逻辑门实现了批量生产,人们也一直在探索缩小晶体管尺寸的途径。12 现代 CPU 的工作原理仍然以布尔代数为基础。从本质上说,现代 CPU 只是一种由数以百万计的微观导线与逻辑门构成的电路,用于对信息电流进行操作。

122016 年,研究人员制造出 1 纳米级别的晶体管。金原子的直径为 0.15 纳米。

1.3 计数

正确计数至关重要。在处理与计算有关的问题时,必须多次执行计数操作。13 本节涉及的数学知识较前几节更为复杂,但读者无须紧张。有些人认为自己不擅长数学,因此难以成为一名优秀的程序员。事实也不尽然——我的高中数学考试没有及格,后来也拿到了计算机科学的硕士学位。成为一名优秀程序员所需的数学,与一般的数学考试有所不同。

13计数逻辑属于离散数学,它是计算机科学的一个重要领域。

毕业之后,所学的各种公式与逐步推导过程都会逐渐遗忘,需要时在因特网上进行搜索即可。计算并非必须依靠笔和纸才能进行,直觉对于优秀的程序员而言必不可少,学习计数问题将进一步增强这种直觉。接下来将逐一讨论乘法、排列、组合、求和等一系列数学工具。

1.3.1 乘法

如果一个事件以 n 种不同的方式发生,另一个事件以 m 种不同的方式发生,那么两个事件可能以 n\times m 种不同的方式发生。举例如下。

密码破译  PIN 码由两个数字与一个字母组成,每次需要 1 秒的时间进行输入。在最坏的情况下,需要多久才能破译 PIN 码?

两个数字有 100 种搭配方式(00 到 99),一个字母有 26 种搭配方式(A 到 Z),因此共有 100×26 = 2600 种可能的 PIN 码。在最坏的情况下,我们必须尝试每一个 PIN 码,直至找出正确的密码。换言之,需要花费 2600 秒(43 分钟)才能破译密码。

团队建设  有 23 名候选者希望加入你的团队,你采用抛硬币的方式决定是否录用他们。对于每个候选者,如果抛出的硬币正面朝上,则录用他。那么一共存在多少种可能的团队配置?

录用他们之前,唯一的团队配置就是你自己一人;每次抛出硬币后,可能的配置数量将增加一倍。由于必须进行 23 次抛硬币操作,团队配置的数量为 2 的 23 次方

请注意,其中一种配置仍然是你自己。

1.3.2 排列

对于 n 个项,存在 n 的阶乘(n!)种排序方式。阶乘呈爆炸性增长,即便是很小的 n 值,阶乘的结果也相当惊人。如果读者不熟悉阶乘,这里给出其定义如下:

n!=n\times(n-1)\times(n-2)\times\cdots\times2\times1

不难看出,n 个项共有 n! 种排序方式。那么在 n 个项中,选择第一项有多少种方式?选择第一项之后,选择第二项有多少种方式?选择第二项之后,选择第三项有多少种方式?请读者思考这个问题,之后我们将讨论更多的示例。14

14根据惯例,0! = 1,即对 0 个项进行排序,存在一种方式。

旅行推销员  卡车公司为 15 座城市送货,我们希望了解哪种路线安排可以最大限度减少耗油量。如果计算一条路线的长度需要 1 毫秒,那么计算所有可能路线的长度需要多久?

15 座城市的每种排列都是一条不同的路线。阶乘是不同排列的数量,因此共有 15! = 15×14×…×1 ≈ 1.3 万亿条路线。由此可知,需要 1.3 万亿毫秒(约 15 天)才能计算出所有路线的长度。如果城市的数量增加到 20 座,则需要 7.7 万年才能完成计算。

珍贵的曲调  一位音乐家正在研究一种包括 13 个不同音符的音阶,她希望你找出所有仅使用 6 个音符的旋律。每个音符在每种旋律中都要播放一次,每种使用 6 个音符的旋律需要 1 秒钟进行播放。那么播放这位音乐家所要求的全部旋律需要多久?

在 13 个音符中,我们需要计算其中 6 个音符的排列。为忽略未使用音符的排列,必须在第 6 个因子后停止阶乘计算。形式上,\frac{n!}{(n-m)!}n 个可能项中 m 种可能排列的数量。在本例中:

可以看到,共有超过 120 万种播放时间为 1 秒的旋律。换言之,需要 343 个小时才能将所有旋律听完——最好说服音乐家通过其他方式寻找完美的旋律。

1.3.3 具有相同项的排列

如果某些项相同,那么对 n 个项而言,排序方式的数量要少于 n! 种。交换位置的相同项不应被计作不同的排列。

在一个包含 n 个项的序列中,如果有 r 个项相同,则存在 r! 种重新排序相同项的方式。因此,n! 将对每个不同的排列进行 r! 次计数。为获取不同排列的数量,需要将 n!r! 相除。以字母“”为例,不同排列的数量为 10!/3! 种。

DNA 研究  一位生物学家正在研究一种与遗传疾病有关的 DNA 片段。它由 23 个碱基对构成,其中 9 个必须为 A-T,另外 14 个必须为 G-C。这位生物学家希望为所有具有这些碱基对数目的 DNA 片段运行模拟任务,那么所需的模拟任务总数是多少?

我们首先计算 23 个碱基对所有可能的排列,然后将结果与 9 个重复的 A-T 以及 14 个重复的 G-C 碱基对相除,从而得到碱基对排列的数量:

\frac{23!}{(9!\times14!)}=817~190

但问题尚未结束。如果将碱基对的取向考虑在内,就会得到下图所示结果。

对于每一个 23 个碱基对的序列,存在 2^{23} 种不同的取向构型,因此序列总数为:

这只是一个已知分布的 23 个微小碱基对序列。迄今为止,最小的可复制 DNA 来自猪圆环病毒,包括 1800 个碱基对!从技术角度看,DNA 编码与生命确实令人叹为观止。一个难以置信的事实是,人类 DNA 约有 30 亿个碱基对,在人体的 3 万亿个细胞中复制。

1.3.4 组合

请读者想象一副包含所有黑桃花色的扑克牌 (共 13 张),那么向对手发 6 张牌有多少种方式?在 13 个可能项中找出 6 种排列,其数量为 \frac{13!}{(13-6)!} 种。由于 6 张牌的顺序无关紧要,我们必须将结果与 6! 相除,从而得到符合要求的组合数量。

\frac{13!}{6!(13-6)!}=1716

二项式 {n\choose m} 表示从一组 n 个项中选择 m 个项的方式的数量(不考虑顺序):

{n\choose m}=\frac{n!}{m!(n-m)!}

上述二项式读作“nm”。

皇后问题  有一副空棋盘以及 8 个后,后可以放在棋盘的任何位置,那么后共有多少种不同的放置方式?

国际象棋棋盘由 64 个(8×8 方格的网格)组成。从 64 个可用的方格中选择 8 个,共有 {64\choose8}\approx44 亿种方式。

1.3.5 求和

计数时经常需要对序列求和,序列和采用求和符号(∑)表示。在表达式中对 i 的每个值求和表示为:

例如,对前 5 个奇数求和可以写作:

\sum^4_{i=0}(2i+1)=1+3+5+7+9

采用 0、1、2、3、4 替换 i ,从而得到 1、3、5、7、9。类似地,对前 n 个自然数求和可以写作:

\sum^n_{i=1}i=1+2+\cdots+(n-1)+n

天才数学家高斯在 10 岁时,老师曾要求他对自然数求和。高斯没有采用逐一相加的方法,而是发现了一个巧妙的诀窍:

\sum^n_{i=1}i=\frac{n(n+1)}{2}

读者能猜出高斯是如何发现上述公式的吗?相关解释请参见附录。接下来,我们讨论如何利用它来解决实际问题。

廉价机票  你需要在今后 30 天内随时飞往纽约,而机票价格会根据出发日期与返程日期发生无法预测的变化。那么必须查看多少对出发 / 返程日期,才能找到今后 30 天内往返纽约的最便宜的机票?

只要返程日期与出发日期为同一天或晚于出发日期,那么从今天(第 1 天)到最后一天(第 30 天)之间的任何出发 / 返程日期都是有效的。因此,第 1 天有 30 对有效的出发 / 返程日期,第 2 天有 29 对,第 3 天有 28 对,以此类推,第 30 天只有一对有效的出发 / 返程日期。换言之,总共需要考虑 30+29+…+2+1 对出发 / 返程日期。我们可以将其写作 ?i ,并利用高斯发现的诀窍计算它的值。

也可以利用组合来解决这个问题。从 30 天中选择两天,顺序无关紧要:较早的一天作为出发日期,较晚的一天作为返程日期,由此可得 {30\choose2}=435。请注意,必须将出发日期与返程日期为同一天的情况考虑在内。这样的组合共有 30 种,因此出发 / 返程日期的总数为 {30\choose2}+30=465 对。

1.4 概率

随机性原则有助于我们理解博彩、预报天气或设计低风险的备份系统。这些原则并不复杂,却被大多数人所误解。

图 1-8 “随机数”(取自 http://xkcd.com

我们首先利用计数来计算赔率,然后学习如何使用不同的事件类型来解决问题,最后解释赌徒为何会输得精光。

1.4.1 对结果计数

一个骰子可以掷出 6 种可能的结果,即点数 1、2、3、4、5、6。因此,掷出点数 4 的概率为 1/6。那么掷出奇数点数的概率又如何呢?由于奇数点数有 3 个(点数 1、3、5),所以概率为 3/6 = 1/2。形式上,一个事件发生的概率为:

如果骰子的平衡性良好且投掷者没有作弊,则每种可能的结果发生的概率相同,上述表达式成立。

团队建设(续)  有 23 名候选者希望加入你的团队,你采用抛硬币的方式决定是否录用他们。对于每个候选者,如果抛出的硬币正面朝上,则录用他。那么没有录用任何候选者的概率有多大?

之前的示例曾经讨论过,共有 2^{23}=8~388~608 种可能的团队配置。没有录用任何候选者的唯一方式是抛出的硬币连续 23 次正面朝下,因此这种情况发生的概率是 P ( 无人录用 )=1/(8 388 608)——客观地说,商业航班失事的概率约为五百万分之一。

1.4.2 独立事件

抛硬币与掷骰子时,硬币正面朝上与掷出点数 6 的概率为 1/2×1/6 = 1/12 ≈ 0.08,即 8%。如果一个事件的结果不会对另一个事件的结果产生影响,则称二者相互独立。两个独立事件发生的概率是它们各自概率的乘积。

数据备份  我们需要将数据保存一年。一种磁盘损坏的概率是十亿分之一,另一种磁盘的价格只有前者的 20%,但损坏的概率为两千分之一。那么应该选择昂贵的磁盘还是便宜的磁盘?

如果使用 3 张便宜的磁盘,那么仅当所有磁盘都损坏时才会丢失数据。这种情况发生的概率为 (1/2000)^3=1/8~000~000~000。与昂贵的磁盘相比,3 张便宜磁盘提供的高冗余度能降低数据丢失的风险,而价格只有昂贵磁盘的 60%。

1.4.3 互斥事件

骰子不可能同时掷出点数 4 与某个奇数点数。因此,要么掷出点数 4 要么掷出某个奇数点数的概率为 1/6+1/2 = 2/3。如果两个事件不可能同时发生,则称二者互斥。如果希望任一互斥事件发生,将它们各自的概率相加即可。

订阅选项  网站提供免费、基本、高级等 3 种订阅计划。已知一名随机的新用户有 70% 的概率选择免费计划,20% 的概率选择基本计划,10% 的概率选择高级计划。那么新用户注册付费计划的可能性有多大?

在本例中,事件是互斥的,即用户无法同时选择基本计划高级计划。用户付费的概率为 0.2 + 0.1 = 0.3。

1.4.4 对立事件

骰子不可能同时掷出点数 3 的倍数(点数 3 和 6)与无法被 3 整除的点数,但必然会掷出其中之一。由于掷出点数 3 的倍数的概率为 2/6 = 1/3,掷出无法被 3 整除的点数的概率为 1-1/3 = 2/3。如果两个互斥事件涵盖所有可能的结果,则称二者对立。因此,对立事件的概率之和为 100%。

塔防游戏  城堡由 5 座炮塔保护,每座炮塔有 20% 的概率在入侵者到达城堡前消灭它们。那么消灭入侵者的概率有多大?

读者是否认为炮塔击中入侵者的概率为 0.2 + 0.2 + 0.2 + 0.2 + 0.2 = 1(或 100%)?!不要将各个独立事件的概率相加,这是一个常见的错误。本例需要应用两次对立事件。

  • 20% 的命中概率与 80% 的未命中概率互为对立事件,因此所有炮塔均未命中的概率为 0.8^5\approx0.33
  • 事件“所有炮塔均未命中”与“至少有一座炮塔命中”互为对立事件,因此消灭入侵者的概率为 1-0.33 = 0.67。

1.4.5 赌徒谬误

如果将一枚普通的硬币向上抛 10 次,且 10 次均为正面朝上,那么在第 11 次抛出硬币时,是否正面朝下的概率更大一些呢?再者,购买彩票时选择数字 1 到 6,是否比选择均匀间隔的数字更不容易赢呢?

请记住,不要成为赌徒谬误的受害者。过去的事件永远不会影响独立事件的结果——永远不会。在真正的随机彩票抽奖中,选择任何指定数字获奖的概率与选择其他数字完全相同。不存在所谓的“潜规则”,使得之前不经常选择的数字在今后会被更频繁地选择。

1.4.6 高级概率

概率涉及的内容相当广泛,本节的介绍难免挂一漏万。在处理复杂问题时,务必记得寻找更多工具。举例如下。

团队建设(再续)  有 23 名候选者希望加入你的团队,你采用抛硬币的方式决定是否录用他们。对于每个候选者,如果抛出的硬币正面朝上,则录用他。那么录用 7 名或更少候选者的概率有多大?

没错,这个问题并不简单。利用 Google 进行搜索,最终将引至“二项分布”。读者可以在 Wolfram Alpha 中输入“B(23,1/2) ≤ 7”来观察结果。

1.5 小结

这一章讨论了与求解问题密切相关的一些知识,但并未涉及任何实际的程序代码。1.1 节解释了将重要内容写下来的原因和方法。我们为需要解决的问题建模,并将概念工具应用于所创建的模型中。1.2 节讨论了布尔代数、真值表等处理逻辑问题所需的工具。

1.3 节讨论了计数,它在计算各种问题的可能性与配置时发挥了重要作用。快速进行粗略估算有助于判断计算是否可行,刚入行的程序员往往会浪费时间分析太多的情况。1.4 节解释了概率计算的基本规则。在这个美妙但不确定的世界中,概率对于解决问题至关重要。

在此基础上,我们简要介绍了学术界称为离散数学的许多重要知识点。读者可以从下面列出的参考资料或维基百科中找到更多有趣的定理。例如,根据“鸽巢原理”,不难证明纽约至少有两个人的头发数量一样多。

这一章讨论的部分内容与第 2 章密切相关。第 2 章将介绍计算机科学中最重要的概念——复杂度。

参考资料

  • 《离散数学及其应用(第 7 版)》,Kenneth H. Rosen 著
  • 周以真教授关于计算思维的幻灯片

目录