前言

2006年3月，美国卡内基·梅隆大学计算机科学系主任周以真（Jeannette M. Wing）教授在美国计算机权威期刊《Communications of the ACM》上首先提出了“计算思维”（Computational Thinking）的概念。周教授认为：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。她还认为，计算思维是每个人的基本技能，不仅属于计算机科学家。我们应当使每个学生在培养解析能力时不仅掌握阅读、写作和算术（Reading, wRiting and aRithmetic，3R），还要学会计算思维。正如印刷出版促进了3R的普及，计算机也以类似的正反馈促进了计算思维的传播，计算机逐渐成为了当今问题求解的最重要工具。

1．计算机与问题求解

在20世纪40年代，为了求解军事领域复杂的炮弹弹道计算问题，科学家发明了第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer）。随着计算机计算能力的增强，计算机被广泛应用到了社会生活的各个领域。大到宇宙探测、基因图谱绘制，小到日常工作、生活娱乐，无不需要计算机的支持。

作为“问题求解的一个有力工具”，计算机尽管没有思维，只能机械地执行指令，但它运算速度快、存储容量大、计算精度高。如果能够设计有效的算法和程序，充分利用这些优点，计算机就能成为问题求解的一个利器。

（1）运算速度快是计算机最重要的特点之一

很多问题尽管比较复杂，但仍然存在求解的方法，只是这些方法往往计算量比较大，计算过程较为繁杂，人们难以在可以接受的时间内手工求解。

如用1, 2, 3, 4, 5, 6, 7, 8, 9九个数字拼成一个九位数，每个数字使用一次且仅用一次，要求得到的九位数的前3位、中间3位和最后3位构成的三位数的比值为1∶2∶3。192384576就是一个符合该要求的数，因为192∶384∶576 = 1∶2∶3。

对于这样的问题，很容易想到的一个求解方案是：列举所有可能的九位数123456789……987654321，并逐个验证是否符合比值要求。理论上，这是一个可行的办法，可是几乎没有人愿意这样做。因为这样的九位数总共有9! = 362880个，即使每秒验证一个数（对于人工验证，这已经是很快的速度了！），也需要100多个小时。

但是，计算机实现同样的“笨方法”效果就大不一样。考虑用一个数组d保存九位数的各位数字，x,y,z分别代表前三位数、中间三位数和最后三位数，用STL（Standard Template Library）中的函数next_permutation计算九个数字的下一个排列。当某个排列（也即是一个九位数）满足比例要求x:y:z=1:2:3时，则输出该九位数。下面是解决此问题的C++代码，在普通的计算机上运行该程序，需要的时间还不到0.1秒。

（2）存储容量大是计算机的另一个重要特点

人们很容易记住10以内两个数的乘积，也就是小学数学中的“九九乘法表”。如果要求人们记住100以内的任意两个数的乘积，普通人可能会觉得“记忆”不够。但对于计算机来说，这就是“小菜一碟”，一个100×100的二维数组就可以把“百百乘法表”保存下来。

人们常说的内存、硬盘、光盘、U盘等都是存储器，可以通俗地理解为计算机的记忆部件。容量的基本单位是字节（Byte，简称B），其他单位有KB（1KB=1024B）、MB（1MB=1024KB）、GB（1GB=1024MB）等。容量越大，可以存储的数据就越多，其记忆力就越强。“百百乘法表”如果用一个100×100的二维int型（假设一个int型整数占2字节）数组保存，它仅需要占用20 000字节（少于20KB）的空间。相比现在计算机动辄数GB的内存容量来说，“百百乘法表”的存储开销有点微不足道。

需要特别指出的是，运算速度快、存储容量大仅仅是计算机硬件系统的两个突出特点。在实际问题求解过程中，只有硬件平台远远不够，人们需要针对问题设计不同的算法，并把算法转化为计算机可以运行的程序。

2．计算机问题求解的知识体系

计算机问题求解的本质是把特定领域中特定问题的求解过程转换为一个计算机可以执行的程序。在这个转换过程中，除了必要的领域专业知识，问题求解者还需要掌握计算机算法设计方面的知识，主要包括：高级程序设计语言、数据结构和算法。这些知识构成了计算机问题求解的核心知识体系。

在计算机教学体系中，“高级程序设计语言”“数据结构”和“算法”是相互承接的课程。从计算机问题求解的角度看，这三门课程的知识相互交叉、相互支撑。高级程序设计语言和数据结构是算法设计的基础，高效的算法和数据结构需要用某种高级程序设计语言去实现；一个好程序不仅需要“编程技巧”，更需要合理的数据结构和高效的算法。

程序设计语言是问题求解的基本工具。随着计算机技术的发展，程序设计语言经历了一个从低级程序设计语言到高级程序设计语言的发展历程。机器语言和汇编语言等面向特定的体系结构和指令系统，在计算机发展的早期应用较多。随着形式语言理论、编译技术的发展，与目标机器无关的高级程序设计语言（如C/C++、Java等）逐渐成为程序设计的主流。本书约定的程序设计语言是C/C++。需要注意的是，程序设计语言并不等于程序设计，程序设计的目的是表达程序设计者的思想，按照计算机能理解的方式描述需要让计算机完成的工作，而程序设计语言只是表达这种思想的工具。程序设计的关键之处在于明确数据在计算机中的表达形式，以及确定如何将输入转化为输出的一系列计算步骤，而这些都需要数据结构和算法理论的指导。

数据结构是问题求解的基础要素。数据是信息的载体，无论是待求解问题的输入/输出，还是问题求解过程中产生的中间量；无论是简单的量（如单个数值），还是复杂的对象，它们在计算机中都是以数据的形式存储的。在问题求解时，为满足数据存储的结构化要求并提高程序执行效率，人们首先面临的问题是怎样合理地组织、存储和加工这些数据。常用的数据结构有线性表、栈、队列、树、图、哈希表等。数据结构的设计和应用不是一个教条化的过程，同一个问题也许可以运用不同的数据结构求解，而且它们求解的效率往往不一定相同。另外，有些问题可能没有现成的数据结构直接套用，需要人们综合运用基本数据结构组合成新的数据结构。无论是已有数据结构的选择还是新数据结构的设计，人们都需要应用算法设计方面的知识。

算法设计是问题求解的关键要素。简单地说，算法可以理解为将问题输入转化为问题答案的一系列计算步骤。算法必须满足正确性和复杂性要求。首先，算法执行结果必须正确，它能正确无误地把每一个问题实例的正确答案求解出来。其次，算法的复杂度要适中。计算机系统的资源（包括运行时间和存储空间）是有限的，因此算法必须在有限的资源条件下正确地求解问题。同样的问题，某些算法执行结果可能不正确，某些算法执行结果正确无误。即使执行结果都正确的不同算法，它们的执行效率可能也不尽相同，如有些算法需要几个小时，甚至几天，有些算法仅仅需要几秒或几分钟。算法设计是一个灵活的、创造性的过程，甚至可以认为是一个艺术创造过程。有些算法是现实生活中人们解决问题时所用办法的升华和抽象，有些算法是数学理论和数学模型的体现及具体化。人们需要掌握经典的算法思想及其应用技巧，也要学会怎样针对特定问题设计和创造新算法。

3．本书的内容和结构

本书是一本介绍怎样综合运用算法设计理论和技术进行问题求解的实用性教材，主要介绍算法设计原理和方法，同时对运用算法求解问题时涉及的C/C++程序设计细节，尤其是影响算法准确性和复杂性的编程要点和技巧也进行了详细阐述。数据结构往往是算法设计和实现的基础，特别是一些高级数据结构本身就体现了很强的算法思维，因此本书不仅单独设立了“程序设计语言与数据结构”一章介绍数据结构，在介绍具体算法时也会交叉讨论相应的数据结构知识。本书包括7章，组织如下。

第1章介绍计算机问题求解和算法的基本概念，然后着重阐述算法复杂度分析的基本理论和方法。

第2章介绍程序设计与数据结构相关内容。程序设计和数据结构是算法设计的重要支撑，本章重点介绍程序设计的三个盲点，以及常用的基本数据结构及其用法。

第3章介绍枚举算法。“大道至简”，枚举算法是一种最朴素、最简单的算法思想，但在具有卓越运算速度的计算机系统中，它却是常常被忽视的问题求解利器。本章重点阐述怎样直接和间接运用枚举算法求解问题。

第4章介绍递归和分治。“凡治众如治寡，分数是也”，分治策略是分析和解决复杂问题最常用的策略之一。本章根据分治算法的求解步骤把分治策略归纳为三类，并结合具体实例阐述每类策略的设计思想、适用范围及实现要点。

第5章介绍动态规划。动态规划是最具有创造性的一种算法，归约、分治等思维方法都在动态规划算法框架中得到了很好的体现。本章重点讨论基于“划分”和“约简”策略的动态规划的原理和运用技巧。

第6章介绍贪心算法。这种类似“瞎子爬山”的策略如果运用适当，能够快速地产生最优解。本章将给出一些典型的贪心算法问题，并探讨贪心算法的正确性证明。

第7章介绍搜索技术。搜索是求解一些难解问题的常用策略，它把问题求解转换为状态空间图中的路径探索过程，究其本质，搜索是一种枚举和优化策略的综合算法。“运用之妙，存乎一心”，本章以典型问题为例介绍5种经典搜索策略的原理、适用范围及实现要点。

为便于教学和读者自学，本书提供有适用于理论教学的课件以及实践学习的配套平台——“北京交通大学在线程序评测系统”（http://algo.bjtu.edu.cn，简称BOJ）。BOJ是一个公益性质的计算机问题求解实践平台，也是本书的配套网站。本书的例题和习题都以专题的形式加入BOJ题库中，读者在学习本书时，可登录该系统进行编程求解和自我评测。

作 者