1.2 问题的求解过程

软件开发的过程就是计算机求解问题的过程，使用计算机解题的核心就是进行算法设计，算法是为解决特定问题而采取的有限操作步骤，是对解决方案准确而完整的描述。

算法是精确定义的，可以认为算法是问题程序化的解决方案。

1.2.1 问题及问题的求解过程

当前情况和预期的目标不同就会产生问题，求解问题（Problem Solving）是寻找一种方法来实现目标。问题的求解过程（Problem Solving Process）是人们通过使用问题领域的知识来理解和定义问题，并凭借自身的经验和知识去选择和使用适当的问题求解策略、技术和工具，将一个问题的描述转换成对问题求解的过程，如图1-2所示。

计算机求解问题的关键之一是寻找一种问题求解策略（Problem Solving Strategy），得到求解问题的算法，从而得到问题的解。

一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程（Software Engineering）将软件开发和维护过程分成若干阶段，称为系统生命周期（System Life Cycle）或软件生命周期。

通常把软件生命周期划分为：分析（Analysis）、设计（Design）、编码（Coding or Programming）、测试（Testing）和维护（Maintenance）5个阶段。前4个阶段属于开发期，最后一个阶段处于运行期。

算法设计的整个过程，可以包含问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。在此我们只关心算法的设计和分析。

现在给出在算法设计和分析过程中所要经历的一系列典型步骤。

（1）理解问题（Understand the Problem）：在设计算法前首先要做的就是完全理解所给出的问题。明确定义所要求解的问题，并用适当的方式表示问题。

（2）设计方案（Devise a Plan）：求解问题时，考虑从何处着手，考虑选择何种问题求解策略和技术进行求解，以得到问题求解的算法。

（3）实现方案（Carry Out the Plan）：实现求解问题的算法，使用问题实例进行测试、验证。

（4）回顾复查（Look Back）：检查该求解方法是否确实求解了问题或达到了目的。

（5）评估算法，考虑该解法是否可以简化、改进和推广。

1.2.2 算法设计与算法表示

1. 算法问题的求解过程

算法问题的求解过程本质上与一般问题的求解过程是一致的。求解一个算法问题，需要先理解问题。通过最小阅读对问题的描述，充分理解所求解的问题。

算法一般分为两类：精确算法和启发式算法。精确算法（Exact Algorithm）总能保证求得问题的解；启发式算法（Heuristic Algorithm）通过使用某种规则、简化或智能猜测来减少问题求解的时间。

对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（Approximation Algorithm）。如果在算法中需做出某些随机选择，则称为随机算法（Randomized Algorithm）。

2. 算法设计策略

使用计算机的问题求解策略主要指算法设计策略（Algorithm Design Strategy）（技术）。算法设计策略是使用算法解题的一般性方法，可用于解决不同计算领域的多种问题。这是创造性的活动，学习已经被实践证明是有用的一些基本设计策略是非常有用的。值得注意的是要学习设计高效的算法。算法设计方法主要有：分治策略、贪心算法、动态规划、回溯法、分支限界法等。我们将在后面的章节中陆续介绍。

3. 算法的表示

算法需要用一种语言来描述，算法的表示是算法思想的表示形式。显然，用自然语言描述算法时，往往一个人认为明确的操作，另一个人却觉得不明确或者尽管两个人都觉得明确了，但实际上有着不同的理解，因此，算法应该用无歧义的算法描述语言来描述。

计算机语言既能描述算法，又能实际执行。在这里，我们将采用C++语言来描述算法。C++语言的优点是数据类型丰富，语句精炼，功能强，效率高，可移植性好，既能面向对象又能面向过程。用C++语言来描述算法可使整个算法结构紧凑，可读性强，便于修改。

在课程中，有时为了更好地阐明算法的思路，我们还采用C++语言与自然语言相结合的方式来描述算法。

1.2.3 算法确认和算法分析

确认一个算法是否正确的活动称为算法确认（Algorithm Validation），其目的在于确认一个算法是否能正确无误地工作，即证明算法对所有可能的合法输入都能得出正确的答案。

1. 算法证明

算法证明与算法描述语言无关。使用数学工具证明算法的正确性，称为算法证明。有些算法证明简单，有些算法证明困难。在本课程中，仅对算法的正确性进行一般的非形式化的讨论和通过对算法的程序实现进行测试。

证明算法正确性的常用方法是数学归纳法。如【程序1-1】中求最大公约数的递归算法rgcd，可用数学归纳法证明如下：

设m和n是整数，0≤m<n。若m=0，则因gcd(0, n)=n，程序rgcd在m=0时返回n是正确的。归纳法假定当0≤m<n<k时，函数rgcd(m, n)能在有限时间内正确返回m和n的最大公约数，那么当0<m<n=k时，考察函数rgcd(m, n)，它将具有rgcd(n%m, m)的值。这是因为0≤n%m<m且gcd(m, n)=gcd(n%m, m)，故该值正是m和n的最大公约数，证毕。

如果要表明算法是不正确的，举一个反例，即给出一个能够导致算法不能正确处理的输入实例就可以。

2. 算法测试

程序测试（Program Testing）是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例，Test Case），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项活动。

调试只能指出有错误，而不能指出它们不存在错误。测试的目的是发现错误，调试是诊断和纠正错误。大多数情况下，算法的正确性验证是通过程序测试和调试排错来进行的。

3. 算法分析

根据算法分析与设计的步骤，在完成算法正确性检验之后，要做的工作就是算法分析。

算法分析（Algorithm Analysis）是对算法利用时间资源和空间资源的效率进行研究。算法分析活动将对算法的执行时间和所需的存储空间进行估算。算法分析不仅可以预计算法能否有效地完成任务，而且可以知道在最好、最坏和平均情况下的运算时间，对解决同一问题不同算法的优劣做出比较。

当然在算法写成程序后，便可使用样本数据，实际测量一个程序所消耗的时间和空间，这称为程序的性能测量（Performance Measurement）。