本章将介绍一些基本的编程原理，它们是应对复杂的大型程序的基础。在学习这些原理时，可以了解到，设计优秀、文档记录完整的程序具有成本效益。本章还简要介绍算法和数据抽象，讨论它们与作为本书主题的问题求解和编程技术的关系。后续各章将从编程原理转向介绍数据的组织和使用方式。在学习这些新技术时，您将看到，本章的原理是开发所有解决方案的基础。

2.1  问题求解与软件工程

在上次编写程序时，您是从哪一步开始的？大部分编程新手仅花一点儿时间读一读问题描述，就开始编写代码。他们的目标很明确：使程序能够执行，并能够得到预期的结果。于是，他们运行程序、分析错误消息、插入分号、更改代码逻辑和删除分号等，反复处理，直到程序开始工作。大部分时间都耗费在检查语法和程序逻辑上。虽然这样做也能逐步提高编程技术，但能开发出大型软件吗？也许会，但不是最优的方法。

要知道，大型软件开发项目通常需要一个编程团队的参与，一个人是无法完成的。团队工作需要进行总体规划、组织与交流。如果软件开发随意而为，团队的成员将无法正常工作，而且会增加成本。软件工程的出现解决了这些问题。软件工程是与计算机科学相关的工程学科，有利于计算机程序的开发工作。

本章将首先概述问题求解过程，以及处理问题的各种方式。

2.1.1  问题求解的含义

这里的“问题求解”指描述问题，以及开发计算机程序来解决问题的整个过程。这个过程包含多个阶段，如理解待解决的问题、设计概念化的解决方案，以及用计算机程序实现解决方案。

“解决方案”的准确含义是什么？解决方案通常由“算法”和“数据存储方式”两部分组成。“算法”是对在有限时间内求解问题的方法的分步描述。算法经常在数据集合上执行操作。例如，算法常常给集合添加新数据、从集合中删除数据，或针对数据集合提出若干问题。

解决方案的这种定义可能造成错觉：问题求解技术主要表现在算法上，而数据存储方式只起辅助作用。实则不然，我们需要做的决不是简单的存储数据。在构建解决方案时，必须组织数据集合，从而按算法要求的方式操作数据。实际上，本书主要讲述的是数据组织方法。

在为给定的问题设计解决方案时，可通过几种技术来简化任务。本章简要介绍这些技术，后续各章将进一步阐述它们。

2.1.2  软件的生命周期

软件开发是一个漫长、连续的过程，称为“软件生命周期”。该过程以初始规划为始，接着是程序的编写和调试，最后修改和增强初始软件版本(可能持续数年)。图2-1将软件生命周期的9个阶段比作为水轮的9个部分1。可以看到，各个阶段将循环往复地进行，而不是线性的。软件生命周期的起点是问题描述，但开发过程一般可以从一个阶段转到其他任何阶段。例如，在测试程序时，可能需要更改问题的描述，或需要更改解决方案的设计。注意，这9个阶段以文档记录(documentation)为核心。文档记录不是一个独立的阶段，它贯穿于软件生命周期的所有阶段。

图2-1  软件生命周期就像一个水轮，可从一个阶段转到其他任何阶段

在过去几年，出现了递增、迭代式的开发方法。这些方法以循环方式，逐步应用软件生命周期的前七个阶段：问题描述、设计、风险分析、验证、编码、测试和完善。完善阶段要考虑下一步对系统进行什么修改（或完善），从而使开发工作返回到问题描述阶段。采用这种方式，需要先开发整个系统的一部分，再组合对解决方案的完善部分。系统一旦开发好，就可以进入生产和维护阶段。在使用Java等面向对象的语言时，最初的开发工作是构建对象的一个子集，再逐步改进这些对象，添加新对象，直到系统开发完成，能用于生产为止。

下面将讨论典型软件生命周期的各个阶段。所有阶段都很重要，但由于篇幅所限，此处仅详述与本书关系最密切的阶段。

1. 第1阶段：问题描述

在初步描述软件的目标后，必须明确阐明问题的所有方面。描述问题的人不一定是编程人员，所以最初的问题描述不见得准确。在此阶段，必须对最初的问题描述进行准确的定义和详细的说明，并与编程人员和非编程人员广泛交流。

在编写软件的规范时，必须回答以下问题：输入什么数据？哪些数据有效，哪些数据无效？软件的使用者是谁？选择什么形式的用户界面？要求进行什么错误检测，显示什么错误消息？有什么假设？有特例吗？选用哪种输出形式？需要哪些文档记录？未来要对软件进行哪些改进？

原型程序(prototype program)可模拟软件产品的部分预期行为。通过编写原型程序，可以加强与用户的交流，阐明软件的问题描述。例如，即使是一个简单(甚至低效)的程序也能显示需要的用户界面，这有助于分析问题。此时发现难点或改变思路，要比开始或已经完成编程时再改变的代价小得多。

编程任务可能已经给出了程序的问题描述。但这些问题描述的某些方面可能并不清晰，还需进一步阐明。编程新手对如何编写程序的问题描述没有任何经验，所以需要多加琢磨，逐步提高自己的能力。

2. 第2阶段：设计

完成了问题描述阶段后，就要设计问题的解决方案了。在设计中等规模和中等复杂程度的解决方案时，很难一次性处理整个程序。要简化问题求解过程，最好将一个大问题分成若干个可以控制的小问题。最终程序将包含多个模块（即自包含的代码单元）。

如果使用Java这样的面向对象语言，这些模块的形式就是对象。如第1章所述，对象是利用类实现的。在设计类时，应使对象是独立的或松散耦合的。耦合用来说明程序中的哪些对象是相互关联的。如果程序中的每个对象都与其他对象关联，则称为强耦合。这意味着，对象间的信息流很大。如果对象是松散耦合的，那么一个对象中的变化对程序中其他对象的影响将很小。

在设计类时，还应使对象是强聚合的。聚合用来说明对象中的哪些数据和方法是相互关联的。理想情况下，每个对象都应表示解决方案中的一个组件。对象中的方法也应该是强聚合的，都应执行一个定义好的任务。

在设计阶段，还应明确指定对象之间的交互操作。对象交互的方式是各个对象通过方法调用来传递消息，消息表示对象间的数据流。在设计方法时，应提供以下问题的答案：对象中的哪些数据可以由这个方法使用？这个方法假设什么条件？方法执行哪些操作？在方法执行之后，存储在对象中的数据有变化吗？换言之，需要详细指定每个方法的假设条件、输入和输出。

例如，程序设计人员若要为图形对象提供一个方法，将该对象移到屏幕的一个新位置，则可能编写以下问题描述：

方法将接收一个(x,y)坐标。

方法将图形移到屏幕的一个新位置。

可将上述描述看作方法与调用方法的代码间的“合约”。

如果独自完成整个程序，通过此合约，可将问题系统地划分为较小的任务。如果程序是一个团队项目，则合约有助于分清各个成员的责任。无论谁编写move方法，都必须遵守此合约。在编写和测试move方法后，合约通知程序的其余部分如何正确地调用move方法，并使其了解这么做的结果。

但要注意，方法的合约并未限定方法用什么方式执行任务。若程序的另一部分为该方法做了一些假设，则必须独立承担做这些假设所带来的风险，因为方法只执行预定的任务。例如，若后期重编方法，用另一种算法在屏幕上移动图形，就根本不必改动程序的其他部分。只要新方法遵守原始合约的条款，则程序的其他部分可以忽略这个更改。

对您来说，上述内容应该并不陌生，但您可能不大了解“合约”的含义。实际上，方法的初始条件(precondition)及结束条件(postcondition)就是合约。初始条件指方法开始时必须存在的条件描述，结束条件指方法结束时的条件描述。例如，遵循上述合约的move方法的伪码如下：

move(x, y)

// Moves a shape to a new location on the screen.

// Precondition: The calling program provides an

// (x, y) pair, both integers.

// Postcondition: The shape is moved to the new

// location.

实际上，这些初始条件和结束条件不够充分，只是一个合约初稿。如上例，“moved”的含义是什么？是相对于前一位置，将图形移动(x, y)？还是将图形移至新坐标位置(x, y)？x和y的值域如何？在实现该方法时，可能假设：“moved”指将图形移至新坐标位置(x, y)，x和y的值域是0到100。当某人试图通过move方法，使用(–5，–5)，相对于前一位置移动图形时，必然出现错误。这个用户不知道实现该方法的上述假设条件，除非修改了初始条件和结束条件，来记录这些条件，如下所示：

move(x, y)

// Moves a shape to coordinate (x, y) on the screen.

// Precondition: The calling program provides an

// (x, y) pair, both integers, where

// 0 <= x <= MAX_XCOOR, 0 <= y <= MAX_YCOOR, where

// MAX XCOOR and MAX YCOOR are class constants that

// specify the maximum coordinate values.

// Postcondition: The shape is moved to coordinate

// (x, y).

在编写初始条件时，首先描述方法的形参，然后说明该方法使用的类命名常量，最后列出该方法的假设条件。同样，在编写结束条件时，先描述该方法对形参的作用，对于值方法，要说明返回值；然后描述已发生的其他操作。

在面向对象的系统中，方法也可以改变对象的状态。对象状态是指对象拥有的数据。例如，图形对象有两个数据值，用来表示它在屏幕上的位置。move方法实际上在对象中修改了这两个值，将图形移动到屏幕上的另一个位置。注意，move方法中的结束条件反映了对象状态的变化。

编程新手容易忽视准确无误的文档记录的重要性，特别是当一个人既是小程序的设计人员，也是编程人员和用户时，这个问题更加突出。若仅设计move方法，而未记下合约条款，那么，在后来实现该方法时，还会记得move方法的具体内容吗？在编写好move方法的数周之后，还能记得用法吗？为了唤起记忆，是分析Java代码方便，还是读取初始条件和结束条件方便？随着程序规模的扩大，正确编写的文档显得更加重要，无论个体编写者，还是团队成员，都要注意这个问题。

注意，自己或他人可能已经实现了一些需要的对象或方法。Java支持软件组件的重用，它一般将组件组织到类库中，将类组合为包含已编译代码的包。这将无法访问方法的Java代码。Java应用程序编程接口(Application Programming Interface，简写API)就是这样一个预先编写的软件集合。假如要使用Java API包java.lang.Math中的静态方法sqrt，因为sqrt已经过预编译，所以无法访问其源代码，但知道它的用法：若给sqrt传送一个double类型的表达式，则sqrt将该表达式的平方根返回为double类型。这就是说，即使不了解java.lang.Math.sqrt的实现方法，同样可以使用它。而且，即使java.lang.Math.sqrt不是用Java语言编写的，也没有影响！没有必要了解java.lang.Math.sqrt的细节，只要了解其规范，就可以在自己的程序中放心地使用它。

如果以前为程序设计阶段安排的时间很少或者没有，就必须改掉这一习惯。设计阶段的最终结果应是一个易于转换为某种编程语言结构的解决方案。为设计阶段分配足够的时间，可以减少编码和调试程序需要的时间。

下面将继续阐述有关设计的问题。

3. 第3阶段：风险分析

开发软件是有风险的。一些风险是所有软件项目所共有的，还有一些是某个项目所特有的。一些风险可以预测，也有一些不可预测。风险会影响项目的进度、成本、业务是否成功，甚至是人的生命和健康。一些风险可以消除或减少，但不能避免所有的风险。在识别、评估和管理软件产品开发的风险时，可以采用一定的技术。后续课程将介绍相关的技术。风险分析的结果影响软件生命周期的其他阶段。

4. 第4阶段：验证

可以用正式的理论方法来证明算法的正确性。目前，该领域的研究还不完善，所以此处只分析验证过程的某些方面。

“断言”(assertion)是对算法中某处具体条件的描述。初始条件和结束条件是方法开始和结束时的条件的断言。“不变式”(invariant)是一个条件，在算法中的某个位置，不变式恒为true；“循环不变式”(loop invariant)也是一个条件，在每次执行算法中的循环前后，循环不变式恒为true；由后述可知，循环不变式有助于正确地编写循环。使用不变式，可在开始编码前就发现错误，从而节省代码的调试和测试时间，并从总体上节省时间。

证明算法类似于证明几何定理。例如，为了证明方法的正确性，应先从初始条件开始(类似于几何的公理和假设)，然后推演算法的步骤，导出结束条件。为此，应考虑算法的每个步骤，并说明步骤前的断言如何导出步骤后的某个断言。

通过证明各个语句的正确性，可以证明语句序列、方法以及程序本身的正确性。例如，设若断言A₁为true，执行语句体S₁，则可导出断言A₂为true。再设断言A₂和语句S₂可导出断言A₃。那么，可以得出结论，若断言A₁为true，执行S₁与S₂语句序列，将导出断言A₃。按这种方式继续，最终可以证明程序的正确性。

很明显，如果在验证过程中发现了错误，可以更正算法，并可能修改问题描述。因此，使用不变式进行推导，可在开始编码前减少算法中的错误，从而节省代码调试时间。

一些构造语句，如if语句、循环和赋值语句的正确性可得到有效的证明。一种重要的技巧是使用循环不变式，来推导出迭代算法的正确性。例如，证明下列简单的循环结构能计算出数组item前n个元素的和。

// computes the sum of item[0], item[1],  .  .  .,

// item[n-1] for any n >= 1

int sum = 0;

int j = 0;

while (j < n) {

    sum += item[j];

    ++j;

}   // end while

在循环开始执行前，sum为0，j为0。循环执行一次，sum为itme[0]，j为1。一般情况下：

sum为元素item[0]到item[j–1]的和。

该语句就是这个循环的不变式。对于一个循环，在下列情况下，不变式恒为true。

●       初始化步骤之后，循环开始执行之前

●       在循环的每次迭代前

●       在循环的每次迭代后

●       循环终止后

对于上面的循环例子，有：

int sum = 0;

int j = 0；

                             ←不变式为true

while (j < n) {

                             ←不变式为true

   sum += item[j];

   ++j;

                             ←不变式为true

}   // end while

                             ←不变式为true

通过观察不变式，可证明迭代算法是正确的。对于上面的循环例子，必须证明不变式在以下4个位置为true：

(1) 开始时不变式必为true。在循环第一次执行前，上例的sum和j的初始值为0。此时的不变式为：sum包含元素item[0]到item[–1]的和。此范围没有元素，故不变式为true。

(2) 循环的执行必须维持不变式的值。即要说明：若不变式在循环的任何迭代之前为true，则迭代后必为true。上例的循环将item[j]加到sum上，之后j增1。当循环执行后，添加到sum的最后一个元素是item[j–1]，故迭代后不变式为true。

(3) 不变式必须证明算法的正确性。即要说明：若循环终止时不变式为true，则算法正确。在上例中，循环终止时，j等于n，不变式为true：sum等于元素item[0]到item[n–1]的和。这正是要求计算的和，故算法正确。

(4) 循环必须终止。即要说明：循环将在经过有限次的迭代后终止。在上例中，变量j开始为0，随后，每次循环执行时，j都增1。这样，对于任何n≥1，j最终将等于n。while语句的特性保证该循环能够结束。

使用不变式，不仅能证明循环是正确的，也能证明循环是错误的。例如，假设while语句中的表达式是j≤n，而不是j<n。前面的步骤1、2仍然正确，但第3步发生了变化：当循环终止时，j包含n+1；因为不变式应为true，所以sum等于元素item[0]到item[n]的和。这不是要求计算的和，故循环错误。

注意，步骤1～4与数学归纳法有明显的联系。开始时不变式为true，建立了基例(base case)。这类似于：对于自然数0，属性为true。证明循环的各个迭代维持不变式的值是归纳步骤。这类似于：若对于任意自然数k，属性为true，则对于自然数k+1，属性为true。在证明上述4点后，可得出结论：在循环的每次迭代后，不变式为true；这类似于用数学归纳法得出的结论：对于每个自然数，属性为true。

标识循环不变式有助于编写正确的循环。应以注释形式来说明不变式，放在各个循环的前面。对于上例，可使用如下形式：

// Invariant: 0 <= j <= n and

// sum = item[0] +...+ item[j-l]

while (j < n)

...

可以肯定，对于下面的循环来说，其不变式是正确的。记住，在循环开始前和每次迭代后(包含最后一次迭代)，各个不变式必须为true。另外，对于for循环，为便于理解，可将其临时转换为等效的while循环。

// Computes an approximation to e^x for a real x

double t = 1.0, s = 1.0;

intk = 1;

// Invariant: t == x^k-1/(k-1)! and

// s == 1+x+x²/2!+ּּּ+x^k-1/(k-1)!

while (k <= n) {

    t *= x/k;

    s  += t;

    ++k;

}   // end while

// Computes n! for an integer n >= 0

int f = 1;

 // Invariant: f == (j-1)!

 for (int j = 1; j <= n; ++j) {

    f *= j;

 }  // end for

5. 第5阶段：编码

编码阶段将设计思想转换为某种编程语言，并消除语法错误。在有些人看来，编码是编程的全部。这是一个错误观念，必须对此有清醒的认识：对于大多数软件而言，编码阶段并不是生命周期的主要部分，只是相对次要的工作。

6. 第6阶段：测试

在测试阶段，要尽可能地排除逻辑错误。一种方法是首先使用能得出已知结果的有效输入数据，来测试对象的各个方法。如果某些数据有值域，则测试该值域的端点值。例如，若n的输入值域为1~10，则一定要测试n为1和10的情况。另外，要用无效的数据来测试程序的错误检测能力。尝试一些随机数据，最后尝试一些实际数据。测试是一门科学，也是一门艺术，后续课程将进一步介绍。

7. 第7阶段：完善解决方案

问题解决过程的第1到第6阶段的结果是一个能工作的程序，它经过广泛测试，并根据需要进行了调试。如果程序已经能够解决最初的问题，这个完善阶段还有什么意义？

通常，解决问题的最好方法是首先在解决方案的设计期间做一些简化假设。例如，可假设输入是某种格式，而且其内容是正确的，之后基于这些假设开发完整的工作程序。接下来，可向工作程序添加更复杂的输入和输出例程、附加功能和更多的错误检查功能。

这种最初简化问题的方法使问题解决过程需要增加一个完善步骤。当然，必须谨慎，确保最终的完善阶段不需要完全重新设计解决方案。通常，可以轻松地完成这些完善任务，在使用模块化设计方法的情况下，尤其如此。事实上，按照这种方式完善功能是模块化设计的一个重要优点。另外要注意，不管何时修改程序，也不管这些更改看上去多么微不足道，都需要再次对程序进行彻底测试。

由上述讨论可知，在软件的生命周期中，各个阶段并不完全相互独立，也不是线性的。在设计早期中做一些简化假设时，就应该考虑以后如何处理这些假设。测试程序可对设计方案的更改提供建议，而若更改了程序，就必须再次测试程序。

8. 第8阶段：生产

软件产品完成后，将其分发给预定用户，在用户的计算机上安装，并投入使用。

9. 第9阶段：维护

维护程序与维护小汽车不同。软件产品的磨损可以忽略不计。但软件用户总会检测到测试阶段没有发现的错误，更改这些错误是软件维护的一部分。维护阶段的另一方面包括通过添加更多功能，或修改已有的部分，来增强软件的性能，从而更好地服务用户。软件极少由设计和实现原始程序的人来维护。因此，详细的文档记录显得格外重要。

程序的生命周期与人的生命有关吗？确实有。阶段1~7应看作问题求解过程的步骤。使用该策略，首先根据一些初始的简化假设，设计和实现解决方案(阶段1~6)。结果是一个结构完好的程序，它解决了在一定程度上得到简化的问题。问题解决过程的最后一个步骤，即阶段7，是完善以前的工作，得到一个符合原始问题描述的复杂程序。

2.1.3  优秀的解决方案

在投入时间和精力研究问题求解技术前，应考虑一下，为什么掌握这些技术有助于找出优秀的问题求解方案？一个浅显的理由是：使用这些技术，将得到优秀的解决方案。这引出一个更基本的问题，什么是优秀的解决方案？本节将尝试回答这一问题。

因为计算机程序是解决方案的最终形式，所以我们来分析一下优秀的计算机程序的组成。很显然，编写程序的目的是执行某个任务。在执行任务的过程中，存在真实而有形的成本。该成本包含多种因素，如程序消耗的计算机资源(计算时间与内存)，程序使用者遇到的困难，以及程序行为不当所造成的后果。

不过，该成本并不是解决方案的总成本，仅考虑了软件生命周期中一个阶段的情况，也就是使用程序的阶段。要评估一个解决方案是否优秀，还必须考虑开发解决方案的其他各阶段，以及在编写出实现解决方案的程序后的各阶段。这些阶段都需要考虑成本。解决方案的总成本必须考虑开发、完善、编码、调试和测试人员的时间价值，以及维护、修改和扩展软件的成本。

所以，在计算解决方案的总成本时，必须考虑各种因素。若从多个角度考虑成本，则可以根据下列标准评估解决方案：

如果解决方案在软件生命周期的所有阶段引发的总成本最低，它就是一个优秀的解决方案。

有趣的是，从早期的计算环境至今，各种成本要素的相对重要性发生了变化。最初，计算机时间成本相对于人力时间成本显得很高。另外，当时人们编写程序的目的是执行非常具体、狭义的确定性任务。如果任务发生了变化，就新编一个程序。程序维护不是一个大问题，所以人们很少关心程序的可读性。程序一般只有一个用户，即编程人员，所以编程人员不关心程序的误用或易用性。程序界面一般也不受重视。

在这样的环境下，计算机资源成本占据主导位置。如果两个程序执行相同的任务，则需要较少时间和内存的程序为优。但时至今日，计算成本已大幅下降，在计算成本时，问题求解者和编程人员的时间价值成为非常重要的因素。计算成本下降的另一个结果是，计算机可用来执行各个领域(很多是非科技领域)的任务。计算机用户往往不具备技术专长，也不了解程序的工作原理，他们希望软件易于使用。

现在的程序比早期程序规模更大，也更复杂，需要多人参与设计、使用和维护。合理的结构和详细的文档记录显得格外重要。程序要执行更加重要的任务，因此出错的代价变得极大。因此，社会既需要结构完好的程序，也需要能验证程序正确性的技术。人们不会也不应该把他们的生计(甚至生命)托付给一个只有编写者能够理解和维护的程序。

时代的发展摒弃了“效率最高的解决方案一定最优”的观念。如果两个程序执行相同的任务，较快者不一定是较优者。如果编程人员试图用书本中的各种技术，以降低代码可读性为代价，力求节省几微秒的计算时间，则显然背离了当今的成本结构理念。在编写程序时，既要考虑计算机因素，也要考虑人的因素。

当然也不能走向另一个极端，认为解决方案的效率无关紧要。而实际上，在很多情况下，效率依然是解决方案是否可用的决定性因素。准确地说，效率是必须考虑的多种因素之一。如果两种解决方案的效率接近，则其他因素将决定哪个方案更好。但如果二者的效率差别很大，则这种差别将成为压倒一切的因素。在问题求解过程的各个阶段中，在开发解决方案的基本方法时，效率是最需要考虑的因素。解决方案要素(即算法和数据存储方式)的选择对效率影响极大，而编写的代码对效率影响不大。

在软件开发的成本中，另一个因素是代码的可重用性。使用现有的代码可以减少开发解决方案的成本和时间。这也减少维护成本，因为可重用的组件一般都经过了仔细的设计，也得到了全面的测试。在软件开发过程中，有两种典型的代码重用方式。第一种是，代码库和开放源代码库中的可用组件常常适用于一个系统。注意，这些成品组件的原始设计完全独立于当前的软件开发。然而它们可以进行调整和完善，成为当前解决方案的一部分。第二种重用代码的方式是，项目中的组件按照一定的方法设计，以使它们成为软件开发后期的更具体组件的基础。

本书倡导一个问题求解原则：将解决方案的成本看作多元成本。有理由认为，这个原则在当前和未来数年都是合理的。