算法：程序员的数学读书笔记

0的故事

一、按位计数法

二、不使用按位计数法的罗马数字

三、十进制转二进制

四、0所起到的作用

逻辑

一、为何逻辑如此重要

二、兼顾完整性和排他性

三、逻辑

四、德摩根定律

五、真值表

六、文氏图

七、卡诺图

八、逻辑表达式

余数

一、余数

二、余数性质

三、更多思考题

四、奇偶校验

五、总结

数学归纳法

一、简介

二、说明

三、定义

排列组合

一、计数

二、计数方法

三、排列组合

递归

一、开头

二、汉诺塔

三、阶乘

四、斐波那契数列（Fibonacci sequence）

五、分形图（fractale）

指数爆炸

一、指数爆炸

二、倍数游戏

三、二分法查找

四、对数

五、如何处理指数爆炸

六、总结

0的故事

——无即是有

一、按位计数法

生活中常见的计数法：

10进制计数法：十进制计数法是世界各国常用的一种记数方法。也是我们从小学就开始学习的计数法。常说“满十进一”，这种以“十”为基数的进位制，叫做十进制。
2进制计数法：一打啤酒是12瓶，每12瓶就是一打，这个就叫做十二进制。
16进制计数法：“半斤八两”一词是个常用成语，很多人却忘了我们中国所用的称重单位斤和两，一斤=16两，每满16两是一斤，这就叫做十六进制。

编程中常见的计数法：

2进制计数法：二进位计数制仅用两个数码。0和1，所以，任何具有二个不同稳定状态的元件都可用来表示数的某一位。而在实际上具有两种明显稳定状态的元件很多。
8进制计数法：使用的数字有0、1、2、3、4、5、6、7共 8种。80的位、81的位、82的位、83的位……（基数是8）
16进制计数法：使用的数字有0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F共 16种。160的位、161的位、162的位、163的位……（基数是16）在16进制计数法中，使用 A、B、C、D、E、F（有时也使用小写字母 a、b、c、d、e、f）来表示 10以上的数字。

二、不使用按位计数法的罗马数字

罗马计数法的特征如下：

数位没有意义，只表示数字本身。
没有0。
使用 I (1)、 v (5)、 X (10)、 L (50)、 C (100)、 D (500)、 M (1000）来记数。
将并排的数字加起来，就是所表示的数。

例如，3个并排的1( I ）表示3，并排的 V 和 I ( VI ）表示6, VII 表示8。
罗马数字的加法很简单，只要将罗马数字并排写就可以得到它们的和。比如，要计算+2，只要将表示1的 I 和表示2的 I 并排写作皿就行了。但是，数字多了可就不太简单了。

思考：为什么十二写成10而不是102？

$N = a_{n}b^{n} + a_{n-1}b^{n-1} + ... + a_{1}b + a_{0}$

0～15不同按位计数法表示：

二进制	八进制	十进制	十六进制
0	0	0	0
1	1	1	1
10	2	2	2
11	3	3	3
100	4	4	4
101	5	5	5
110	6	6	6
111	7	7	7
1000	10	8	8
1001	11	9	9
1010	12	10	A
1011	13	11	B
1100	14	12	C
1101	15	13	D
1110	16	14	E
1111	17	15	F

三、十进制转二进制

除二取余

四、0所起到的作用

0的作用：站位

在按位计数法中，数位具有很重要的意义。即使十位的数字“没有”，也不能不写数字。这时就轮到0出场了，即0的作用就是占位。换言之，0站着一个位置以保证数位高于它的数字不会产生错位。

0的作用：统一标准，简化规则

“0次方”，还将1特意表示成10的0次幂，能够将按位计数法的各个位数所对应的大小统一表示成10的n次幂。计算机中，计数也是从0开始。

日常生活中的0

日常生活中0表示“无”或“没有”。

逻辑

——真与假的二元世界

一、为何逻辑如此重要

逻辑是消除歧义的工具：

我们平时使用的语言——自然语言，是极易产生歧义的。就连“或者”一词，也不是只有一个正确意义。然而，规格说明书（记述如何编写程序文件）一般都是用自然语言描述的。因此，程序员必须走出自然语言歧义的迷宫，谨慎解读规格说明书，确定其正确的意义。“逻辑”，是消除自然语言歧义、严密准确地记还事物的工具。

二、兼顾完整性和排他性

有没有“遗漏”
有没有“重复”
画一根数轴辅助思考
注意边界值
使用 if 语句分解问题
逻辑的基本是两个分支

三、逻辑

逻辑非!：不是 A
逻辑与&，&&：A 并且 B
逻辑或|，||：A 或者 B
异或：A 或者 B （但不都满足）
相等==：A 和 B 相等
蕴涵：若A 则 B

四、德摩根定律

非(P 且 Q) = (非 P) 或 (非 Q)
非(P 或 Q) = (非 P) 且 (非 Q)

真值证明

假设你要证明：

(A v B) = A ^ B，则可构造真值表如下：

A	B	AvB	(AvB)	A	B	A^B
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

可见，在A和B的所有可能取值下， (A v B) 与 A ^ B 的值都相同，故要证明的式子成立。
对于 (A ^ B) = A v B 的情形可以同样的方法证明。

逻辑证明

设x属于Cu(A∪B)
则x属于u却不属于A∪B
所以x属于u却不属于A，也不属于B
故x属于CuA且属于CuB
故x属于CuA∩CuB
反过来，式子仍然成立
同理，另一式也成立

五、真值表

表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。

真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。
表达式可以是论证：
表达式的合取，它的每个结合项(conjunct)都是最后要做的结论的一个前提。

六、文氏图

文氏图（英语：Venn diagram），或译Venn图、 [1] 温氏图、维恩图、范氏图，是在所谓的集合论（或者类的理论）数学分支中，在不太严格的意义下用以表示集合（或类）的一种草图。

它们用于展示在不同的事物群组（集合）之间的数学或逻辑联系，尤其适合用来表示集合（或）类之间的“大致关系”，它也常常被用来帮助推导（或理解推导过程）关于集合运算（或类运算）的一些规律。

七、卡诺图

卡诺图是逻辑函数的一种图形表示。卡诺图是一种平面方格图，每个小方格代表逻辑函数的一个最小项，故又称为最小项方格图。

方格图中相邻两个方格的两组变量取值相比，只有一个变量的取值发生变化，按照这一原则得出的方格图（全部方格构成正方形或长方形）就称为卡诺方格图，简称卡诺图。

八、逻辑表达式

用逻辑运算符将关系表达式或逻辑量连接起来的有意义的式子称为逻辑表达式。逻辑表达式的值是一个逻辑值，即“true”或“false”。C语言编译系统在给出逻辑运算结果时，以数字1表示“真”，以数字0表示“假”，但在判断一个量是否为“真”时，以0表示“假”，以非0表示“真”。

余数

——周期性与分组

一、余数

概念

余数就是做除法预算时剩下的数。周期性和分组是余数性质的体现。

作用

当数据很大时，找到规律，使用余数，获得正确的答案。也就是说，运用余数，大数值得问题就能简化成小数值问题。

二、余数性质

问题 : 今天是星期日，100天以后是星期几？

答案：100%7=2 星期二

周期性

一周有7天。每过7天，变循环到相同的星期数。

分组

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

数0～6分别代表星期日～星期六，为一组。

三、更多思考题

加大难度

问题 : 今天是星期日，10的100次幂天以后是星期几？

答案：100%6=4 星期四

可以直接计算吗？当然不行，数太大。那我们该怎么做？先不急求出答案，先找规律。

规律

1天以后 1%7=1 星期一

10天以后 10%7=3 星期三

100天以后 100%7=2 星期二

1000天以后 1000%7=6 星期六

10000天以后 10000%7=4 星期四

100000天以后 100000%7=5 星期五

1000000天以后 1000000%7=1 星期一

省略…

余数以1，3，2，6，4，5…的顺序循环。

数0～5分别代表星期一、星期三，星期二、星期六、星期四、星期五为一组。

再加大难度

问题 : 1234567的987654321次幂个位数是多少？

答案：987654321%4=1 个位数为7

通过试算找出规律吗？1234567的2次幂，数就很大了。

那我们该怎么做？能影响乘方结果个位数的只有个位数。

规律

7的0次幂 1

7的1次幂 7

7的2次幂 9

7的3次幂 3

7的4次幂 1

7的5次幂 7

7的6次幂 9

省略…

个位以1，7，9，3…的顺序循环。

数0～3分别代表1、7，9、3为一组。

四、奇偶校验

作用

数据传输过程会受到外界干扰，造成数据的改变。通常让数据流的前面或者后面一位成为奇偶校验位，用来检测数据传输过程中是否发生变化。

奇校验

比如Ascll码，我们知道它使用了7位二进制表示了128个常用的字符。现在我们令它的最高位成为奇偶校验位。在发送前，通过改变奇偶校验位是0还是1，从而使得8位数据中1的个数为奇数。
比如0101011，它包含了4个1，在发送前，我们需要在最高位，也就是我们约定的奇偶校验位也加上一个1。如此一来，数据中总共包含了5个1。
在数据传输过程中，如果受到外界干扰，其中任意一个0变为1，则1的个数变为了偶数6。如果其中任意一个1变为了0，则1的个数也变为了偶数4。
如此一来，接收方便可以通过检查1的个数是否为奇数来确保数据是否发生了改变。如果检查的1的个数是奇数，就是正确的数据。如果是偶数，说明数据发生了改变，就丢弃它。

偶校验

偶校验和奇校验一样，这不过在发送的时候校验位要添加的值要确保数据中1的个数是偶数。然后再接收方要检查1的个数是不是偶数，如果是偶数，就是正确的数据，否则，数据发生了改变。

使用奇校验还是偶校验由通信双方规定。它们的区别在于，使用奇校验发送的数据中不会全是0。

五、总结

对于难以处理的庞大数值，只要发现其周期性并使用余数，就能够简化问题。此外，还可以根据余数结果的差异，将许多事物进行分组。只要运用奇偶性就能省略反复试验的过程。当我们“想要详细地研究”事物时，往往容易陷人“想正确把握所有细节”的思维。但是，像奇偶性校验那般，较之“正确地把握”，有时“准确地分类”更为有效。人们只要发现了周期性和奇偶性，就能将大问题转换为小问题来解决。余数就是其中一种重要的武器。

感兴趣的同学：

可以自行百度寻找恋人、铺设草席、哥尼斯堡七桥（一笔画）问题。

数学归纳法

——如何征服无穷数列

一、简介

数学归纳法是证明某断言对于0以上的所有整数(0,1,2,3,…）都成立的方法。0以上的整数0,1,2,3,…有无穷个，但若使用数学归纳法，只需要经过“两个步骤”，就能证明有关无穷的命题。

二、说明

1+2+3…+100？

大家都知道1加到100是5050。如果通过一步一步计算需要很长的时间。那么，有没有一个方法快速的求出答案。

德国数学家高斯（Karl Friedrich Gauss，1777-1855，后来成为了历史上著名的数学家。）在9岁时遇到了同样的问题，却马上得出了答案。当时他既没有计算器也没用计算机，是不是很厉害啊！那么，他究竟是怎么算出来的呢？

小高斯是这么想的：

1+2+3…+100正向计算和100+99+98…+1逆向计算的结果是相同的。那么，如果两者相加就是100个101，100×101=10100。再除于2，获得一半的值就是5050。真是妙不可言啊！

小哆啦是这么想的：

1+100是101，2+99也是101…

那么101有100÷2=50个

所以答案是101×50=5050

多米诺骨牌

想要推到所有的多米诺骨牌，我们会怎么做呢？

大家会说，把它们排成前面一个倒下就能顺次带倒下一个骨牌，推到第一个骨牌就可以了。是的，没错，就是这样。

以上两个案例，就体现了数学归纳法的“两个步骤”。

三、定义

数学归纳法是证明有关整数的断言对于0以上的所有整数（0,1,2,3,…）是否成立时，所用的方法。

假设现在要用数学归纳法来证明“断言 P ( n ）对于0以上的所有整数 n 都成立”。数学归纳法要经过以下两个步骤进行证明。

基底（ base )：证明“ P (0）成立”
归纳（ induction )：要证明无论 k 为0以上的哪个整数，“若 P ( k ）成立，则 P ( k + I ）也成立”。

若步骤1和步骤2都能得到证明，就证明了“断言 P ( n ）对于0以上的所有整数 n 都成立”。

排列组合

——解决计数问题的方法

一、计数

概念

有人会说：计数有什么概念可言，我们从小就学会“数数”，再简单不过了。但是，如果数非常大的时候，计数结果的正确性，我们就很难保证了。这时，我们就需要通过一些方法，获得正确的计数结果。计数就是通过加法法则、乘法法则、置换、排列、组合等计数方法。获得准确的计数结果。

注意

我们不需要死记硬背计数方法，而是注意这些方法是如何推导出来的。

注意“遗漏”和“重复”

计数和第二期内容讲的逻辑是一样的，遗漏就是没有数全所有的数，重复则和遗漏恰恰相反，是将已经数了的，又多数一次或几次。所以，有“遗漏”或“重复”，就不能获得准确的计数结果。

举个例子：

爸爸是大学毕业生，开发工程师

妈妈是大学毕业生，测试工程师

舅舅是高中毕业生，饭店老板

初中以上学历的学历的是3人，根据条件判断，不能有遗漏。即是大学毕业生，又是开发工程师的是1人，不能重复计算，因为是同一人。

注意不要忘记0

我们回顾一下，0所起到的作用。0的作用：站位、统一标准，简化规则。在计算机中，0起到非常重要的作用。不仅在二进制，排序、集合等等都有涉及。

问题 : 间隔1米站1位同学，那么10米需要几位同学？

需要11位同学，因为第一位同学不需要间距，10÷1是10是间隔数，而不是人数。本题和植树问题相似，不要忘记0的重要性。

二、计数方法

加法法则

要数出分为两个集合的事物时，可以使用加法法则。但是，加法法则只在集合中没有重复元素的条件下成立。也就是说，使用加法法则时，一定要注意是否有重复。

问题 : 1～13数字中2的倍数和6的倍数的有多少？

2的倍数有：2,4,6,8,10,12，共6个

3的倍数有：3,6,9,12，共4个

即是2的倍数，又是3的倍数有：6,12，共2个

因此有6+4-2=8

既不是2的倍数，也不是3的倍数。的倍数的个数，加上3的倍数的个数，再减去重复的个数，就是容斥原理（the rinciple of inclusion and exclusion）。这是“考虑了重复元素的加法法则”。在使用容斥原理时，必须弄清“重复的元素有多少”。这也是“认清计数对象性质”的一个例子。

乘法法则

需要根据两个集合进行“元素配对”时，可以使用乘法法则。

举2个例子：

大家都非常熟悉扑克牌，有4种花色，每个花色有A、2～10、J、Q、K，共13张牌。除大王牌，一共是4×13=52张牌。
有3个骰子，摇骰子，3个骰子摇出来的数，形成3位数，共能形成6×6×6=216种。也可以理解为6的3次幂，每个骰子出来的结果有1～6，6种情况，3个骰子就有6的3次幂种。

置换

将 n 个事物按顺序进行排列称为置换（substitution）。

举个例子：

A、B、C这3张牌，有3×2×1=6种排法。因为第1张牌，可以从A、B、C任选。而第2张牌，只能从剩下2张牌中选，第3张牌没得选。

问题：扑克牌（不包括王牌）摆成一排，有多少种排法呢？

和↑例子，思路相同。

52!=52×51×50×…×1 数非常大

这里，52！称为52的阶乘（factorial），是因乘数呈阶梯状递减而得名。

0! 是多少呢？0还是1

三、排列组合

排列

排列（permutation）和置换类似，都需要考虑顺序。区别是置换是排序所有事物，而排序是从事物中拿出几个或多个进行排序。

举个例子：

在上面置换例子的基础上，多了D和E两张牌，也就是有5张牌。从5张牌中，选择3张牌，有如下图所示种排法。P是排列首字母大写。

$P_{5}^{3} = \frac{5!}{(5-3)!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} = 5 \times 4 \times 3$

组合

组合（combination）和置换、排列不同，不考虑排序，内容一样就是相同。

举个例子：

5张里面取3张的组合的总数写作 $C_{5}^{3}$ （C是combination的首字母。）计算如下。

5张里面取3张的组合的总数 = 5张里面取3张的排列总数（考虑顺序排列的数） / 3张的置换总数（重复度） $\frac{P_{5}^{3}}{P_{3}^{3}} = \frac{5 \times 4 \times 3 }{3 \times 2 \times 1} = 10$

置换、排列和组合的关系

置换：可以看作是排列的一个特例，即当排列中选取的元素数目等于集合中元素的总数时，排列就变成了置换。
排列和组合：虽然都涉及从n个不同元素中取出m个元素，但排列关注的是元素的有序排列，而组合关注的是元素的无序组合。简单来说，排列是需要考虑顺序的；组合不需要考虑顺序，仅考虑选择对象。

递归

——自己定义自己

一、开头

“GUN is Not UNIX”，这里GUN是什么的缩写？是“GUN is Not UNIX”的缩写。那第一个单词GUN是什么的缩写？那也是“GUN is Not UNIX”的缩写。是不是一脸懵，这就是递归。在开发中，常常使用递归，方法调用自己。使用递归时，要注意逻辑，不然有可能死循环。

二、汉诺塔

有可能大家没有听说过“汉诺塔”这个词汇。但是，大家一定玩过或听说过这个游戏。是一个由法国数学家爱德华.卢卡斯（Edourd Lucas）于1883年发明的游戏。

游戏规则

有3个柱子，1个柱子上有圆盘，从上往下，圆盘逐渐变大。需要把所有的圆盘从一个柱子上，移动到另一个柱子上。

规则1：一次只能移动一个圆盘。
规则2：圆盘上不能放置比自己大的圆盘。

问题 : n层汉诺塔，至少要移动多少次呢？

2的n次幂减1

我们先笼统的看一下，需要进行的步骤。因为，规则2的限制，需要将最大圆盘以上的圆盘，移动到临时柱子上。我们先将n-1层汉诺塔的移动次数，用H(n-1)函数表示。最大圆盘，只要移动一次，就能放到目标柱子上。然后，我们需要将剩余的圆盘，从临时柱子上，移动到目标柱子。同样，用H(n-1)函数表示。所以，总的移动次数H(n)=H(n-1)+1+H(n-1)。我们将这种 H(n) 和 H(n-1) 的关系式称为递推公式（recursion relation , recurrence）。

我们先依次计算一下：

0个圆盘，H(0)=0，没有圆盘，不需要移动。

1个圆盘，H(1)=H(0)+1+H(0)=0+1+0=1，只需要移动最大圆盘。

2个圆盘，H(2)=H(1)+1+H(1)=1+1+1=3，需要将上面的圆盘先移动到临时柱子，再移动到目标柱子。

3个圆盘，H(3)=H(2)+1+H(2)=3+1+3=7

…

6个圆盘，H(6)=H(6)+1+H(6)=31+1+31=63

在来回移动圆盘的过程中，你一定会觉得“在重复做相似的事情”。之所以会产生这种感觉是因为我们有“发现规律的能力”。这种感觉很重要。

我们看一下，依次计算结果：0,1,3,7,15,31,63…

我相信直觉敏锐且聪明的你，已经找到规律：

0 = 1 - 1

1 = 2 - 1

3 = 4 - 1

…

63 = 64 - 1

获得表达式H(n)=2的n次幂-1，这种只使用 n 表示 H(n) 的式子叫作解析式。

总结

将 n 层汉诺塔转换为 n-1 层汉诺塔的问题，即在问题中找出递归结构。虽然不知道 H(n-1) 的结果，但将它当作“已知条件”来运用。接下来就根据递推结构建立递推公式，求出答案。这就是递归的思维方式。

三、阶乘

我们先看一下，上一期遗留的问题。

n! = n × (n-1) × (n-2) × … × 2 × 1

按照↑的定义，似乎“0的阶乘”意义不明确。

递归定义阶乘

阶乘的递推结构：

n! = n × (n-1)!

阶乘的递推公式：

3! = 3 × 2!

2! = 2 × 1!

1! = 1 × 0!

0! = 1

为了顺利进行上诉递归定义，所以 0! = 1。大家是否发现阶乘的递归定义和数学归纳法比较类似呢？n=0时相当于数学归纳法的步骤1（基底）, n >1时相当于步骤2（归纳）。若用多米诺骨牌来打比方，“正确地定义0!”就相当于“确保推倒第1张多米诺骨牌”。

递归（recursion）和归纳（induction）在本质上是相同的，都是“将复杂问题简化”。

四、斐波那契数列（Fibonacci sequence）

数列0,1,1,2,3,5,8,13,21,34,55,89,… 是在13世纪由数学家斐波那契（Leonardo Fibonacci 1170-1250）发现的，因此被命名为斐波那契数列。

斐波那契数列，只要是程序员，都会了解并掌握。原题是不断繁殖的动物，动物出生后，第二天开始每天1只的速度繁殖下一代，不考虑死亡。动物数量呈爆发式增长。

递归思路和汉诺塔相近且网上有很多。

F(n) = F(n-1) + F(n-2)

F(0) = 0

F(1) = 1

F(2) = F(n-1) + F(n-2) = 1 + 0 = 1

F(3) = F(n-1) + F(n-2) = 1 + 1 = 2

…

感兴趣的同学：

可以继续计算一下，还可以百度摆砖头、创作旋律等递归。

五、分形图（fractale）

含有递归结构的递归图形叫做分形图。插入图片来自于网络。

杨辉三角（帕斯卡三角形）

百度百科解释：杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形（Pascal's triangle）。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。

谢尔平斯基三角形

谢尔平斯基三角形（英语：Sierpinski triangle）是一种分形，由波兰数学家谢尔宾斯基在1915年提出。

递归图形

感兴趣的同学：

还有很多很多递归图形，可以自行查找。

指数爆炸

——如何解决复杂问题

一、指数爆炸

概念

“指数爆炸”，所谓爆炸，其实不是真的爆炸。指数爆炸（blow up），是一个数学术语，即指数函数的 “爆炸性” 增长。如果遇到的问题中包含指数爆炸就要多加注意了。因为一旦处理不好，该问题可能会膨胀到难以收拾的地步。相反，若能巧妙利用 “指数爆炸”，它将成为解决难题的有力武器。

我们先来体验一下指数爆炸的威力。

问题：假设现在有一张厚度为 1 mm 的纸，纸质非常柔软，可以对折无数次。毎对折1次，厚度便翻一番。已知地球距月球约 390000 km，请问对折多少次后厚度能超过地月距离呢？

◆提示
这个问题看上去有点异想天开。即从 1 mm 开始，反复进行厚度翻倍的 “倍数游戏”，要重复多少次才能超过 390000 km。

我们先凭感觉估计一下，需要对折多少次才能达到月球。一万次差不多吧？哈哈学过的小伙伴们，应该已经知道答案了。经过计算发现，仅仅对折 39 次，就让 1 mm 的纸的厚度达到了地球到月球的距离，实在是让人大吃一惊！

仅仅反复 “折纸”，数值不断翻倍，就很快得出了非常庞大的数值。我们把这种数值息这增长的情况称为指数爆炸。之所以称为指数爆炸是因为折纸时厚度（2的n次幂）的指数 n 就是对折次数。根据上下文，也可以称为指数式增长。

虽然把 1 mm 的纸，仅仅对折 39 次，就能从地球到达月球。但是，我们对折 8 次，已经是极限。所以，对折 39 次，只是理论上来说是可以达到的，而现实是做不到的。如同，给我一个支点就能撑起整个地球。

二、倍数游戏

指数爆炸引发的难题

我们开发程序往往都需要测试，如果测试不完备，就会遗留Bug，程序就有可能崩溃（crash）或挂起（freeze）。

举个例子：

程序中有多个按钮，每个按钮都有ON、OFF两种状态，即开和关。每一种开关组合，对应一个指令，也可以说是功能。按钮个数为 3 个时，只有 8 种组合。但是，如果有 30 个按钮，就如折纸一样，会有爆炸性增长。30 个按钮说起来不多，开关组合却达到了 10亿以上。综上所述，穷尽测试是不现实的。因此，通常在软件开发中不进行这种 “一个不漏” 的全覆盖测试，而是只挑选出可能对功能有影响的按钮进行测试。这时，如何选出要测试的范围是很重要的。

三、二分法查找

利用指数爆炸

二分法查找（binary search）是在有序数据中找出目标数据时“总是判断目标数据所在范围内正中间数据”的方法。也叫作 “二分法” “二分查找”。“二分法查找” 的递推公式和“汉诺塔”的递推公式相同，不过 n = 0 时的值不同。P(n) = 2的n+1次幂 - 1，通过 n 次查找，可以在（2的n+1次幂 - 1）数中找到答案。

“二分法查找” 使用了指数爆炸的方法进行查找，这句话的意思是每次查找查找范围会缩小一半儿。换言之，每判断 1 次就能从近 2 倍的查找对象中找出目标数据。