程序员的数学思维修炼(趣味解读)(txt+pdf+epub+mobi电子书下载)

作者：周颖

出版社：清华大学出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

程序员的数学思维修炼(趣味解读)试读：

前言

数学在人类文明的发展过程中起着非常重要的作用。数学推动了重大的科学技术进步。从远古的“结绳记事”，到现代计算机技术的快速发展，都与数学这门学科的发展密不可分。

无论是日常生活中简单的商品交易计算，还是神舟飞船设计中复杂的计算，都离不开数学。生活即数学。没有二进制，就不会有现在的计算机；没有几何学，就没有现在的高楼大厦……。

对于程序员来说更需要知道：数学是计算机科学的基础。在我国，绝大部分大学的计算机科学系都是从数学系中分出来的。由此也可以看出，计算机科学与数学的关系非常紧密。

数学是一门化繁为简的学科。通过数学，可以对现实生活中的很多不同事物进行高度抽象，从而能找出不同事物的共性。不过，由于数学的这种高度抽象，又使数学变得很难学。特别是一些复杂的公式推导，看起来就头痛。

本书面向程序员介绍了程序设计中常用的数学基础知识。通过阅读本书，可以训练程序员的数学思维能力和程序设计能力，进而拓宽视野，增强职场竞争力。

本书特点

□ 简单易懂　用通俗易懂的语言讲解知识点，尽量避免复杂的公式推导过程，让读者能够轻松阅读并掌握相关的数学知识。

□ 门槛很低　阅读本书的读者不需要精通很多高深的数学知识，只需要具备基本的四则运算、乘方等数学基础知识和日常生活中的基本逻辑判断能力即可。

□ 生动有趣　本书拒绝枯燥乏味的讲解，而是代之以轻松活泼的风格，讲解时列举了大量我们都很熟悉，而且非常有趣的数学实例。

□ 内容丰富　本书从最简单的数据的表示开始，对素数、递归、排列组合、逻辑推理、几何构造、统筹规划等方面都会逐一介绍，涵盖了程序员需要掌握的数学知识。

□ 图文并茂　讲解每个知识点和实例时，都给出了简单易懂的图示和必要分析，让读者理解起来清晰明了，没有任何障碍，也让读者感觉到学习数学并不困难。

本书内容概述

第1章通过一则童话故事导入了数据大小的知识，然后逐步介绍了十进制、二进制、八进制、十六进制以及其他常用进制的知识，还介绍了不同进制的转换方法。

第2章从素数的判断开始，逐步介绍了与素数相关的数学知识，包括孪生素数、梅森素数、哥德巴赫猜想、RSA的应用等内容。

第3章介绍递归这种自己调用自己的方法，通过阶乘、汉诺塔、斐波那契数列等经典实例，练习从复杂事物中发现递归结构的方法。

第4章的主题是排列组合，从乘法原理、加法原理入手，介绍了排列与组合的概念和关系，并研究了计算机中的字符编码、密码长度等相关内容。

第5章讨论余数。主要介绍使用余数对数据进行分组，如日历、一些小魔术都是通过余数分组的规则进行的；本章还讨论了计算机中的奇偶校验及两个有趣的问题（座位安排和智叟分牛）。

第6章介绍概率的相关知识，首先从两个常见的事例导入概率的概念，接着从军事故事、赌场游戏、中奖概率等方面介绍了概率的实际应用。

第7章学习翻番的知识。首先介绍翻番和翻倍的概念、计算方式。接着进一步通过复利的威力、对折纸张、舍罕王的赏赐等实例，展示了翻番这个令数据快速增长的数学概念。最后还介绍翻番的逆运算——折半的应用。

第8章学习数理逻辑的相关知识，介绍了逻辑、命题逻辑、布尔逻辑、逻辑的重叠与遗漏等概念，最后介绍了通过卡诺图化简逻辑表达式的方法。

第9章则在第8章的基础上进一步讨论了逻辑推理，包括演绎推理中的三段论、选言推理、假言推理、关系推理，以及归纳推理中的完全归纳推理和不完全归纳推理。

第10章介绍了几何图形构造的基础知识，从花盆摆放、残缺棋盘、丢失的线条等有趣实例，初步了解几何图形构造，最后还介绍了几何图形的分割与拼接。

第11章讨论统筹规划相关知识，首先从田忌赛马这个古老故事中看出统筹规划的重要性，然后通过生活中的两个简单例子认识统筹规划，最后还讨论了“背包问题”及其程序设计方法。

本书读者对象

本书可适用以下各类人员阅读：

□ 计算机专业的学生；

□ 数学专业的学生；

□ 程序设计人员；

□ 数学爱好者；

□ 编程爱好者。

本书作者

本书由周颖主笔编写。其他参与编写的人员有韩先锋、何艳芬、李荣亮、刘德环、孙姗姗、王晓燕、杨平、杨艳艳、袁玉健、张锐、张翔、陈明、邓睿、巩民顺、吉燕、水淼、宗志勇、安静、曹方、曾苗苗、陈超。

编写本书的过程中，虽然编者竭尽全力，不敢有丝毫疏忽，但恐百密一疏，书中仍难免存在不足之处，望广大读者批评指正。编著者

第1章 数据的表示

数学古称算学，是中国古代科学中一门重要的学科。根据中国古代数学发展的特点，可以分为5个时期，分别是萌芽、体系的形成、发展、繁荣和中西方数学的融合。

在数学的不同发展阶段，对于数据的表示都有一些不同的形式。从远古的结绳记数，到现在用计算机等现代科技设计记数，数的表示形式也在逐步演化。

本章主要介绍数据的各种表示形式，包括各种进制及进制之间的转换。

1.1 一则童话

根据我们所学的知识可知道，数据通常是用0、1、2、3、4、5、6、7、8、9这些数来表示，由这些数的不同组合表示现实生活中各种各样的数据。首先来看这个数列中的前两个数：0和1，从通常意义来说，0就是什么也没有，真的是这样吗？对程度员来说不应该这样理解。

先来看这样一个问题，0和1谁大？

1.1.1 0和1的故事

从以上故事可看出以下两点：

□ 0并不表示什么都没有。

□ 数的大小与所处的位置有关系。

下面就来讨论这两个问题。

1.1.2 0是什么都没有？

通常意义上，0表示“没有”的意思。例如，“2012年过去了，可我的收获为零！”这就表示在2012年没有收获。

但是，0真表示什么都没有吗？

其实，0不仅表示什么都没有，它还有更丰富的内涵。例如，0度并不是没有温度，而是表示温度为0度，比零下1度高，比1度低，如图1-1所示。图1-1

在日常生活的常用语中，也有很多用0来表示的，如“很多女孩子都喜欢吃零食”，这里的“零食”并不是表示没有“食”，如图1-2所示。图1-2“为了增加收入，改善生活，很多程序员在业余时间都会接点零活来做。”这里的“零活”并不是没有“活”。

其实，在数学上，0也并不是表示没有。例如，8和8.0相等吗？其含义相同吗？

看起来在小数点后添加一个0是没有意义的，不过，其含义实际是不相同的。在近似数表示中，数字8表示数据只精确到个位，如7.9、8.2等数精确到个位都表示为8。而8.0表示数据精确到十分位，如8.02、7.99等数精确到十分位都表示为8.0。所以，从这个角度来看，8和8.0是不相等的。

1.1.3 0的位置

从“0和1的故事”可看出，当0所处的位置不同时，其含义也不一样。如前面说的8和8.0，当把0放在小数点后面时，从绝对值方面来看，两个数是相等的，但从近似数来看，小数点后多了一个0，其表示的含义也就不一样了。

那么，在小数点左侧添加0呢？如果在数的最左侧添加0，无论添加多少个0，数的大小都不变。

但是，如果在数的中间插入0，数的位置与数的大小关系就很明显了，如在18的中间插入一个0，得到的是108，很明显，其大小差别很大。

对于18，表示十位为1，个位为8，也就是说，表示18这个数有1个10，8个1。而108，表示百位为1，十位为0，个位为8，即表示有1个100，0个10，8个1，这时的0是一个占位符，把1从十位挤到百位。

而如果在紧邻小数点的左侧添加0，则数据会扩大10倍。

1.1.4 程序中的0

在电子技术中，0一般表示低电平，1为高电平。在逻辑计算中，0一般表示逻辑假（False），1为逻辑真（True）。在数值运算中，0与平常数学中0的含义相同。

在程序中，数据0有什么含义呢？

1．未赋值的变量为0？

在不同的程序设计语言中，对于未赋值变量的处理不一样。

对于Basic类的程序语言，如QB（Quick Basic，简环QB）、VB（Visual Basic，简称VB），如果数值型变量未赋初值，则其初始值为0。例如，有以下VB程序代码：

在以上VB代码中，声明了变量i，但未对其进行赋值。虽然未进行变量赋值初始化，但VB编译器会自动将这类数值型变量初始化为0。因此，执行以上代码将显示如图1-3所示的对话框。图1-3

对程序员来说，VB对变量进行初始化的方式很讨人喜欢，变量声明后就可以使用。但是，在.Net Framework中，其处理方式又不相同，例如，以下是VB.NET中的代码：

以上代码并不会出错，但运行后得到的结果如图1-4所示。从这个结果可看出，在VB.NET中，如果变量使用之前未进行初始化，这时其值为空（并不为0）。图1-4

其实，在Visual Studio开发环境中仔细观察代码，可看到在MsgBox函数中的变量i下方有一个波浪线，将鼠标指针指向变量i，可看到如图1-5所示的提示信息，提示变量i在赋值前被使用。图1-5

对于C语言系列的程序设计语言（如C、C++、C#等），程序员就没那么幸运了，未初始化的变量编译器并不会将其初始化为0，而且不同编译系统可能会采用不同的处理方式。例如，有如下的C#程序：

以上的C#程序是没办法编译通过的。在Visual Studio开发环境中可以看到变量i下方有一条波浪线，将鼠标指针移到变量i上，可看到如图1-6所示的错误提示信息，提示使用了未赋值的局部变量i。

要想得到如图1-3所示的对话框，在C#中必须将变量i进行初始化，给变量赋值为0，修改后的代码如下：图1-6

而在Dev-CPP环境中编写以下C语言程序：

编译时不会提示错误，运行时则将显示类似图1-7所示的结果。图1-7

虽然在程序中没有初始化变量i，但变量i却有一个值（图1-7中显示的是1976933940，下次运行该程序时可能又是另一个值），这是为什么呢？原来，在ANSI C中定义变量时，编译器将给该变量分配内存，但并不会将分配的内存初始化为0。这样，原来该内存区域中保存的是什么值，新指定的变量也就具有了什么值。在图1-7所示结果中，给变量i分配的内存中的值正好为1976933940，所以变量i也就具有了这个值。

2．数值0的类型转换

程序中经常会用到数据类型的转换，如将数值类型转换为字符串类型、将数值类型转换为布尔类型等。

将数值0转换为字符串0，这种转换很好理解，其显示的内容都是相同的0，只有在进行数值运算时才能体现出不同。

数值0转换为布尔类型是什么值呢？

在ANSI C中没有专门设置布尔类型，在进行逻辑运算时，将0值作为布尔值False，将非0值作为布尔值True。

在C#中，定义了Boolean类型，数值0转换为Boolean类型时得到的结果为False，非0值转换为Boolean类型时得到的结果为True。

3．除以0异常

我们在小学就学过：0可以做被除数，但不可以做除数。在程序中，当除数为0时，将出现异常。例如，有以下C代码：

当执行以上代码时，由于除数Divisor为0，将产生一个严重的错误，导致程序不能继续运行，如图1-8所示。图1-8

在程序执行中如果遇到这种异常，将导致程序中断，但这不是我们所希望的。一个好的程序员应该考虑并处理程序中可能发生的各种异常，并捕获这些异常，然后给用户显示出一个友好的错误提示信息。不过，ANSI C中并没有提供异常捕获机制，因此需要程序员根据程序执行过程，主动去判断除数，以避免产生这种严重异常。例如，可将以上代码修改为以下形式：

编译执行以上程序，将得到如图1-9所示的结果，提示了“除数不能为0！”，程序并没有进入严重异常状态。图1-9

在异常捕获方面，C++、C#就要方便得多。例如，C#定义了很多异常（也包括DivideByZeroException异常），我们在程序中可以使用try…catch结构来捕获这些异常并进行处理。

1.2 司空见惯的十进制数

有没有想过，为什么6+8=14

从小就这样学的呗！

对，我们小学就开始学“逢十进一，借一当十”，觉得很自然。这就是司空见惯的十进制计数法。

1.2.1 远古的结绳记事

远古时期，人类文明还没有得到发展，但是，“数学”却先于语言、文字而产生。这是因为人们在生活中用到数学的地方很多。例如，每个人捕获猎物的数量，应该怎么表示呢？首先想到的是双手10个手指。天长日久，人类在大自然的生存过程中，积累了更多的生存经验。随着人类征服自然、适应自然的能力逐步提高，捕获或养殖的动物数量也逐步增加，此时靠双手的十个手指来计数就不够了。从史料来看，此时人类进一步的做法是排石子、划道道等。此时，数数还不会，计算更是谈不上。

在我国民间有一种传说，认为伏羲氏始创了结绳记事的方法。结绳记事，是在绳子上打一个结来表示一个数，如图1-10所示，“事大大其绳，事小小其绳，结之多少，随物众寡”，这在当时所起的作用是非常大的。

随着人类文明的进步，人类将一只羊、两只羊、三只羊……这些具体的概念抽象化，得到了数字1、2、3……，只是当时的表现方式有所不同，如图1-11所示。从图中可看到，巴比伦数字类似于按数量摆放石子，而中国数字类似于画痕，罗马数字进一步抽象，用Ⅴ表示数字5，如果在其左侧有一竖，表示为4（=5-1），若在其右侧有一竖，表示为6（=5+1），右侧有两竖，表示为7（=5+2），依次类推。在罗马数字中用Ⅹ表示10，根据其左侧或右侧的竖线数量来表示低于10或大于10的数。现在罗马数字仍在很多地方使用。图1-10图1-11

阿拉伯数字则是现今国际通用的数字，最初由印度人发明，后由阿拉伯人传向欧洲，之后再经欧洲人将其现代化。正因阿拉伯人的传播，成为该种数字最终被国际通用的关键点，所以人们称其为“阿拉伯数字”。阿拉伯数字由0、1、2、3、4、5、6、7、8、9共10个计数符号组成。采取位值法，高位在左，低位在右，从左往右书写。借助一些简单的数学符号（小数点、负号等），这个系统可以明确地表示所有的有理数。为了表示极大或极小的数字，人们在阿拉伯数字的基础上还创造了科学记数法。

1.2.2 什么是十进制计数

正如本节开始时所说，十进制计数法是我们司空见惯的，从小学习的就是十进制。那么，什么是十进制计数？

十进制数基于位进制和十进位两条原则，即所有的数字都用10个基本的数字表示，满10进1，同时同一个数字在不同位置上所表示的数值大小不同，因此数字的位置非常重要。

十进制的基本数字是0、1、2、3、4、5、6、7、8、9。要表示这10个数字的10倍，就将这些数字左移一位，右侧用0补上空位，即可得到10、20、30、……90（0的10倍还是0），如图1-12所示。若要继续扩大10倍来表示数字，就继续左移数字的位置，然后在右侧用0补上空位，即100、200、300……。图1-12

要表示一个数的十分之一，百分之一，千分之一，就将数字向右移，在左侧（小数点右侧）补上0，即可得到十分位（0.1）、百分位（0.01）、千分位（0.001），如图1-13所示。图1-13

1.2.3 为啥人类习惯十进制

为什么我们从小学习的就是十进制，而不是更简单的二进制？

首先，看看我们的双手，我们有10根手指，如图1-14所示。从人类最初计数时起，首先想到的就是用双手的手指来计数，数满10个数再增加一双手，这样就产生了十进制。图1-14

另一个很重要的方面，就是习惯。我们从小接受的教育就是使用十进制数进行计算，因此习惯了十进制数的运算。

二进制的运算规则比十进制简单，为什么不使用二进制呢？这是因为二进制的运算规则虽然简单，但是要表示一个较大的数据时，需要用很长一串数据，如十进制的50000写成二进制为1100 0011 0101 0000，一共需要16位，谁一眼能看出该数据的大小？

如果我们一直使用二进制，可能对二进制表示的数也能方便地识别出来，但是和十进制相比可以看出，十进制数比二进制数更简洁，更易识别。

而比十进制更大的进制（如十六进制），其运算规则复杂，更难以使用。

因此，在日常生活中是以十进制数为主。

1.2.4 十进制运算规则

十进制数的常用运算包括加、减、乘、除这4种，也称为四则运算。在初等数学中，当一级运算（加、减）和二级运算（乘、除）同时出现在一个算式中时，它们的运算顺序是先乘除，后加减。要改变这种运算规则，则需要通过括号，因为四则混合运算中，总是先计算括号内，然后再计算括号外。同一级运算顺序则是按从左到右的顺序进行。

在加、减、乘、除这4种运算中，加、减法互为逆运算，乘、除法互为逆运算，而乘法是加法的简便运算，如图1-15所示。图1-15

1．加法

加法运算是把两个数合并成一个数的运算，可以将整数、小数、分数进行合并运算。在加法运算中，首先应当将相加的数从个位开始按位对齐，然后从个位开始（从右向左）逐位相加。加法运算时，两数（或多数）相加的和超过10时就向前一位进位，这种规则称为“逢10进1”，如图1-16所示。

2．减法

减法运算是已知两个加数的和与其中一个加数，求另一个加数的运算。在减法运算中，首先应当将相减的数从个位开始按位对齐，然后从个位开始逐位相减。如果对应位上被减数小于减数时，需向被减数前一位进行借位，借1当10，再和本位的数相加，得到一个超过10的数，再用这个数与减数进行运算即可，如图1-17所示。图1-16图1-17

3．乘法

乘法运算是求几个相同加数的和的简便运算。乘法运算比加、减法更复杂，不过，对于十进制数的乘法运算来说，只需要背熟九九乘法表，并按此规则逐位相乘，然后再将各位乘积进行累加，即可得到最终结果，如图1-18所示。图1-18

4．除法

除法运算是已知两个因数的积与其中一个因数，求另一个因数的运算。

除法法则：除数是几位，先看被除数的前几位，前几位不够除，多看一位，除到哪位，商就写在哪位上面，不够商1时，要用0占位。除法可能会有余数，余数要比除数小。如果商是小数，商的小数点要和被除数的小数点对齐；如果除数是小数，要将其化成整数后再用整数的除法进行计算。

除法是乘法的逆运算。图1-18所示的乘法算式，可表示成如图1-19所示的除法算式：图1-19

1.2.5 十进制数的分解

十进制数由0～9这10个数字组成，依据数字所在位置决定数值的大小。数据的各位从右向左依次为个位、十位、百位、千位……。

如图1-20所示，个位的9表示有9个1，十位的8表示8个10，百位的7表示7个100，按这种方式，可将十进制数按图1-21所示方式进行分解。图1-20图1-21

仔细看图1-21所示数据的分解式，从右向左，每个数码都比其右侧的数大10倍，可将上式简写成图1-22所示的形式。图1-22

十进制是我们从小就开始学的，以上这些规则都很简单，为什么还要在这里重复呢？因为程序员通过十进制的这些运算规则可推导出其他进制数的运算规则，也可设计解决更多的问题，例如大整数的运算问题。

1.2.6 20！等于多少

在设计大整数之前，我们先来看一个例子。以下是一个C语言程序，该程序中定义了一个计算整数阶乘的函数fact()，在主函数中调用fact()函数计算1～20各数的阶乘。

运行以上程序，得到如图1-23所示的结果。图1-23

从图1-23中可以看出，14!的结果比13!的结果还小，肯定出问题了。为什么会出现这种错误呢？电脑连15的阶乘都计算不出来？

分析程序代码可看出，程序中使用的是int类型的变量，在C语言中，这种变量保存的数据范围为–2,147,483,648～2,147,483,647，而13!再乘以14，其结果已经超过int类型的表示范围（其实，13!的值应该为6,227,020,800，已经超过了int类型的表示范围），因此，数据就出错了，从17!、18!还可以看出其结果变成了负数。

既然知道了出错原因是由于数据类型导致的，那么，是不是将以上程序的int类型改变为位long类型，就可以计算更大数的阶乘了呢？理论上是这样，不过，由于ANSI C中规定，在字长为32位的计算机中，int类型和long类型都是32位。因此，这里将数据类型修改为long也不能解决问题。

在支持64位字长的C#系统中，long类型使用64位二进制位表示（8个字节），其表示的数据范围为–9,223,372,036,854,775,808～9,223,372,036,854,775,807。但是，这么大的数在阶乘面前也很快就被会填满，图1-24所示为使用C#计算各数阶乘的输出结果。

从图1-24中可看到，使用64位字长的long类型，20的阶乘也可以被正确表示出来了。但是更大的数呢？21!、22!的结果是多少？图1-24

哦，My God！还是出错了，21的阶乘就变成负数了。这还是long类型的表示范围问题，long类型的表示范围为–9,223,372,036,854,775,808～9,223,372,036,854,775,807。

对于基本的整数类型，使用ulong（无符号长整型）类型来保存数据，其表示范围也只为0～18,446,744,073,709,551,615，再大的数就没办法表示了。那么，更大数的阶乘该怎么办呢？

1.2.7 大整数构想

在实际应用中，除了阶乘之外，还有很多地方需要使用到非常大的整数，而计算机程序设计语言对数据的表示范围总是有限的。因此，还得我们程序员自己想办法，设计一个能处理大整数的类，这个类应该能处理任意位数长度的整数。

根据本节前面对十进制数的分析，可以很容易地想到，可以在程序中用一个数组来表示大整数的各位，由于数组元素的多少只受计算机内存限制，因此，就可以处理任意长度的大整数了。

如图1-25所示，定义一个数组，然后将数据的各位分解到数组的各个元素中。图1-25

这个数组只是大整数的一种表示形式，要处理大整数，还需要记录数据的正负、加减时的进位等。然后定义以下常用操作：

□ 加法：将整数从个位开始（即数组的0号元素）进行累加。累加时还需判断是否要进位（逢10进1），因此，在累加时还需要将进位数进行累加。

□ 减法：将整数从个位开始（即数组的0号元素）进行减法操作，若不够减还需要从前一位借位（借1当10）。被减数在进行减法操作时还需要减去被借的位。

□ 乘法：按图1-18所列的乘法算式，可将乘数中的每一个数组元素与被乘数相乘，然后将结果累加，即可得到大整数相乘的结果。当然，在进行加法和乘法运算时也需要考虑进位的情况。

□ 除法：除法的实现要麻烦一点。首先要考虑试商的问题，从被除数的高位开始与除数对齐，试商时用被除数的部分位减去除数，判断能减几次，就可商几。另外，除法还需要考虑余数问题。除法的过程如图1-26所示。

从图1-26的演算过程可看到，除法运算需要循环调用加法运算进行试算，然后再调用减法运算计算试商后的余数。

根据这个构想编写大整数处理函数，即可处理任意长度的整数（如可保存、计算长度为100位、200位甚至更多位整数的加、减、乘、除运算），不再局限于C语言所提供数据类型中有限的整数长度了。

有幸的是，在微软的.NET Framework 4（以及JAVA的JDK 1.5）中已经提供了一个大整数类型，可以处理任意长度的大整数。如果使用.NET Framework 4进行开发，就不用自己编写大整数类型了。当然，如果在ANSI C环境下编写程序，仍然可以按本节介绍的构思编写自己的大整数类型。图1-26

1.3 为啥要用二进制

既然人类从远古时代就开始使用十进制数了，为啥还要用二进制呢？二进制有什么优势呢？下面我们一起走进二进制的世界。

1.3.1 人脑与电脑

通过人类的进化，以及人们长期的学习和训练，人脑的潜能可以被不断地发掘。吉尼斯世界纪录中记纸牌记得最多的是一名英国人，他只需看一眼就能记住54副洗过的扑克牌（一共有2808张牌）。还有人能记住圆周率小数点后的42,905位数字！可见，人脑的潜能是可以不断被挖掘的。

在生活中，人脑对很多事物都形成了条件反射，例如，对于数据10与9的大小，我们可以直接反应出10比9大。不过，由于没有通过相应的运算，仅凭人脑直觉反应得出的结果可能是不准确的。例如，对于像比较大的两个数99999999与100000000，要想看一眼就得出哪一个数据更大，就变得不太可能了，即使得出结论，可能也会有错误。为什么呢？这是因为数据的位数变多了，并且重复的数很多，人脑无法一下子反应出来。通常要数一下有多少位数，然后才能进行判断。

计算机（俗称的电脑）却不一样，对于任何操作，电脑都需要经过相应的运算，然后才能得出结果。不管是比较10与9，还是比较99999999与100000000，电脑都会按规定的算法进行运算，最后得出相应的结果。而电脑一旦得出结果，其结果肯定是准确的！

在电脑中，使用二进制来保存数据和编写程序。为什么选用二进制，而不选用人类已经熟练使用的十进制呢？

如果要让电脑使用十进制，首先，应该让电脑能识别出十进制中的10个数字。怎么识别10个数字呢？通常的考虑是，可以通过元器件中电压的高低水平来分别标识10个数字。假如最高电压为12V，那么10个数字中，每个数码可以分配的电压区间为1.33V，如图1-27所示。图1-27

从图1-27可知，每个数之间的电压间隔小，如果外界干扰造成电压大幅变化，数据就不准确了（如本来电压为1.33V，可被识别为数字1，但是由于外界干扰，电压增加了1V，就变成2.33V了，这里距离2.67V更近，就可能被识别为数字2）。还有一个最大的问题，在硬件上要识别这10种状态，其电路结构将非常复杂。

当然，这里只是一种假设，实际应用中采用的是二进制。由于二进制数只有2个数码，电路就很简单了，因为具有两种稳定状态的元件（如晶体管的导通和截止，继电器的接通和断开，电脉冲电平的高低等）很容易被找到。

因此，在电脑中使用二进制主要有以下优点：

□ 技术实现简单。电脑由逻辑电路组成，逻辑电路通常只有两个状态，开关的接通与断开，这两种状态正好可以用“1”和“0”表示。

□ 运算规则简单。两个二进制数的和、积运算组合分别有3种规则，相比十进制数的运算规则来说非常简单（十进制的九九乘法表就有81种规则），有利于简化计算机内部结构，提高运算速度。

□ 适合逻辑运算。逻辑代数是逻辑运算的理论依据，二进制只有两个数码，正好与逻辑代数中的“真”和“假”相吻合。

□ 易于进行转换。二进制数与十进制数、八进制数、十六进制数之间的转换很方便。

□ 抗干扰能力强。用二进制表示数据具有抗干扰能力强、可靠性高等优点。因为每位数据只有高低两个状态，当受到一定程度的干扰时，仍能可靠地分辨出它是高电平还是低电平（只分辨电平的高低，而不用识别具体电压值）。

知道电脑用二进制数来存储后，再来看电脑就简单了。电脑保存的数据用电路的两种状态表示，当数据很大时，只需要增加数据的位数就可以了。

当超大规模集成电路迅速发展起来后，电脑中就可以处理、存储海量数据信息了。并且，由电脑保存的数据保存周期长，不易丢失、损坏。而由于人类的认知及人的记忆会随时间出现遗忘等原因，要用人脑来存储、处理海量信息，就不太可能。

因此，很多人认为电脑比人脑强。其实，电脑本质上只能识别0和1这两种状态！而更复杂的功能，则是由人类对0和1这两种状态进行各种组合而得到的。

1.3.2 二进制计数规则

二进制的计数规则非常简单，只需要记住以下3点就行了：

□ 基数为2。

□ 只有2个数码，即0和1。

□ 逢2进1，借1当2。

如图1-20所示，十进制数可以由多位组成，从右向左分别为个位、十位、百位、千位、万位……，与此类似，二进制数也可由多位组成，从右向左分别为1位、2位、4位、8位、16位……，如图1-28所示。图1-28

为什么称为1位、2位、4位、8位……呢？其实，这是从十进制角度来看二进制的各位数得出的名称。根据二进制计数的规则，用二进制计数时，第一个数为0，第2个数为1（根据逢2进1的规则），接下来为10（所以第2位就是“2位”），继续下来依次为11、100（所以第3位就是4位）、101、110、111、1000……。

如表1-1所示是十进制数0～127用二进制表示的对应形式。从表1-1中可以看到，当十进制数为0和1这两种情况时，可用1位二进制来表示这两种状态；当十进制数在7以内时，可以使用3位二进制数来表示——随着十进制数的增大，对应的二进制数的位数也会增多，在表1-1中表示到十进制数127时就需要7位二进制位来表示了。表1-1　十进制数0～127对应的二进制表示

1.3.3 简单的二进制运算规则

与十进制数的运算规则相比，二进制数的运算规则就简单多了。同样，二进制也可对数据进行加、减、乘、除这些基本的算术运算，另外，二进制数据还可进行逻辑运算。有关逻辑运算的内容需要另一个主题来介绍，下面先来看看二进制的算术运算是多么的简单。

1．加法

与十进制的加法相比，二进制的加法规则要简单得多。如果只考虑一位数相加的情况，在十进制加法运算中，加数和被加数都有0～9共10种可能，因此，会产生100种可能的情况（即使根据加法交换律将重复的运算过滤掉，也会有55种情况）。而二进制加法运算中，加数和被加数都只有两种可能，因此，只会有以下4种情况：

根据加法交换律，将第2、3种运算看作为一种运算，则二进制的加法运算就只有3种情况了。3比55！二进制的加法运算规则是不是要简单得多！

对于多位数的二进制相加，其运算规则与十进制相同，仍然会有进位的情况，只是进位时采用“逢2进1”的方式。例如，将十进制数25加上38，根据表1-1找出对应的二进制数，即可列出如图1-29所示的十进制数与二进制数加法的竖式。图1-29

在图1-29所示的两种进制的加法运算中，左侧的十进制运算是按“逢10进1”的方式进位，右侧的二进制运算则是按“逢2进1”的方式进位。虽然是两种不同的数据表示方式，但运算的结果是一致的（十进制数65对应的二进制数为1000001）。

2．减法

二进制的减法运算规则也很简单，只有以下4种可能：

如图1-30所示为十进制和二进制减法的竖式，在运算时注意十进制是“借1当10”，而二进制则是“借1当2”。图1-30

3．乘法

十进制数的乘法运算需要按“九九乘法表”法则进行，而二进制乘法的规则就简单多了，与加、减类似，也只有以下4种情况：

可以看出，只有当被乘数、乘数都为1时，结果才为1；当被乘数或乘数有一个为0时，相乘的结果就为0。

另外，二进制的乘法运算可以很简单地转化为加法运算。首先看如图1-31所示的乘法竖式，左边是十进制的乘法竖式，右边是二进制乘法竖式。

从右侧的乘法竖式可看出，当乘数某位为0时，这一位与被乘数相乘时各位都为0，当乘数某位为1时，这一位与被乘数相乘时得到的是被乘数对应的各位，只是需要将被乘数向左移动相应的位数。这样，二进制数的乘法就可以很简单地转化为“加法与移位”。图1-31

4．除法

除法是乘法的逆运算，既然二进制的乘法表只有4项，则其除法表也对应有如下4项（其中除以0是无意义的）：

看看图1-31中乘法的逆运算，如图1-32所示。图1-32

从图1-32中可看出，二进制的除法运算也可简单地转化为“减法与移位”操作。

可以看出，在二进制中，加、减、乘、除算法都可转换为加法运算。对于减法运算，只需要将被减数设置为负数，就可将其转换为加法；对于乘法，则可使用“加法与移位”操作来完成；对于除法，则可使用“减法与移位”操作来完成。

既然比较复杂的乘法和除法运算能简单地转化为加、减法和移位操作，因此，电脑中就只需要设计一个加法器即可，这样就简化了电路设计。

1.3.4 二进制数的分解

在前面的二进制计数规则中曾说过，二进制数从右向左依次为1位、2位、4位、8位……，这是指二进制数中各位的意义。虽然只有0和1这两个数码，但是其所处的位置不同，表示数据的大小也不同。例如，有以下二进制数：

这个二进制数共有4位，由3个1和1个0组成。同样的3个1，由于其处于不同的位置，这些1所表示的大小也是不同的，其所处的位置称为权。按从右向左的顺序各位的含义如下：

□ 第1个1表示“1的个数”；

□ 第2个1表示“2的个数”；

□ 第3个0表示“4的个数”；

□ 第4个1表示“8的个数”。

因此，二进制数1011由1个8、0个4、1个2、1个1组成。按各位的权列出的算式如下：

从这种按权展开式可看出，每个位的“权”表现为2的幂次关系，即相邻两位相同数码代表的值为2倍的关系（从右向左看，第2位的1是第1位的1的2倍）。

这种按权展开式可方便地将二进制数转换为十进制数。

1.3.5 十进制数转换为二进制数

将二进制数按权展开，就可以方便地将其转换为十进制数。那么，十进制数该怎么转换成二进制数呢？

十进制整数转换为二进制整数通常采用“除2取余，逆序排列”法。

具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

例如，将十进制数14转换为二进制数时，“除2取余”的转换过程如图1-33所示。图1-33

通过图1-33所示的逐项除2取余方式，得到每次除以2的余数，最后将取得的余数按逆序排列，即将十进制数14转换为二进制数1110。将这个二进制数按权展开，又可得到十进制数14。

1.4 还有哪些进制

其实，除了我们常用的十进制数和电脑用的二进制数之外，生活中还有很多的计数进制，并且有很多的进制也在电脑中使用。

1.4.1 神奇的八卦：八进制

八卦最初是上古人们记事的符号，后被用为卜筮符号，古代常用八卦图作为除凶避灾的吉祥图案。因此，八卦也就被打上了封建迷信的标记。

1．从八卦说起

其实，八卦中隐含了二进制和八进制的概念。首先，八卦的最基本概念是阴和阳，这就相当于二进制中的0和1。在八卦图中用一根长实线代表阳，用一根中间断开的线代表阴，然后由3个这样的线条符号组成8种形式（相当于3位二进制数，可以表示8种状态），因此叫做八卦，如图1-34所示。图1-34

在八卦中，每一卦形代表一定的事物。乾代表天、坤代表地、坎代表水、离代表火、震代表雷、艮（gèn）代表山、巽（xùn）代表风、兑代表泽。

经过几千年的发展，八卦被赋予了很多的含义，除了上面介绍的代表自然现象之外，还可以代表方位、家族、五行，还可以将卦图转换为二进制数。如表1-2所示就是八卦中各卦所代表的不同含义。表1-2　八卦的含义

2．一种计算方式：八进制

可以看出，八卦中的每一卦由3位二进制组成，这样表示8种状态的数据就是一种八进制计数方法。当然，八进制计数不会使用八卦的方式来表示，更多的情况下是使用阿拉伯数字来表示。

八进制计数法则主要有以下3个特点：

□ 基数为8；

□ 由8个数码组成，分别是0、1、2、3、4、5、6、7；

□ 逢8进1，借1当8。

如表1-3所示是十进制数、八进制数和二进制数的对应关系。表1-3　十进制数、八进制数、二进制数对应关系

从表1-3中可看出，1位八进制数与3位二进制数相对应。

八进制计数法在早期的计算机系统中很常见，因此，偶尔我们还能看到人们使用八进制表示法。八进制适用于12位和36位计算机系统（或者其他位数为3的倍数的计算机系统）。但是，对于位数为2的幂（8位、16位、32位与64位计算机系统）的计算机系统来说，八进制就不算很好了。因此，在过去几十年里，八进制渐渐地淡出了电脑。不过，还是有一些程序设计语言提供了使用八进制符号来表示数字的能力，而且还是有一些比较古老的UNIX应用仍在使用八进制。

1.4.2 钟表使用的十二进制

另一个我们常用的进制就是十二进制，如图1-35所示的钟表表面显示为12个小时，即每12小时绕一圈，又从0点开始。图1-35

历史上，在很多古老文明中都使用十二进制来记数。这或许是由于一年中月球绕地球转12圈。在中国文化中，十二进制在记时中也有广泛应用。中国古代设有12地支，与一天的12个时辰对应。一个地支还对应2个节气，从而表示1年的24节气。同时，将地支与12种动物对应，成为12生肖，表示12年为周期的循环。

十二进制在各种度量衡中也经常会用到。如英制单位中1英尺等于12英寸，金衡制中1金衡磅等于12金衡盎司。

十二进制计数法的规则如下：

□ 基数为12；

□ 由12个数码组成，分别是0、1、2、3、4、5、6、7、8、9、A、B；

□ 逢12进1，借1当12。

虽然十二进制在日常生活中很常用，不过，在计算机程序设计中使用的频率倒不多，反而是二进制、八进制、十进制、十六进制使用得要多一些。

1.4.3 半斤八两：十六进制

再来看一个计算机中使用得很多的进制：十六进制。

在日常生活中，也有很多使用十六进制的地方。中国原来使用的重量单位就是十六进制的，即16两为1斤，这也就有了所谓的“半斤八两”的说法了。

现在还在使用的磅和盎司这两个重量单位也是采用十六进制的方式计数的，1磅等于16盎司。

计算机中使用二进制可以很好地计数和运算，为什么还要使用十六进制呢？

在使用二进制书写程序时，会发现有一个很麻烦的问题，要用二进制数表示一个比较大的十进制数时会需要很多位的二进制位。例如，表示十进制的255，就需要8位二进制数，而表示65535这个十进制数，则需要16位二进制数。

在程序中要处理的数据经常会比65535大得多，那就需要使用二进制数的更多位数了。对于很多位的二进制数，不但书写困难，还容易出错（这么长一串，稍不注意就可能输入错误）。

而使用十进制数又不方便与二进制数相对应，因此就引进了十六进制。

十六进制计数法的规则如下：

□ 基数为16；

□ 由16个数码组成，分别是0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F；

□ 逢16进1，借1当16。

如表1-4所示是十进制数、十六进制数和二进制数的对应关系。表1-4　十进制数、十六进制数、二进制数对应关系

从表1-4中可看出，1位十六进制数与4位二进制数相对应。这样，当程序员在编写程序时，若将数据按十六进制格式书写，将大大缩短输入数据的位数。例如，对于十进制数255，用二进制表示需要8个1来表达（即1111 1111），而用十六进制来表示，则只需要2个F（即FF）。类似地，对于十进制数65535用二进制来表示需要16位，而用十六进制来表示，则只需要4位。

1.4.4 60年一个甲子：六十进制

在中国，经常可以听到“甲子”这个概念，这是农历历法中的一个概念，每60年为一个甲子，以天干与地支两者经一定的组合方式搭配成60对，为一个周期。

这就是六十进制的一种使用。

在现实生活中，使用六十进制的地方也很多。不过，与其他进位制不同，六十进制在一般运算和逻辑中并不常用，主要用于计算角度、地理坐标和时间。

例如，1小时等于60分钟，而1分钟则为60秒。而1个圆可被均分成360度，每1度有60角分，1角分等于60角秒。

六十进制在计算机程序中使用得很少。

1.4.5 各种进制之间的转换

前面介绍二进制时，曾介绍了二进制数与十进制数之间的转换方法：二进制数转换为十进制数时，将二进制数“按权展开”，即可得到十进制数；而十进制数转换为二进制数时，使用“除2取余，逆序排列”即可。

类似地，其他进制的数转换为十进制数时也可采用相似的方法，只是在“按权展开”时，使用各进制的基数即可。因此，可得到其他进制转换为十进制的统一按权展开式：

在上面的统一算式中，D表示转换后得到的十进制数，Xn-1为B进制中从右向左数第n位数。例如，二进制数1101的按权展开式为：

而十六进制BC0D的按权展开式为：

如果要将十进制数转换为B进制数，也可以采用除以基数B再取余的方法来求得，如图1-33所示，只是将除数由2改为B进制数的基数B即可。

只要能将任意数转换为十进制数，然后又有将十进制数转换为任意进制数的方法，通过十进制数进行中转，即可进行任意进制数之间的转换了。使用这种思路可编写出以下的进制转换程序，可在任意两种进制之间进行转换。

这个程序比较简单，定义了4个函数：

□ main()函数为主函数，接收输入源数据、进制，以及需要转换成的进制。

□ int_pow()函数为幂运算函数。在任意进制数按权展开时需要用到幂运算。

□ xtod()函数为将任意进制转换为十进制的函数，通过按权展开的方式进行。

□ dtox()函数为将十进制数转换为任意进制的函数，通过除模取余的方法进行。

编译运行以上程序，输入一个数据及其进制，然后输入要转换到的进制，即可得到结果。如图1-36所示，当输入BC0D，并输入进制为16，转换的进制为10，则可得到48141。图1-36

1.4.6 二进制与八进制、十六进制的转换

除了按以上方法进行任意进制之间的转换外，在程序中经常用到的是二进制与八进制、二进制与十六进制之间的转换。对于这些特殊进制间的转换，可以用更简单的方法。

二进制数转换为八进制数，可概括为“3位并1位”的方法。具体转换方法是：按从右向左的方向，每3位二进制数为一组，最高位210不足3位时，添0补足3位，然后将各组的3位二进制数按2、2、2权展开后相加，得到一位八进制数。例如：

而将八进制数转换为二进制数时，可采用相反的操作，即将每位八进制数拆为3位二进制数，称为“1位拆3位”。

类似地，由于1位十六进制数与4位二进制数对应，二进制数转换为十六进制数时就可按“4位并1位”的方法进行，而十六进制数转换为二进制数则可按“1位拆4位”的方法进行。

第2章 神奇的素数

素数在自然数中占有非常重要的地位，素数是一类既简单又神秘的数字。说其简单，是因为小学生也知道什么是素数；说其神秘，是因为从古至今，多少数学家都想弄明白素数的规则，却一直没有找到其分布规律。

数学家都没研究出来的规律，程序员当然也不可能会找到。但是，任何事物都有正反两面，正是由于素数的无规律特点，在密码学中就可以大量采用。另外，在一些齿轮啮合设计中，也通常将齿轮的齿数设计成素数，以增加两齿轮中两个相同的齿相遇啮合次数的最小公倍数，这样可增强齿轮的耐用度，减少故障。

2.1 怎么判断素数

怎么判断素数呢？首先需要对素数进行定义，然后根据其定义判断指定的数是不是素数。对程序员来说，可以按素数的定义编写相应程序对素数进行判断。

2.1.1 什么是素数

数学中的定义是这样的：素数，又称为质数，是指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数。或者说素数是只有1和本身两个因数的数。

比1大但不是素数的数称为合数。1和0既非素数也非合数。

根据素数的定义，可用如图2-1所示方式列出10以内各数的因数，从而得出2、3、5、7为素数，而4、6、8、9不是素数。图2-1

从上面的因数分解可看出，10以内共有4个素数。随着数据的增大，素数的分布频率将变得更稀少，10000以内的素数共有1229个，由于篇幅所限不逐一列出，下面列出1000以内的168个素数，如图2-2所示。图2-2

对图2-2所列出的1000以内的素数进行总结，可看出在以100为间隔的区间中素数的个数是没有规律的，其中：

□ 100以内的素数有25个；

□ 100～200之间的素数有21个；

□ 200～300之间的素数有16个；

□ 300～400之间的素数有16个；

□ 400～500之间的素数有17个；

□ 500～600之间的素数有14个；

□ 600～700之间的素数有16个；

□ 700～800之间的素数有14个；

□ 800～900之间的素数有15个；

□ 900～1000之间的素数有14个。57885161

目前最大的已知素数是2–1（此数字位长度是17425170），它是在2013年1月25日由GIMPS发现的。该组织还在431126092008年8月23日发现了目前所知第二大的已知素数2–1（此数字位长度是12978189）。

2.1.2 验证素数

在图2-2中列出了1000以内的素数，究竟这些数据是不是素数呢？需要进行验证。

验证一个自然数是否为素数，这个问题在中世纪就引起了人们的注意，当时人们试图寻找一个公式一劳永逸地解决问题，到了高斯时代，基本上确认了简单的素数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。验证素数的算法可分为两大类，即确定性算法及随机算法，如图2-3所示。图2-3

确定性算法可得出确定的结果，但通常算法较慢，而随机算法正好相反。通过计算机进行运算，可解决算法较慢的问题，其算法的实现也很简单。

确定性算法中最常用的就是试除法。试除法是根据素数的定义得出的一种方法，用需要验证的数N逐个除以从2开始至N–1中的所有数，若能被某一个数整除，表示有一个因数，说明数N不是素数；若直到N–1都不能被整除，则说明该数是素数。

根据以上思路，可编写以下的试除法函数：

其实，可以对素数的定义进行进一步的分析。要判断数N是否为素数，不需要用N一直除到N–1才能确认，而只需要除到根据以上分析可看出，从6个红球号码中选择5个就可以了。例如，N=15，则能被15整除的除数有1、3、5，对于除数5就不用判断，因为N被3整除时其商就是5，也就表示N能被5整除了。

因此，为了减少循环判断的次数，提高程序的执行效率，可将函数is_prime()进行修改，以提高程序的效率。2

从上面的程序可看到，在for循环中以i与n值进行比较，就可以显著地减少循环的次数，从而提高验证的效率。

2.1.3 寻找素数的算法

通过验证方法可以验证某个整数是否为素数，而寻找素数的方法，就是寻找在给定限度内的所有素数排列。例如，要求出1000以内的所有素数，就是一个寻找素数排列的问题。由于已经有上面定义的is_prime()函数，求出1000以内所有素数的方法就很简单了，可以用以下程序来完成。

执行以上程序，可得到1000以内的所有素数列表，如图2-4所示。图2-4

在上面的代码中，通过is_prime()函数来验证指定区间（2～1000）中的每一个数是否为素数，而is_prime()函数中又通过循环进行验证。这种双循环会导致程序执行效率不高。

这时可考虑采用另一种寻找素数的算法：著名的Eratosthenes求素数方法。下面演示如何用这种方法求100以内的素数。

Eratosthenes算法假设有一个筛子，用来存放2～100之间的所有数，如图2-5（a）所示。

由于偶数都能被2整数，因此偶数都不是素数（2除外），则将这些数筛去，得到如图2-5（b）所示的数据（设置了背景色的数字将被筛去）。

接着再将3的倍数筛去，得到如图2-5（c）所示结果。

接下来继续将5的倍数筛去，得到图2-5（d）所示结果。

最后再将7的倍数筛去，得到如图2-5（e）所示结果，即可得到100以内的所有素数。图2-5

从图2-5中可看到，在使用Eratosthenes算法进行筛选时，只需要执行4次筛选就完成了100以内的素数的筛选，效率非常高。如果要筛选的数据范围更大，由于只需要选择已经筛选过的素数对后面的数进行筛选，因此可快速筛选出后面的素数。

从图2-5中的算法过程可以看出，Eratosthenes算法比试除法的效率要高得多。

根据图2-5中所示的过程编写相应的程序，具体代码如下：

2.1.4 已被证明的素数定理

自古以来就有很多数学家研究素数，因此，得出了许多与素数有关的定理。下面简单介绍一些已被证明的素数定理。

1．在(a,2a]之间必有一个素数

在一个大于1的数a和它的2倍之间（即区间(a, 2a]中）必存在一个素数。如图2-6所示，可看到在(a, 2a]区间中都至少包含一个素数。

2．存在任意长度的素数等差数列

什么是等差数列呢？这是一个古老的数学课题。一个数列从第二项起，从后项减去前项所得的差是一个相同的常数，则这个数列就被称为等差数列。图2-6

用素数构成的等差数列被称为素数等差数列。例如从5开始，以12为间隔常数，就可以得到这样的序列：

对这个数列来说，只有前5个数是素数，第6个数65能被5整除，不是素数，因此，在这里得到的是由5个素数构成的素数等差数列：

还有更长的素数等差数列吗？当然有，如下面的10个素数就构成间隔为210的素数等差数列：

2004年4月18日，格林和陶哲轩两人宣布：他们证明了“存在任意长度的素数等差数列”，也就是说，对于任意值K，存在K个成等差级数的素数。例如K=3，有素数序列3、5、7（两数之间差2）……K=10，有素数序列199、409、619、829、1039、1249、1459、1669、1879、2089（两数之间差210）。他们将长达50页的论文——《素数含有任意长度的等差数列》张贴在当日的预印本网站上，并向《美国数学年鉴》（Annals of Mathematics）投稿。

这是一项惊人的成就，他们的发现揭示了素数中存在的某种规律。他们的证明立即在国际学术界引起轰动。

3．其他已证明的素数定理

已证明的素数定理还包括以下几项：

□ 一个偶数可以写成两个数字之和，其中每一个数字最多只有9个质因数。

□ 一个偶数必定可以写成一个质数加上一个合数，其中的因子个数有上界。

□ 一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合数。后来，有人简称这个结果为（1+5）。

□ 一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合数，简称为（1+2）。

2.2 孪生素数

我们知道，素数在自然数中的比例很少，而孪生素数就更少了。那么，什么是孪生素数？孪生素数有什么特点呢？

2.2.1 什么是孪生素数

所谓孪生素数，是指间隔为2的相邻素数，它们之间的距离已经近得不能再近了，就像孪生兄弟一样，因此被称为孪生素数，也称为双生素数。

例如，素数3和5，其间距为2，就是一组孪生素数。100以内的孪生素数还有5与7，11与13，17与19，29与31，41与43，59与61，71与73。

100以内的孪生素数共有8对，不过，随着数字的增大，孪生素数的分布变得越来越稀疏，寻找孪生素数也变得越来越困难。那么会不会在超过某个界限之后就再也不存在孪生素数了呢？

2.2.2 孪生素数的公式

对于自然数Q与Q+2，若都不能被小于的任何素数整除，则Q与Q+2就构成一对孪生素数。这句话可以用以下公式表达：

以上公式中，P、P、P表示从小到大的顺序素数2、3、5、12k27……，B≠0且B≠P–2，若Q<(P)–2，则Q与Q+2是一对孪生素数。iiiK+1也就是说，将数Q分解后，最小剩余不能为0和P-2，例如Q不能是2M，i3M+1，5M+3，7M+5……，PM–2，否则Q+2就是合数。ii

看一个例子吧。假设Q=29，可分解为以下算式：

由于的结果取整后为5，因此，在上式中只按公式分解到5为止，一共有3项（即k=3），且每项的B值都不为0，且B的每一项不i等于P–2。因此，可得到29与29+2是一对孪生素数。i

上式也可使用同余式来表达：

根据中国剩余定理，对于给定的余数，在除数为素数的范围内有唯一的解。例如在上式中，除数为2、3、5时余数也知道了，因此就可以推算出Q的值为29。

2.2.3 中国剩余定理

什么是中国剩余定理呢？先来看一则中国民间的传说故事——“韩信点兵”。秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足500，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步紧逼，楚军乱作一团。交战不久，楚军大败而逃。

韩信是怎么知道军队有1073名士兵的呢？

对于这个问题，可将其描述为一个数学问题，就是：一个数除以3余2，除以5余3，除以7余2，求这个数是多少？

先列出除以3余2的数：

再列出除以5余3的数：

在这两列数中，首先出现的公共数是8，3与5的最小公倍数是15，两个条件合并成一个就是：

将n分别取1、2、3、……即可得到数列：

再列出除以7余2的数：

可以看出，符合题目条件的最小数是23。

也就是说，我们已把题目中三个条件合并成一个：该数除以105余23。

由于汉军原有士兵1500人，死伤四五百人，即剩余的士兵应为1000余人，即可得到士兵的总数：

2.2.4 孪生素数分布情况

我们知道，素数本身的分布是随着数字的增大而越来越稀疏，不过幸运的是，早在古希腊时代，欧几里得（Euclid）就证明了素数有无穷多个。长期以来人们猜测孪生素数也应该有无穷多组，可是该怎么验证这个猜想呢？

对于程序员来说，当然是想编写程序来查找素数和孪生素数。当然，由于计算机位数的限制，所表示的整数范围是有限的，如果要找出更多的素数或孪生素数，需要另外编写大整数处理的相关功能。

由于篇幅限制，本书将不介绍大整数方面的功能，下面只列出一个简单的求解孪生素数的程序。在程序中，将先筛选出素数，然后在素数中再筛选出孪生素数。

执行以上程序，将得到如图2-7所示的结果。从结果中可以看到，在10000以内共有1229个素数，而孪生素数只有205对。图2-7

在上面的程序中，常量MAXNUM定义为10000，即可求出10000以内的素数，如果将MAXNUM定义为更大的常量值，则可求出更多的素数和孪生素数。当然要注意，由于计算机中变量表示范围及程序栈空间大小的限制，MAXNUM定义的数据大小是有限的。

2.3 使用素数的RSA算法

RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。RSA算法就是素数的典型应用。下面简单介绍一下RSA算法，要完整地实现RSA算法，需要较长的代码，本书就不给出相应的程序了，而是重点介绍RSA的概念、原理和实现的过程。

2.3.1 什么是RSA

在计算机中常用的加解密技术分为两类，即对称加密和非对称加密。

在对称加密技术中，对信息的加密和解密都使用相同的密钥Key，如图2-8所示，也就是说使用同一个密钥Key对数据进行加密和解密。这种加密方法可简化加解密的处理过程，信息交换双方都不必彼此研究和交换专用的加解密算法。如果在交换阶段，密钥Key没有泄露，那么加密数据的机密性和报文完整性就可以得到保证。

对称加密技术虽然简单，但存在一些不足，由于加密、解密都需要使用同一个Key，这样，信息传送双方都要接触到这个Key，密钥Key更容易泄露。图2-8

而非对称加密（又称为公开密钥加密）中，不再只有一个密钥Key了。在非对称加密算法中，密钥被分解为一对，一个称为公开密钥（简称公钥PK），另一个称为私有密钥（简称私钥SK）。对于公钥，可以通过非保密方式向他人公开，而私钥则由解密方保存，不用对别人公开。

发送信息的一方通过公钥对数据进行加密，然后发送给接收方。接收方通过私钥对密文进行解密，加、解密的过程如图2-9所示。图2-9

由于非对称加密方式可以使通信双方无须事先交换密钥就可以建立安全通信，因此被广泛应用于身份认证、数字签名等信息交换领域。

非对称加密体系一般是建立在某些已知的数学难题之上，是计算机复杂性理论发展的必然结果。最具有代表性的非对称加密方式是RSA公钥密码体制。

2.3.2 RSA算法基础

在RSA算法中，最基础的一个定理就是RSA定理，这个定理描述如下：若P和Q是两个相异质数，另有正整数R和M，其中M的值与( P–1 )( Q–1 )的值互质，并使得( RM ) mod ( P–1 )( Q–1 )=1。有正整数A，且A

在以上描述中mod表示取余的运算。

在RSA算法中还引用了很多定理，详细介绍的话需要很大篇幅，这里就不逐一介绍了。下面介绍一下RSA算法的基础操作步骤。

1．生成公钥和私钥

生成公钥PK和私钥SK的步骤如下。（1）随意选择两个大的素数P和Q，P不等于Q。（2）将P、Q两素数相乘得到一个数N，即N=PQ。（3）将P、Q分别减1，再相乘，得到一个数T，即T=（P–1）（Q–1）。（4）选择一个整数E，作为一个密钥，使E与T互质（即E与T的最大公约数为1），并且E必须小于T。（5）根据公式DE mod T=1，计算出D的值，作为另一个密钥。（6）通过以上步骤计算得出N、E、D这3个数据，其中（N、E）作为公钥，（N、D）作为私钥（当然也可以将公钥和私钥互换）。（7）生成公钥和私钥后，就可以将公钥对外发布了，如图2-10所示。图2-10

2．用公钥加密信息

发送信息的一方收到公钥PK后，就可以通过公钥PK对数据进行加密。加密的操作步骤如下，其中明文为M，加密后得到的密文为C，公钥为（N，E）。

3．用私钥解密信息

接收方持有私钥（N，D），在接收到密文C后，即可通过私钥进行解密，得到明文M。解密的过程如下：

2.3.3 RSA算法实践

了解RSA算法生成密钥、加密、解密的过程之后，接下来进行一次RSA算法的模拟操作，进一步了解RSA算法的使用过程。

1．生成公钥和私钥

生成公钥PK和私钥SK的过程如下：

2．用公钥加密

有了公钥，就可方便地进行数据加密了。在上面这个例子中的公钥为（143，7），私钥为（143，103），由于是手工计算，为了使计算的数据量小一点，因此将公钥与私钥进行交换，即公钥使用（143，103），而私钥则使用（143，7）。设明文为2，则加密过程如下：

3．用私钥解密

收到密文C（这里为63）后，则可以通过私钥（143，7）进行解密，解密过程如下：

从以上生成密钥、加密、解密的过程可以看出，虽然我们这里只使用了两个小的素数11和13，但其计算量却很大，特别是在加密和解密过程中，需要进行幂运算，得到的结果将是一个非常大的整数。在实际应用中，P、Q要取很大值的素数，则得到的N、D、E值也将很大，所以在加密、解密过程中的幂运算结果将更大，通过C语言（或其他程序设计语言）提供的基本数据类型已经没办法保存这么大的数了。

因此，在RSA算法中，虽然过程很简单，但需要编写程序处理大整数，包括大整数的加、减、乘、除、幂运算等。

2.3.4 RSA应用：数字签名

RSA的典型应用就是数字签名技术。

数字签名技术是实现交易安全的核心技术之一，它的实现基础就是RSA加密技术。在这里，我们介绍数字签名的基本原理。

以往的书信或文件是根据亲笔签名或印章来证明其真实性的。但在计算机网络中传送的报文又如何盖章呢？这就是数字签名所要解决的问题。数字签名必须保证以下几点：

□ 接收者能够核实发送者对报文的签名；

□ 发送者事后不能抵赖对报文的签名；

□ 接收者不能伪造对报文的签名。

现在已有多种实现数字签名的方法，但采用公开密钥算法要比常规算法更容易实现。下面就来介绍这种数字签名。

发送者A用其私密密钥SKA对报文M进行运算，将结果DSKA（M）传送给接收者B。接收者B用已知的A的公开密钥得出EPKA（DSKA（M））=M，如图2-11所示。图2-11

因为除A外没有别人能具有A的私密密钥SKA，所以除A外没有别人能产生密文DSKA（M）。这样，报文M就被签名了。用私钥加密后的密文发送给对方，对方只能用持有的公钥进行解密，以实现核实发送者对报文的签名。

假若用户A要抵赖曾经发送过报文给用户B。用户B可将M及DSKA（M）出示给第三方。第三方很容易用PKA去证实用户A确实发送消息M给用户B。反之，如果是用户B将M伪造成M'，则用户B不能在第三方面前出示DSKA（M'）。这样就证明用户B伪造了报文。可以看出，实现数字签名也同时实现了对报文来源的鉴别。

2.3.5 RSA被破解的可能性

加密与破解是一对矛盾，再强的加密方法，总有被破解的一天。RSA算法是否安全呢？是否能被很轻松地破解呢？

RSA是被研究得最广泛的公钥算法，从提出到现在经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥方案之一。

RSA的缺点主要有以下两点：

□ 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

□ 分组长度太大，为保证安全性，N至少也要600比特二进制位以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET协议中要求CA采用2048比特二进制位长的密钥，其他实体使用1024比特的密钥。

根据前面的运算过程可看出，RSA算法的安全性依赖于大数分解。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。

RSA的安全性在于对于一个大数N，没有有效的方法能够将其分解，从而在已知（N， D）的情况下无法获得E；同样在已知（N，E）的情况下无法求得D。

在本节前面演示RSA加密算法时，P、Q的取值很小，使得N的值也很小，当得知（N，E）可以很容易地被破解计算出D，根本不能保障安全性！

这里选择小的P、Q是因为通过手工计算，太大的数没办法处理，而在实际应用中必须选择较大的P、Q，使得计算出的N足够大，这样不容易被破解。当然，随着计算机运算速度的提高，被破解的可能性也就变大了。现在小于1024位的N已经被证明是不安全的，因此不应使用小于1024位的RSA，最好是使用2048位的N。

例如，下面是一个1024位的N值及D和E值：

怎么样，看着这么长的N值头痛了吧（1024比特二进制位是256位16进制数）。这么长的数不要说用手工计算，就是用计算机来计算，也需要专门编写处理大整数运算的相关方法，才能进行处理。

当将N值取为2048比特二进制位时，则计算量将更大，从而就可保障密文的安全。当计算机速度更快，能较快破解密文时，还需要将N值取得更大。

2.4 哥德巴赫猜想

说到素数的相关知识，就离不开哥德巴赫猜想。本节简单介绍哥德巴赫猜想的相关内容，了解什么是哥德巴赫猜想，怎么进行哥德巴赫猜想验证。

2.4.1 哥德巴赫猜想是什么

1742年，在给欧拉的信中，哥德巴赫提出了以下猜想：

因现今数学界已经不使用“1也是素数”这个约定，当初猜想的现代陈述为：

欧拉在回信中也提出另一等价版本，即：

今日常见的猜想陈述为欧拉的版本，把命题：

1966年，我国的陈景润证明了“1+2”的成立，即：14

对于哥德巴赫猜想的实际验证表明，至少4～10以下的偶数都能表示成两个素数之和。很多时候，偶数表示成两个素数和的方法还不止一种，例如：

大数学家欧拉相信这个猜想是正确的，但他不能证明。

叙述如此简单的问题，连欧拉这样首屈一指的数学家都不能证明，这个猜想便引起了许多数学家的注意。从哥德巴赫提出这个猜想至今，许多数学家都不断努力想攻克它，但都没有成功。

为什么说没有成功呢？由于在数列中，某一个数是否为素数是没有规律的，只能逐个推算。而对于一个很大的整数，要求出其等于两个素数之和，其计算量是非常巨大的，例如，要求1万位或10万位的整数是否等于两个素数之和，不要说手工计算，就是用计算机来推算，其程序设计的工作量都显得很复杂，需要处理大量的数据存储和转换过程。当然，对于一些比较小的整数，则可以很容易地求出来其等于两个素数之和。

2.4.2 数值验证

与不少数学猜想一样，数值上的验证也是哥德巴赫猜想的重要一环。5

1938年，尼尔斯·皮平（Nils Pipping）验证了所有小于10的偶数。7

1964年，M·L·斯坦恩和P·R·斯坦恩验证了小于10的偶数。10

1989年，A·格兰维尔将验证范围扩大到2×10。11

1993年，Matti K. Sinisalo验证了4×10以内的偶数。14

2000年，Jorg Richstein验证了4×10以内的偶数。18

至2012年2月为止，数学家已经验证了3.5×10以内的偶数，在所有的验证中，没有发现偶数哥德巴赫猜想的反例。

虽然不是数学家，但身为程序员的我们也可进行一翻哥德巴赫猜想的验证，例如：

首先检验：6=3+3；

接着检验：8=3+5；

接着检验：10=5+5；

…………

下面利用计算机的快速计算能力，编写程序验证哥德巴赫猜想。

对于哥德巴赫猜想的验证，算法很简单，其基本思路是：设N为大于等于6的一个偶数，可将其分解为N和N两个数，分别检查N和121N是否为素数，如都是，则在该数中得到验证。若N不是素数，就21不必再检查N是否素数。先从N=2开始，检验N和N（N=N-N）是211221否素数。然后是N+2，再检验N、N是否素数……，直到N=N/2为止。1121

为了提高程序的效率，可对程序进行优化，首先根据Eratosthenes算法将指定范围中的素数都筛选出来保存到一个数组中，接着对整数N进行分解和判断。

根据上面的思路，编写相应的C程序如下：

执行以上程序，输入1000000（一百万），验证1000000以内的偶数，运行结果如图2-12所示。图2-12

从图2-12中的运行结果可看出，在1000000以内的所有偶数都通过了验证。

2.5 梅森素数

我们知道，在自然数中素数较少，10000以内的自然数中只有1229个素数，而孪生素数就更少，10000以内的孪生素数只有205对（510个）。在素数中还有更稀少的一个种类，那就是梅森素数，截止2013年2月，人们仅发现48个梅森素数。

2.5.1 什么是梅森素数

那么，什么是梅森素数呢？

马林•梅森是17世纪法国著名的数学家和修道士，也是当时欧洲科学界一位独特的中心人物。梅森在欧几里得、费马等人的有关研究P的基础上对2–1作了大量的计算、验证工作，并于1644年在他的《物理数学随感》一书中断言：对于P=2、3、5、7、13、17、19、P31、67、127、257时，2–1是素数；而对于其他所有小于257的数时，P2–1是合数。前面的7个数（即2、3、5、7、13、17和19）属于被证实的部分，是他整理前人的工作得到的；而后面的4个数（即31、67、127和257）属于被猜测的部分。不过，人们对其断言仍深信不疑，连大数学家莱布尼兹和哥德巴赫都认为它是对的。梅森的猜测中遗漏了61、89、107，而将67和257被错误地包含了进来。

虽然梅森的断言中包含错误，但他的工作极大地激发了人们研究P2–1型素数的热情，使其摆脱作为“完美数”的附庸的地位。由于梅P森最早系统而深入地研究2-1型的数，为了纪念他，数学界就把这种P数称为“梅森数”；并以M来标记梅森数，即M=2-1。如果梅森数ppP为素数，则称之为“梅森素数”（即2–1型素数。）。P

总结一下，梅森素数是指形如2–1的正整数，其中指数P是素数，常记为MP。若M是素数，则称为梅森素数。P

当P=2、3、5、7时，M都是素数，但P=11时，M不是素数，P11因此M不是梅森素数，如图2-13所示。11图2-13

2.5.2 已知的梅森素数列表

是否有无穷多个梅森素数？这是数论中未解决的难题之一。截止2013年2月累计发现48个梅森素数，最大的是P=57885161（即57885161M=2–1)，此时M是一个17,425,170位的非常大的整57885161P数。

如表2-1所示是目前为止已发现的梅森素数列表。表2-1　梅森素数列表

由于现在还不知道在第42个梅森素数（M）至第48个梅25,964,951森素数（M）之间是否还存在未知梅森素数，所以在其序号57,885,161之前用*标出。

第3章 递归——自己调用自己

递归（Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中又调用函数自身的方法。递归是一种奇妙的思考问题的方法，通过递归的这种思路，可简化问题的定义。

3.1 从前有座山，山里有座庙

递归一词常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。

3.1.1 老和尚讲的故事

将时光往前推，在中国还流传着这样一个有趣的故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

怎么样？这个故事就是不断重复着老和尚讲的故事，有趣？还是无聊？

不管怎样，这个故事可以不断地重复，一直讲下去。

这就是生活中一个用递归形成的故事。

3.1.2 德罗斯特效应

再来看一张图，如图3-1所示为一张网页的截图，在网页图中又包括相同的一份较小的截图，在小图中又包含一份更小的截图，……，这样就形成了一幅递归形式的图形。

图3-1所示的图形称为德罗斯特效应（Droste effect），是递归的一种视觉形式，是指一张图片的某个部分与整张图片相同，如此产生无限循环。这种照片是通过名为Mathmap的数学软件制作出来，使用PhotoShop的Droste Effect滤镜也可制作出这种效果。图3-1

3.1.3 什么是递归

那么，什么是递归呢？

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

例如，我们人类的发展繁衍中，人之间的辈份就是一种递归（如图3-2所示），在这个递归中首先定义一个基本情况，接着递归定义，具体情况如下：图3-2

□ A的父母是A的祖先（这是基本情况）。

□ A祖先的双亲同样是A的祖先（递归步骤）。

对于递归，一种便于理解的心理模型，认为递归对对象的定义是按照“先前定义的”同类对象来定义的。

例如：要求能移动100个箱子，该怎么移动？

首先移动1个箱子，并记下它移动到的位置，然后再去解决较小的问题（由于已移动了1个箱子，剩下99个箱子），这时的问题就简化为“怎样才能移动99个箱子？”，……不断重复，到最后，问题将简化为“怎样移动1个箱子”，如图3-3所示。图3-3

类似的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数，如图3-4所示。图3-4

3.1.4 用递归能解决哪些问题

递归是一种非常接近自然思维的思想，其实了解多了以后，用起递归来是非常自然的，但不是每个场合使用递归都是合适的。通常递归方法适合于层次结构本身就是递归定义的情况，比如二叉树的遍历，因为二叉树的定义就是“一颗空树，或者一个节点+左右两颗子二叉树”，它的定义就是递归的，所以用递归操作相当方便。

简单来说，递归问题，可以划分为一个或多个子问题，而处理子问题的规则与处理原问题的规则是一样的。

如图3-2所示的祖先问题、用集合论对自然数的定义问题，以及老和尚讲的故事，都是无穷无尽的。通常意义上来说，对于一个无穷尽的问题，是没办法编写程序来解决的，因为程序没有办法结束。

虽然常见的递归问题都没有尽头，不过，我们可以找到起点，这时可从某一个指定的终点开始，向起点方向运行，当到达起点位置时，即可结束递归调用。

那么，在实际应用中要使用递归算法，通常需要分析以下3方面的问题：

□ 每一次递归调用，在处理问题的规模上都应有所缩小（通常问题规模可减半）。

□ 相邻两次递归调用之间有紧密的联系，前一次要为后一次递归调用做准备，通常是前一次递归调用的输出作为后一次递归调用的输入。

□ 在问题的规模极小时，必须直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的（以规模未达到直接解答的大小为条件），无条件递归调用将会成为死循环而不能正常结束。

根据上面的描述，在设计递归算法时，主要需考虑以下两方面的问题：

□ 确定递归公式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。

□ 确定边界（终了）条件。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。

3.1.5 一个简单例子：求最大公约数

求最大公约数是数学中一个简单的问题。

如果有一个自然数A能被自然数B整除，则称A为B的倍数，B为A的约数。几个自然数公有的约数，叫做这几个自然数的公约数。这些公约数中最大的一个公约数，称为这几个自然数的最大公约数，简称为GCD。

例如，在2、4、6这3个数中，2就是2、4、6的最大公约数。

怎么求最大公约数呢？早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。

辗转相除法的方法是用较大的数M除以较小的数N，较小的除数N和得出的余数R构成新的一对数，继续重复前面的除法（用较大数除以较小数），直到出现能够整除的两个数，其中较小的数（即除数）就是最大公约数。

例如，求153和123的最大公约数，操作过程如下：

所以，153和123的最大公约数就是3。

可以看出，在用辗转相除法求最大公约数时，每次相除后的除数N和余数R都将原来的问题规模缩小，而且有一个边界条件（两数能够整除，即余数为0）。有这两条，就可使用递归算法来解这个问题，处理流程如图3-5所示。图3-5

根据图3-5所示的流程，可编写出以下C语言程序。

在以上程序中，定义了一个gcd()函数，在这个函数中调用gcd()函数，这样就形成了递归调用。在这个函数内部通过辗转相除，然后判断余数是否为0，若为0就返回n值，否则递归调用gcd()函数进行辗转相除。

怎么样，递归调用函数是不是很简单呢？

3.2 用递归计算阶乘

阶乘（factorial）是基斯顿·卡曼于1808年发明的运算符号。阶乘也是数学里的一种术语，在很多计算中都要使用到阶乘。

3.2.1 阶乘该怎么计算

一个正整数的阶乘是所有小于或等于该数的正整数的积，并且有0的阶乘为1的约定。自然数n的阶乘写作n!。

例如，求5的阶乘的算式如下：

从上式可看出，当求n的阶乘时，就从1逐项相乘到n即可，这是一个循环结构，因此编写一个循环程序就可很容易地求出数据n的阶乘，在第1章中曾给出过一个通过循环计算阶乘的C语言程序。

由于阶乘的结果会呈几何级数增长，在32位计算机中，只能计算到13的阶乘，14的阶乘结果就超过32位二进制的表示。即使是在64位字长的计算机中，能表示的数据大小也是有限的，只能保存20的阶乘。

如果需要求很大的数的阶乘（例如求1000的阶乘），就不能简单地使用第1章中介绍的阶乘程序来进行运算了。

如何超越计算机变量的取值范围来计算阶乘？这就需要考虑编写出能处理大整数的函数（在C# 4中已要提供了大整数功能），才能计算更大数的阶乘。由于篇幅所限，这里不单独编写大整数的函数，而是提供另外一种相对简单的求大数阶乘的方法。

这种思路就是：考虑将多位数相乘化解为一位数相乘，例如，11的阶乘为39916800，若需要求12的阶乘，则需要将39916800与12相乘，按手工计算乘法的竖式方法，可用2与39916800相乘的结果加上用1与39916800相乘的结果，然后再将结果相加，得到12的阶乘，如图3-6左图所示。由于前一数的阶乘的结果很大，按左图的方式计算也很容易导致溢出。根据乘法交换律，可以将左图所示算式转换为右图所示算式，这样，每次计算的结果就不容易出现溢出。

按图3-6所示的思路，定义一个数组，使数组的每一个数组元素保存阶乘的一位结果（如图3-6右图所示中，11的阶乘结果为8位，就用数组中的8个数组元素分别保存这8位）。当要计算12的阶乘时，可按以下步骤进行计算。图3-6乘法竖式（1）用12去乘以数组中的每个元素，并将结果保存到原来的数组元素中。（2）判断每个数组元素中的值是否大于9，若大于9则进行进位操作。通过进位操作，使数组中每个元素保存的值都只有一位数。

具体操作过程如图3-7所示。图3-7

通过这种方式，就可以计算出计算机整型变量所能表示数据的十分之一这么大的数的阶乘了（因为数组中保存的是0～9中的1位数，而为了使结果不超过整型变量表示范围，与数组中各元素相乘的数据只能是计算机整型变量所能表示数据的十分之一）。

按这种思路，编写能计算较大整数阶乘的程序，具体代码如下：

执行以上程序计算1000的阶乘，可得到如图3-8所示的结果。从结果中可看到，1000的阶乘共有2568位。图3-8

3.2.2 阶乘的递归计算方法

从前面的运算过程可看出，阶乘是一个规模比较大的问题，这时可考虑通过递归的方式来计算阶乘。

在定义递归算法时，需要考虑3个方面的问题。

首先，每一次递归调用，处理问题的规模应有所缩小，在阶乘中可以做到，如求n的阶乘，可将其分解为如下形式：

由上式可看到，n的阶乘可分解为n乘以（n-1）的阶乘，而（n-1）的阶乘又可分解为（n-1）与（n-2）的阶乘。

这样，每次运算就可将问题的规模缩小。

其次，在定义递归算法时，相邻两次递归调用之间有紧密的联系，前一次为后一次递归调用做准备。在上式中可看到，n的阶乘分解后，下一次递归调用时的输入就为（n-1）。

最后，在问题的规模极小时，必须直接给出解答而不再进行递归调用。在阶乘的递归算法中，计算到最后，求0的阶乘时，就不用再递归，直接返回其结果为1即可。

根据上面的分析，可用以下方式定义阶乘的递归算法。

根据以上定义，可用C语言编写出如下递归计算阶乘的程序。

可以看出，这个程序比第1章中编写的阶乘程序简单。

3.2.3 递归的过程

要理解递归，首先应了解一种数据结构：堆栈（简称栈）的概念。

栈是一个后进先出的压入（push）和弹出（pop）式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向上移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出，然后栈指针向下移动一个位置。

C编译器处理函数调用时，就是使用栈来保存数据的。当主调函数调用另一个函数时，C编译器将主调函数的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。

当进行被调函数时，编译器将栈中的实参数据弹出，赋值给函数的形参。在被调用函数执行期间，还可利用栈来保存函数执行时的局部变量。当被调用函数准备返回时，系统将弹出栈中所有当前函数压入栈中的值，这时，栈指针移动到被调用函数刚开始执行时的位置。接着被调用函数返回，系统从栈中弹出返回地址，主调函数就可以继续执行了。

如图3-9所示就是计算机中栈的示例，左图所示是“函数1”调用“函数2”的情况，在调用“函数2”时，计算机将“函数2”的返回地址压入栈中，接着将函数参数压入栈中。而右图显示“函数2”调用结束返回“函数1”后的情况，这时“函数2”中的参数、返回地址都从栈中弹出。图3-9

栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由系统自动处理。

递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的备份，这些备份和函数的其他执行过程毫不相干。这种机制是大多数程序设计语言实现子程序结构的基础，使得递归成为可能。

假定某个主调函数调用了一个被调用函数，再假定被调用函数又反过来调用了主调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的主调用函数、现在的被调用函数在栈中处于较低的位置，有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。

书归正传，回到阶乘的递归算法上来。假设要计算5的阶乘，通过前面设计的递归程序执行过程如下。

首先，在main()函数中调用fact()函数，将返回地址、参数、局部变量压入堆栈，如图3-10所示。

在fact()函数中，判断n的值若不为0，则递归调用fact(4)，这时将函数的返回地址和参数压入堆栈，如图3-11所示。

将程序继续递归调用时，将fact(3)、fact(2)、fact(1)逐步压入堆栈，如图3-12所示为将fact(0)压入堆栈后栈的结构。图3-10图3-11图3-12

当调用fact(0)时，达到阶乘递归算法的结束条件，这时结束fact(0)函数调用，从堆栈中弹出该层的相关数据，并返回函数的结果1。这时栈顶中保存的将是fact(1)中的相关数据，如图3-13所示。图3-13

当递归函数逐层返回时，栈中压入的数据将逐步弹出，当弹出fact(4)后的栈结果如图3-14所示。图3-14

当函数fact(5)返回时得到5的阶乘等于120，同时从栈中弹出调用函数时的数据，完成整个递归调用。

3.2.4 递归的本质：缩小问题规模

递归式解决逻辑问题的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。

用递归处理问题的过程，就是将问题规模逐步缩小的过程。

例如，在阶乘的递归运算中，就是将一个较大数的阶乘逐步缩小为一个较小数的阶乘，直到缩小到求0的阶乘为止。

在上节的例子中，用递归求解最大公约数的方法也同样如此，利用辗转相除法，在递归调用过程中逐步将被除数、除数缩小。

因此，在解决问题时，如果可以明确地将求解问题规则逐步缩小，就可考虑用递归算法来实现。

利用递归算法编写的程序代码更简洁清晰，可读性更好。有的算法用递归表示比用循环表示简洁精练，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法，如八皇后问题、汉诺塔问题等。有的算法用递归能实现，而用循环却不一定能实现。

但是，也需要注意递归算法一个明显的缺点，每次递归调用时，需要将返回地址、参数等数据压入堆栈，也就是说，递归的内部实现要消耗额外的空间和时间。如果递归调用的层次太深，就可能导致堆栈溢出，从而使程序执行出错。

3.3 汉诺塔

汉诺塔问题是程序设计中的经典递归问题。

汉诺塔（又称河内塔）游戏是一个非常著名的益智游戏玩具，现在市面上卖的这个玩具外形如图3-15所示，这个游戏是从一个古老的传说演化而来。图3-15

3.3.1 古老的传说

相传在印度的贝纳雷斯，有座大寺庙，寺庙中有一块红木板，上面插着三根钻石棒，在盘古开天地，世界刚创造不久之时，神勃拉玛便在其中一根钻石棒上，放了64枚纯金的金片（圆盘），最大的圆盘在最底下，其余一个比一个小，依次叠上去。有一个叫婆罗门的门徒，不分日夜的向这座寺庙赶路，抵达后，就尽力将64枚纯金的圆盘移到另一根钻石棒上，在移动过程中，一次只能移动一个圆盘，且圆盘在放到钻石棒上时，大的不能放在小的上面。可利用中间的一根钻石棒作为辅助移动用。等到婆罗门完成这项工作，寺庙和婆罗门本身都将崩溃，世界将在一声霹雳中毁灭。

那么，世界毁灭会在哪一天呢？

经过计算，需要移动圆盘的次数是一个天文数字18,446,744,073,709,551,615（64个圆盘需要移动的次数为2的64次方）。假设1微秒进行一次移动，也需要约60万年的时间！当移动一个圆盘需花1秒钟时，完成所有圆盘的移动需要近6000亿年！何况移动一个圆盘的时间肯定不止1秒。

离世界毁灭还早得很，人们就根据这个传说演变成汉诺塔游戏，这个游戏的规则是：

□ 将左侧柱子中从小到大放置的8个圆盘移到右侧的圆柱上。

□ 每次只能移动一个圆盘。

□ 小的圆盘只能放在大的圆盘之上。

□ 可以借助另一个圆柱进行辅助移动。

那么，这个游戏该怎么玩呢？

假设有8个圆盘，如图3-16所示，将A柱中的最小圆盘移到C柱，再将A柱中第2个圆盘移到B柱。图3-16

接下来该怎么办呢？又该怎么移动其余的圆盘呢？

3.3.2 从两个盘考虑

如图3-16所示的8个圆盘，移动起来就很麻烦，更别说64个圆盘的移动了。那么，我们先将问题简化一下，从两个圆盘开始考虑。即将A柱中的两个圆盘移到C柱，这个问题就简单了，如图3-17所示，共分3步即可完成任务：（1）从A柱将小圆盘移到B柱。（2）从A柱将下方大圆盘移到C柱。（3）从B柱将小圆盘移到C柱，完成。

好，两个圆盘的移动通过3步就解决了，那么如果要从A柱移动3个圆盘到C柱又该怎么办呢？

由于已经知道将两个圆盘移动到另一个柱子时需要3个步骤，因此，这时就可以不再考虑两个圆盘的移动了。图3-17

这时，可考虑将两个圆盘的移动看作一个整体，即A柱的3个圆盘中上面的两个圆盘看作为一个圆盘，下方最大圆盘作为一个圆盘，则3个圆盘的移动又可化解为两个圆盘的移动。这样，只需要3个步骤就可完成移动，如图3-18所示。图3-18

在图3-18中有以下3步：（1）将A柱中的小圆盘（由上方两个圆盘组成）移到B柱。（2）将A柱中的大圆盘（最下方的圆盘）移到C柱。（3）将B柱中的小圆盘（由上方两个圆盘组成）移到C柱，完成。

在上面的第（1）步和第（3）步中，是将两个圆盘打包移动的。但是，按规则一次只允许移动一个圆盘，这里只是假想一次移动两个圆盘，在实际移动过程中，第（1）步和第（3）步中的每一步最终还是必须分解为3个步骤。

因此，如图3-19所示，在第（1）步中将上面的两个圆盘从A柱移到B柱时，需借助C柱作为辅助柱来进行移动。而在第（3）步中将B柱中的两个圆盘移到C柱时，需借助A柱作为辅助来进行移动。

将各动作分解后，可以看出，将3个圆盘从A柱移动到C柱时需要7步（第（1）步分解为3个步骤，第（3）步分解为3个步骤，再加上第（2）步中的1个步骤）。图3-19

3.3.3 找出递归结构

经过上面的推算可看出，3个圆盘的移动需要7步，那么移动4个圆盘呢？与3个圆盘类似，对于4个圆盘也可分为3个大的步骤，如图3-20所示。图3-20（1）将A柱中的小圆盘（由上方3个圆盘组成）移到B柱。（2）将A柱中的大圆盘（最下方的圆盘）移到C柱。（3）将B柱中的小圆盘（由上方3个圆盘组成）移到C柱，完成。

接着第（1）步、第（3）步需要移动3个圆盘，移动的步骤分别为7步，则将4个圆盘从A柱移动到C柱需要7+1+7=15步。

对比图3-18和图3-20可以看出，如果不考虑第（1）步和第（3）步移动圆盘的数量，这两个图完全一样。也就是说，不管移动多少个圆盘，其实，移动的操作相似。

既然解决问题时具有相似步骤，并且可逐步缩减问题规模，就可考虑使用递归算法来求解。通过上面对移动3个圆盘和4个圆盘时的分析，可总结出汉诺塔的递归结构，对于移动n个圆盘的汉诺塔，可分解为3步，如图3-21所示。（1）移动（n-1）个圆盘。（2）移动第n个圆盘。（3）移动（n-1）个圆盘。

而“移动（n-1）个圆盘”又可继续分解，直至分解到只剩一个圆盘时，直接移动到目标柱为止。

根据图3-21所示的递归结构，可将汉诺塔问题的递归求解法分解为以下步骤。（1）如果只有一个圆盘，则把该圆盘从A棒移动到C棒，完成任务。（2）如果圆盘数量n>1，移动圆盘的过程可分为3步。图3-21（1）将A棒上的n-1个圆盘移到B棒上。（2）将A棒上的一个圆盘移到C棒上。（3）将B棒上的n-1个圆盘移到C棒上。

3.3.4 实现程序

将递归结构找出来以后，编写递归程序就很简单了，下面的代码就是用C语言编写的实现汉诺塔的递归程序。

在以上程序中，函数hanoi()是一个递归调用的函数。这个函数共有4个参数，第1个参数表示要移动的圆盘数量，第2～4个参数表示移动的源位置、临时位置、目标位置。例如，以下调用hanoi()函数的形式：

表示有h个圆盘要从A柱移到C柱，B柱作为临时辅助用的柱。

在递归调用时，需要搞清楚每次移动圆盘的源位置和目标位置。例如，若要将h个圆盘从A柱移到C柱，则需要将（h-1）个圆盘先从A柱移到B柱（借助C柱作为临时辅助），完成这个操作需按以下方式调用hanoi()函数：

接着将第h个圆盘从A柱移到C柱。

然后将临时放在B柱的（h-1）个圆盘移到C柱（借助A柱作为临时辅助），这时需按以下方式调用hanoi()函数：

执行以上程序，当输入4个圆盘时，移动圆盘的过程如图3-22左图所示，共需15次可完成任务。当输入6个圆盘时，移动圆盘的过程如图3-22右图所示，共需要63次可完成任务。图3-22

3.3.5 究竟需要移动多少次

根据我们前面手工推算移动次数，以及图3-22所示计算机程序运行得出的移动次数，可发现当需要移动的圆盘数量为1、2、3、4、5、6……时，移动圆盘的次数分别为：

可以看出，圆盘数量按自然数序列递增，但移动次数却呈接近倍数的方式递增：

按上面列表中计算的移动次数，每次都是在上一次移动次数的基础上乘以2再加1，如果要直接计算移动n个圆盘需要多少次移动，就需要逐个推算。其实，仔细分析上面的列表，可发现如下规律：

这样，当要移动64个圆盘，就需要：

3.4 斐波那契数列

3.4.1 兔子的家族

先来看著名斐波那契数列的例子：兔子家族。

意大利数学家列昂纳多·斐波那契在所写的《算盘书》中提出了下面的问题：

有小兔一对，如果它们第2个月成年，第3个月生下一对小兔，以后每月生产小兔一对，而所生的小兔亦在第2个月成年，第3个月生产另一对小兔，此后也每个月生一对小兔。问一年后共有多少对兔子（假设每产一对兔子必须为一雌一雄，而所有兔子都可以相互交配，并且没有死亡）。

要计算出一年后共有多少对兔子，没有公式可直接计算出来。根据题意，每月兔子的数量与上月兔子和上上月兔子的数量有很大关系，可通过前两个月的兔子数量推算出当月兔子的数量。

3.4.2 从最初几月数据中找规律

从第1个月开始向后推算：

第1个月，只有一对小兔子。

第2个月，小兔子成年，仍然只有一对兔子。

第3个月，有一对成年的兔子，成年的兔子生产一对小兔子，共有两对兔子。

第4个月，有两对成年的兔子，以及第3月1对成年兔子所生产的一对小兔子，共有三对兔子。

第5个月，有三对成年兔子，以及第4个月的两对成年兔子所生产的两对小兔子，共有5对兔子。

前面5个月兔子繁殖的过程如图3-23所示。图3-23

设F(n)表示第n个月兔子的总数，则图3-23所示各月兔子数量可用以下算式来表示：

按上面列出的算式，可以很快推导出1年（共12个月）后兔子的总数，具体算式如下：

也就是说，1年后兔子的总数为144对。

也可将各月的成年兔子与小兔子的数量制作成一个表格，如下所示。

各月兔子的总数量组成一个列表，如下所示。

3.4.3 斐波那契数列

在上面列出的兔子繁殖过程中，每月兔子的数量组成一个序列，这个序列就称为斐波那契数列。这个数列从第3项开始，每一项都等于前两项之和。在数学上，斐波那契数列可以用递归的方法来定义：

在上面的算式中F不是第一项，而是第0项，只是递归而定义的0一个结束项。

在前面计算兔子总数时，我们是从第1个月开始逐月向后推导，如果要计算的项n的数据很多，就需要很多个步骤进行推导。好在我们找到了斐波那契数列的递归定义方式，在上面的3个算式中，F的n值由F和F得出，而F和F又可由它们的前两项得出。也就是n-1n-2n-1n-2说，每次递归调用，都将问题规模缩小，当递归到第1项和第0项时，返回确定的值，这就可使递归调用结束。

只是，在这里的递归调用与本章前面例子中不一样，当计算第n项数据时，需要递归调用（n-1）项和（n-2）项。

根据以上分析，可用C语言编写如下程序计算出斐波那契数列中的前n项数据：

执行以上程序，输入12，表示生成12项斐波那契数列，得到如图3-24所示的结果。图3-24

使用上面的程序，用递归方式推导出第n项的斐波那契数，如果n的值很大，这个推导过程就比较繁琐。其实，用初等代数解法也可推导出计算第n项斐波那契数的公式，具体推导过程这里就不列出来了，具体计算公式如下：

通过上面的公式就可以计算第n项斐波那契数。

如果觉得以上公式计算起来还是比较麻烦的话，可以使用以下公式得到一个大约数值：

例如，若取n=12，则：

3.4.4 神奇的魔八方

最后，来看一个斐波那契数在魔术中的应用：“魔八方”。

一位魔术师拿着一块边长为8分米的正方形地毯，对观众朋友说：“我能把这块地毯分成4小块，再重新缝成一块长13分米，宽5分米的长方形地毯，你相信吗？”

观众中有人开始计算了：边长8分米的正方形，其面积为64平方分米；而边长13分米，宽5分米的长方形，其面积为65平方分米。两者面积相关1平方分米，肯定不行啊。

魔术师之所以称为魔术师，肯定有他的绝活，结果他还真的拼出了长13分米、宽5分米的地毯。如图3-25所示，就是魔术师的裁剪及拼接过程，左图将正方形裁剪成了4部分，右图是由这4部分拼接而成。图3-25

为什么经过一裁一拼，地毯的面积就增加了1平方分米呢？为了分析这个问题，将图3-25右图所示的长方形以左下角为原点制作一个坐标系，如图3-26所示。图3-26

在图3-26所示坐标系中，O点为原点，则A点的坐标为（50，20），B点的坐标为（80，30），则∠AOC的正切为2/5，而∠BOC的正切为3/8，显然OA与OB不在一条直线上。也就是说，实际上后来缝成的地毯有条细缝，面积刚好就是1平方分米。

那么，是不是所有正方形都可以进行这种方式的变化呢？

先来计算一下，设边长为n的正方形是否可以进行这种魔八方的变化。

根据图3-25所示的裁剪和拼接方式，可知道拼接后的矩形的长度为：

由于拼接后的长方形面积比正方形的面积多1，则可得到以下公式：

设：

代入上面的方程，可得到如下方程：

对于这个二元二次方程，由于只有一个方程式，属于不定方程，将这个不定方程中的x、y的值求出来，即可得到正方形的边长。对于不定方程，我们可以先计算出y的值在100以内时的各种整数解，如下表所示。

可以看出，x、y的值构成了斐波那契数列：1、2、3、5、8、13、21、34、55、89、……，也就是说，正方式的边长n应为斐波那契数列的前两项之和。例如，边长为8、13、21这些正方形都可以按魔八方的形式对图形进行裁剪和拼接，以使其面积增大。

第4章 排列组合——让数选边站队

所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。

4.1 把所有情况都列出来

数学是我们日常生活中不可或离的知识，例如，购买商品的价格、数量，接待来访客户的数量，与客户签订合同的数量和金额等，这些都用了到最基本的数学知识计数。

计数，是我们从幼儿园、小学就开始学习的最基本数学知识，可是，到现在为止，你会计数吗？能正确的计数吗？

4.1.1 从0还是1开始

计数还会出错？好吧，那我们来看一个例子。

小张每天从家里到办公室去上班乘坐地铁都要购买3元的票，再多坐一站都需要购买4元的票（根据当地地铁公司的票价规定，乘坐10个区间的票价为3元）。请问，小张早上去上班要路过多少个车站？

你可能觉得这太简单了吧，这也是一个问题？

根据题意，小张购买的是3元的车票，再多坐一站都要购买4元的车票，说明小张坐的车站是3元内的最多车站数，即10站。

所以，小张早上上班路过的车站是10个站。

可是，这个答案却是错误的！

正确的答案应该是要经过11个车站。为什么是这样呢？看图4-1就可得到答案。

在图4-1中，经过的区间用圆圈中的数字表示，经过的车站的编号用下方的数字表示。从图中可看到，小张从地铁站Home出发，经过10个区间到达Office站，包括Home站在内，一共经过了11个地铁站，其中Home的编号为0。

这是从0开始计数的表示方式，与我们平常从1开始计数有些不同，所以很多人都容易在这里犯错。图4-1

对于从0开始计数的情况，最后的数据数量应是计数值加上1，即：

其实，从0开始计数这种方式程序员应该是比较熟悉的，在C、Java等流行的程序设计语言中，数组的下标都是从0开始计数，例如，有以下C语言程序：

执行以上C语言程序，可得到如图4-2所示的结果。图4-2

从图4-2所示的执行结果可看到，数组元素的序号从0开始，程序中定义的数组具有10个元素，其序号为0～9。

因此，如果是以0开始计数，要注意：

4.1.2 赛程安排

赛程安排也是一个计数问题。

在比赛的赛程安排中，不能漏掉参赛的每一位选手，也不能为某一位选手安排重复的比赛。这就是计数中需要解决的两个问题：遗漏和重复。

某学校举行乒乓球比赛，在初赛阶段设置为单循环赛，设有n位选手参赛，每位选手要与其余每位选手进行一场比赛，然后按积分排名选拔进入决赛的选手。这个比赛的赛程应该怎么安排呢？

为了简化，先以5位选手参加比赛为例来进行分析。

首先，每位选手都要与其余的每位选手进行一场比赛，制作一张二维表，将参赛选手分别排在行和列中。在纵横方向上都可以设置与之进行比赛的选手，得到如图4-3所示比赛对阵表。图4-3

在图4-3所示的比赛对阵表中，选手自己不能与自己比赛（如甲与不能与甲进行比赛），因此，图中显示的比赛总场次为：

可是，看图4-3还可发现一个问题，每位选手进行了两场比赛。例如，从行方向来看，第1行中，甲与乙进行了一场比赛，在第2行中乙与甲也进行了一场比赛。如果甲与乙进行比赛、乙再与甲进行比赛，甲、乙两位选手就进行了两场比赛。其他选手的比赛场次也与此相同。

这样，就出现了计数中的“重复”问题，即某一现象被重复计数。

根据比赛规则，每一位选手只能与其余的每位选手进行一场比赛。因此，选手对阵表应如图4-4所示，这时只考虑右上角那些打对勾的比赛场次就行了。图4-4

从图4-4中可看到各选手与对手的比赛场次：

即，比赛的总场次为：

经过10场比赛，各选手都与对手进行了一次单循环比赛，没有遗漏，也没有重复。

从上面的算式中提取相应的规律，对于有n位选手参加的单循环比赛，需要举行的比赛总场次为：

例如，有5位选手参赛，则比赛的总场次为：

若有10位选手参赛，则比赛的总场次为：

4.2 乘法原理

在实际应用中，要将所有情况都列出来，经常要用到乘法原理和加法原理。下面先来看看乘法原理的应用。

4.2.1 行程安排的问题

在日常生活中常常会遇到这样一些问题，就是在做一件事时，要分几步才能完成，而在完成每一步时，又有几种不同的方法。要知道完成这件事一共有多少种方法，就需要用乘法原理来解决。

例如：某公司销售部王经理从重庆到成都参加西南片区的销售会议，之后再到北京参加全国销售会议。其中，他从重庆到成都可以乘长途汽车、火车或飞机，从成都到北京可以乘火车或飞机。那么，王经理从重庆经成都到北京共有多少种不同的走法？

分析这个问题发现，王经理从重庆到北京要分两步走，第一步是从重庆到成都，可以有3种走法，即：

第二步是从成都到北京，有两种走法，即：

所以，王经理从重庆经成都到北京共有下面的6种走法：

在上面讨论问题的过程中，我把所有可能的办法一一列举出来，这种方法叫穷举法。穷举法对于讨论方法数不太多的问题是很有效的，但是如果每一步中的方法数很多时，需要重复列出很多项目，费时费力，还容易出错。例如，在上例中，如果从重庆到成都有10种（或20种走法），从成都到北京又有10种（或更多）的走法，要将每种走法列举出来，将是比较繁琐的事。

4.2.2 乘法原理适用条件

为了解决穷举法比较繁琐的这个问题，可以对上例的行程问题做一番总结，从中提出相应的规律，以方便解决类似问题。

上面的例子中，完成一件事要分两个步骤，由穷举法得到的结论可看出，用第1步所有的可能方法数乘以第2步所有的可能方法数，就是完成这件事的总方法数。

一般地，如果完成一件事需要n个步骤，其中，做第1步有M1种不同的方法，做第2步有M2种不同的方法，做第3步有M3种不同的方法……，做第n步有Mn种不同的方法，那么，完成这件事一共有N种方法，由各步的方法数相乘而得到。

这就是乘法原理。

哪些情况下适用乘法原理？

乘法原理的核心就是分步：每步都只完成其中的一部分，只有每一步都完成了这件事才算完成。分步计数时应注意步与步之间的连续性和独立性，以确保在计数时不遗漏不重复。

因此分步完成的任务可适用乘法原理，有些问题可能需要仔细分解一下才能化解为分步完成的结构。

4.2.3 棋盘上棋子的放法

再来看一个例子。如图4-5所示是一个4×4方格的棋盘，要在该棋盘中放4枚棋子，使每行每列只能出现一个棋子，问：共有多少种不同的放法（图4-5是其中一种放置棋子的方法）？

由于4枚棋子要一个一个地放入棋盘的方格内，因此可看成是分4步解决这个问题。（1）放置第1枚棋子。此时由于16个棋盘方格都没有棋子，因此，这枚棋子可放在任意一个方格中，有16种不同的放法，如图4-6所示。图4-5图4-6（2）放置第2枚棋子。由于棋盘中已经放置了1枚棋子，放第1枚棋子那一行和一列中的其他方格内也不能放第2枚棋子，因此还剩下9个方格可以放第2枚棋子，即第2枚棋子有9种放法，如图4-7所示。图4-7（3）放置第3枚棋子。这时需去掉第1、2枚棋子所在的行和列的方格，还剩下4个方格可以放置第3枚棋子，则第3枚棋子有4种放法，如图4-8所示。图4-8（4）放第4枚棋子。由于要去掉前3枚棋子所在行和列的方格，只剩下1个方格可以放第4枚棋子了，因此第4枚棋子只有1种放法，如图4-9所示。图4-9

根据上面的分析，用乘法原理即可求出4枚棋子的放置方法数量，共有：

种不同的放法。

4.2.4 买彩票保证中奖的方法

接下来说一个轻松的话题，说说用乘法原理来计算彩票的问题。

目前我国有福利彩票和体育彩票两大类，为国家的福利和体育事业做出了贡献。民众购买彩票为相关事业做出贡献，也有可能中奖改善自己的生活。

作为购买彩票的民众来说，肯定是希望自己能中大奖，那么，该怎么买彩票才能确保中奖呢？

由于彩票中奖号码是由摇奖机随机生成的，没办法猜中，因此，要确保中奖，只有将所有彩票号码全部买完没有遗漏，才可确保中奖！

那么，所有彩票号码共有多少种可能？要花多少钱才能买完？这就需要我们用乘法原理将所有可能都计算出来。

例如，对于体育彩票中的“七星彩”，其游戏规则是：彩票号码长度为7位，每位数字为0～9中的一个。那么，七星彩的彩票号码有多少种可能？

如图4-10所示，绘制7个方框用来填写彩票号码。图4-10

由于有7个号码，可以认为是分7个步骤来生成彩票号码。（1）填第1位号码。可以有0～9这10个数字可用，共10种可能。（2）填第2位号码。可以有0～9这10个数字可用，共10种可能。（3）填第3位号码。可以有0～9这10个数字可用，共10种可能。（4）填第4位号码。可以有0～9这10个数字可用，共10种可能。（5）填第5位号码。可以有0～9这10个数字可用，共10种可能。（6）填第6位号码。可以有0～9这10个数字可用，共10种可能。（7）填第7位号码。可以有0～9这10个数字可用，共10种可能。

根据乘法原理，七星彩的号码总数共有：

对于七星彩来说，由于各位数字允许相同，因此计算起来很简单。全部七星彩号码有1000万个，将这1000万个号码全部买完可保证中特等奖。

试读结束[说明：试读内容隐藏了图片]

下载完整电子书