现代大学计算机基础算法思维与程序设计基础

第5章算法思维与程序设计根底5.1开启智慧的“苹果〞—算法5.2亚当夏娃的诱惑—算法与程序5.3登上方舟的神器—经典算法思想

5.1开启智慧的“苹果〞—算法

在20世纪50年代西方某些著名的词典中，还未曾收录过算法(Algorithm)一词。根据西方数学史家的考证，古代阿拉伯的一位学者写了一部名著?Kitābal-jabrWa’lmuqābJla?(?复原和化简的规那么?)。这部著作流传到了西方，结果从作者署名中的al-Khwārizmī派生出了Algorithm(算法)一词，从作品名字中的al-jabr派生出了Algebra(代数)一词。随着时间的推移，Algorithm(算法)这个词已经完全与它原来的含义不同了。计算机系统中的任何软件，都是由大大小小的各种软件组成局部构成的，各自按照特定的算法来实现，算法的好坏直接决定所实现软件性能的优劣。用什么方法来设计算法，所设计的算法需要什么样的资源，需要多少运行时间、多少存储空间，如何判定一个算法的好坏，在开发一个软件时，都是必须予以解决的。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个具体的算法来实现。因此，算法设计与分析是计算机科学与技术的一个核心问题。5.1.1算法的根本概念

欧几里德曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里德所描述的这个过程被称为欧几里德算法，算法这个术语在学术上便具有了现在的含义。下面是这个算法的例子及它的一种描述。

算法欧几里德算法。

输入：正整数m，n

输出：m，n的最大公因子

1.inteuclid(intm，intn)

2.{

3.intr;

4.do{

5.r=m%n;

6.m=n;

7.n=r;

8.}while(r)

9.returnm;

10.}在此用一种类C语言来表达最大公因子的求解过程。在算法的第5行，把m除以n的余数赋予r，第6行把n的值赋予m，第7行把r值赋予n，第8行判断r是否为0，假设非0，继续转到第5行进行处理；假设为0，就转到第9行处理，第9行返回m，算法结束。按照上面这组规那么，给定任意两个正整数，总能返回它们的最大公因子。可以证明这个算法的正确性。算法的历史可以追溯到9世纪的古波斯。最初它仅表示“阿拉伯数字的运算法那么〞。后来，它被赋予更一般的含义，即所谓的一组确定的、有效的、有限的解决问题的步骤。这是算法的最初定义。当代著名计算机科学家D．E．Knuth在他撰写的?THEARTOFCOMPUTERPROGRAMMING?一书中写到：“一个算法，就是一个有穷规那么的集合，其中之规那么规定了一个解决某一特定类型的问题的运算序列。〞

综上所述，可以给出算法的定义：算法是解某一特定问题的一组有穷规那么的集合。5.1.2算法的根本特征

任何解决问题的过程都是由一定的步骤组成的，通常把解决问题确实定方法和有限步骤称为算法。对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是假设干条指令的有穷序列，并且它具有以下特性：

(1)有穷性：算法在执行有限步骤之后结束。

(2)确切性：算法的每一个步骤都有确切的定义。

(3)输入：一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值或初始状态。算法的输入是从特定的对象集合中抽取的。(4)输出：一个算法有一个或多个输出，这些输出与输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。

(5)可行性：在原那么上算法能够精确地运行，进行有限次运算后即可完成一种运算。

必须注意到，在实际应用中，有穷性的限制是不够的。一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法需要执行数十百亿计的运算步骤，那么从理论上说，它是有限的，最终可以结束，但却是人们难以接受的。算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。 5.2亚当夏娃的诱惑—算法与程序

5.2.1算法思想的本质—数学模型

简单地说，数学模型就是对实际问题的一种数学表达，是数学理论与实际问题相结合的一门科学。它将现实问题归结为相应的数学问题，并在此根底上利用数学概念、方法和理论进行深入分析与研究，从而可以从定性或定量的角度来刻画实际问题，并为解决现实问题提供精确数据和可靠指导。算法设计时，首先要根据问题的描述，建立符合要求的数学模型，并设计相关的约束条件等。建立数学模型的步骤如下：

(1)模型准备。要了解问题的实际背景，明确建模目的，搜索必要的各种信息，尽量弄清对象的特征。

(2)模型假设。根据对象的特征和建模目的，对问题进行必要的、合理的简化，用精确的语言做出假设，是建模至关重要的一步。高超的建模者能充分发挥想象力、洞察力和判断力，善于区分问题所有因素的主次，而且为了使处理方法简单，应尽量使问题线性化、均匀化。

(3)模型构成。根据所做的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，建立各个量之间的等式或不等式关系，列出表格、画出图形或确定其他数学结构，选择恰当的数学工具和构造模型的方法对其进行表征，构造出刻画实际问题的数学模型。(4)模型求解。构造数学模型之后，再根据条件和数据分析模型的特征及结构特点，设计或选择求解模型的数学方法和算法，这其中包括解方程、画图形、证明定理、进行逻辑运算及稳定性讨论，特别是编写计算机程序或运用与算法相适应的软件包，并借助计算机完成对模型的求解。

(5)模型分析。根据建模的目的要求，对模型求解的数字结果，或进行变量之间的依赖关系分析，或进行稳定性分析，或进行系统参数的灵敏度分析，或进行误差分析等。通过分析，如果不符合要求，就修改或增减建模假设条件，重新建模，直到符合要求；如果符合要求，还可以对模型进行评价、预测、优化等。(6)模型检验模型分析符合要求之后，还必须回到客观实际中去对模型进行检验，用实际现象、数据等检验模型的合理性和适用性，看它是否符合客观实际，假设不符合，就修改或增减假设条件，重新建模，循环往复，不断完善，直到获得满意的结果。目前计算机技术已为我们进行模型分析、模型检验提供了先进的手段，充分利用这一手段，可以节约大量的时间、人力和物力。

(7)模型应用。模型应用是数学建模的宗旨，也是对模型最客观、最公正的检验。因此，一个成功的数学模型，必须根据建模的目的，将其用于分析、研究和解决实际问题，充分发挥数学模型在生产和科研中的特殊作用。5.2.2算法思想的表达—算法设计

人们希望计算机求解的问题是千差万别的，所设计的求解方法也千差万别。一般来说，算法设计没有固定的方法可循，所以，算法的设计是一个灵活且充满智慧的过程，要求设计者针对具体的问题设计出适合该问题的解决方案。

在进行算法设计时，一般遵循以下步骤：

(1)明确问题的性质，分析题意。这一步很关键。在设计算法的时候，一定要先搞清楚要求算法处理什么问题、实现哪些功能、预期获得的结果等。如果设计者没有充分理解所要解决的问题，那么设计出的算法肯定是漏洞百出的。这一步是算法的切入点，也是设计者必备的技能。(2)建立问题的数学描述模型。数学模型是对实际问题的一种数学表达，进行算法设计时，首先要根据问题的描述，建立符合要求的数学模型，并设计相关的约束条件等。

(3)设计/验证算法。算法设计是把算法具体化，即设计出算法的详细规格说明。在这一阶段，要选择算法的设计策略，并确定合理的数据结构。显然，算法设计策略的选择关乎全局，同样，数据结构的选择对于算法的设计和分析也很重要，如果选择不当，它将影响算法的性能。

做完上面的工作后，采用描述工具将算法的具体过程描述下来，通过对一系列与算法的工作对象有关的定理、引理和公式进行证明，来验证算法所选择的设计策略与思路是否正确。(4)算法分析。算法分析是对算法的效率进行分析，主要是时间效率和空间效率。其中，时间效率显示算法运行速度有多快，空间效率显示算法运行时需要的存储空间有多大。相对而言，人们更关注时间效率。

(5)算法实现和测试。根据算法，采用一种编程语言编程实现，然后上机调试，得到程序的运行结果，分析运行结果是否符合预先的期望，如果不符合，那么找出原因，并对算法或程序进行修正，直到得到正确的结果。5.2.3算法思想的实现—程序设计

程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成局部。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。

任何设计活动都是在各种约束条件和相互矛盾的需求之间寻求一种平衡，程序设计也不例外。在计算机技术开展的早期，由于机器资源比较昂贵，程序的时间和空间代价往往是设计关心的主要因素；随着硬件技术的飞速开展和软件规模的日益庞大，程序的结构、可维护性、复用性、可扩展性等因素日益重要。在程序设计时，一般遵循以下步骤：

(1)分析问题。对于接受的任务要进行认真的分析，研究所给定的条件，分析最后应到达的目标，找出解决问题的规律，选择解题的方法，完成实际问题。

(2)设计算法。即设计出解题的方法和具体步骤。

(3)编写程序。将算法翻译成计算机程序设计语言，对源程序进行编辑、编译和连接。

(4)运行程序，分析结果。运行可执行程序，得到运行结果。能得到运行结果并不意味着程序正确，要对结果进行分析，看它是否合理。不合理要对程序进行调试，即通过上机发现和排除程序中的故障的过程。(5)编写程序文档。许多程序是提供给别人使用的，如同正式的产品应当提供产品说明书一样，正式提供给用户使用的程序，必须向用户提供程序说明书。其内容应包括程序名称、程序功能、运行环境、程序的装入和启动、需要输入的数据，以及使用本卷须知等。5.2.4检验真理的标准—算法分析

解决一个问题，算法不必是唯一的。对表示问题的数据的不同组织方式(数据结构)，解决问题的不同策略将导致不同的算法。解决同一问题的不同算法，消耗的时间和空间资源量有所不同。算法运行所需要的计算机资源的量称为算法的复杂性。一般来说，解决同一问题的算法，需要的资源量越少，我们认为越优秀。计算算法运行所需资源量的过程称为算法复杂性分析，简称算法分析。理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。然而，算法的运行时间都是消耗在数据处理上的，从这个意义上说，算法的空间复杂性不会超过时间复杂性。因此，人们多关注算法的时间复杂性。1．算法复杂性

1)时间复杂性

随着计算机硬件和软件的提升，一个算法的执行时间不便精确计算，只能依据统计方法对算法进行估算。抛开硬件和软件的因素，算法的好坏将直接影响程序的运行时间。一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费的时间就多。一般情况下，算法中根本操作重复执行的次数是问题规模n的某个函数，称为语句频度或时间频度，用T(n)表示，假设有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，那么称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。随着模块n的增大，算法执行的时间增长率f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

例5-1分析下面程序的时间复杂度：

intvalue=0;

//执行了1次

for(inti=0;i<n;i++){

//执行了n次

value+=i;

}这个算法执行了1+n次，如果n无限大，那么可以把前边的1忽略，也就是说这个算法执行了n次，这个算法的时间复杂度就是O(n)。

计算时间复杂度的步骤如下：

(1)去掉运行时间中的所有加法常数。

(2)只保存最高阶项。

(3)如果最高阶项存在且不是1，那么去掉与这个最高阶相乘的常数即可得到时间复杂度。

例5-2计算下面程序的时间复杂度：

分析：当i=0时，里面的for循环执行了n次，当i等于1时里面的for循环执行了n－1次，当i等于2时里面的for执行了n－2次，……所以执行的次数是根据上边计算时间复杂度的步骤，可得以下计算过程：

(1)去掉运行时间中的所有加法常数：这里没有加法常数不用考虑。

(2)只保存最高阶项：这里只保存。

(3)去掉与这个最高阶相乘的常数：这里去掉只剩下n2。

最终这个算法的时间复杂度为O(n2)。

例5-3计算下面程序的时间复杂度：

for(inti=0;i<n;i++){

//do...

}

因为循环要执行n次，所以时间复杂度为O(n)。2)空间复杂性

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间来存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。程序执行时所需存储空间包括以下两局部：

(1)固定局部。这局部空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这局部属于静态空间。(2)可变空间。这局部空间主要包括动态分配的空间以及递归栈所需的空间等。这局部的空间大小与算法有关。

一个算法所需的存储空间用f(n)表示，即S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

2．算法分析意义

算法分析对算法的设计、选用和改进有着重要的指导意义及实用价值。

(1)对于任意给定的问题，设计出复杂性尽可能低的算法是在设计时考虑的一个重要目标。

(2)当给定的问题已经有多种算法时，选择复杂度最低者是在选用算法时应遵循的一个重要准那么。

(3)算法分析有助于对算法进行改进。 5.3登上方舟的神器—经典算法思想

5.3.1化整为零—分治法

1．分治法所能解决的问题特征

(1)该问题的规模缩小到一定的程度就可以容易地解决；

(2)该问题可以分解为假设干个规模较小的相同问题，即该问题具有最优子结构性质；

(3)利用该问题分解出的子问题的解可以合并为该问题的解；

(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。上述第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加的；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，那么可以考虑用贪心法或动态规划法；第四条特征涉及分治法的效率，如果各子问题是不独立的那么分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。2．分治法的求解步骤

1)分解

顾名思义，分治法就是要对待求解问题进行分解，即将问题分解为假设干个规模较小、相互独立、与原问题形式相同的子问题。

那么，怎样对问题分解才合理呢？应把原问题分解为多少个子问题才适宜呢？每个子问题是否规模相同才更为适当？这些问题很难给出肯定的答复。人们通过大量的实践发现，在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分为大小相等的M个子问题，通常M=2，也有M=1的划分，它仍然把问题划分为两局部，取其中的一局部，而丢弃另一局部。例如，二分查找问题在采用分治法求解时就是这样划分的。2)求解各个子问题

如何对各个子问题进行求解呢？由于采用分治法求解的问题被分解为假设干个规模较小的相同子问题，各个子问题的解法与原问题的解法是相同的，因此，可以采用递归技术对各个子问题进行求解。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易解决的程度，这导致递归过程的产生。分治与递归经常同时用在算法设计中，有时，递归也可以采用循环来实现。

3)合并

合并对分治法的性能至关重要，算法的有效性很大程度上依赖于合并的实现。3．分治算法设计模式

其中p(n)表示一个规模为n的问题p，可以分解成K个规模较小的子问题，这些问题相互独立，又与原来的问题结构相同。在解决子问题时，又用相同的方式对每一个问题进行进一步的分解，直到某个阈值n0为止。递归地解这些子问题，再把这些子问题的解合并起来，就得到原来问题的解。n0为一阈值，表示当问题p的规模不超过n0时，问题已容易解出，不必继续分解。Adhoc(p(n))是该分治法中的根本子算法，用于直接解小规模的问题p。因此，当p的规模不超过n0时，直接用Adhoc(p(n))求解。merge(y1，y2，…，yk)是该分治法中的合并子算法，用于将p的子问题p1，p2，…，pk的相应解合并为p的解。

例5-4整数乘法。设X和Y都是n位二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看做一步运算，那么这种方法运行时间为O(n2)。下面用分治法来设计一个更有效的大整数乘积算法。

我们将n位二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见,假设n是2的幂),由此,X=A2n/2+B,Y=C2n/2+D。这样，X和Y的乘积为

Y=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD(1)如果按式(1)计算XY，那么必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)，运行时间为O(n2)，可见，用式(1)计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此把XY写成另一种形式：

XY=AC2n+[(A－B)(D－C)+AC+ BD]2n/2+BD(2)

虽然式(2)来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A－B)(D－C))以及6次加、减法和2次移位。由此需要运行的时间为O(nlog3)=O(n)。5.3.2欲壑难填—贪婪法

1．贪婪算法可解决的问题特征

(1)随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

(2)有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

(3)还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

(4)选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。(5)最后，目标函数给出解的值。

(6)为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步地进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否那么就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。2．贪婪算法的根本思路

(1)建立数学模型来描述问题。

(2)把求解的问题分成假设干个子问题。

(3)对每一子问题求解，得到子问题的局部最优解。

(4)把子问题的解局部最优解合成原问题的一个解。

3．贪婪算法的求解步骤

(1)从问题的某一初始解出发。

(2)朝给定总目标前进一步，求出可行解的一个解元素。

(3)由所有解元素组合成问题的一个可行解。

4．贪婪算法设计模式

贪婪法是在少量运算的根底上做出目前最好的选择，不考虑该选择对将来是否有不良影响，一步一步地进行解的扩充，最后由局部最优解来推导全局最优解

。

例5-5设有n个正整数，将它们连接成一排，组成一个最大的多位整数。例如，n=3时，3个整数25、324、456连成的最大整数为45 632 425；又如，n=4时，4个整数2、9、17、386连成的最大整数为9 386 217。此题很容易想到使用贪婪法，我们考虑把整数按从大到小的顺序连接起来，按这种贪婪标准，很容易找到反例：12、121应该组成12121而非12112，这样情况就有很多种了。是不是此题不能用贪婪法呢？其实此题是可以用贪婪法来求解的，只是刚刚的贪婪标准不对，正确的贪婪标准是：先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之那么把a排在b的后面。

贪婪算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪婪算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，那么贪婪算法应该是最好的选择之一。

5.3.3成竹在胸—动态规划法

动态规划(DynamicProgramming)法是20世纪50年代初美国数学家等人在研究多阶段决策过程(MultistepDecisionProcess)的优化问题时，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，所创立的解决这类过程优化问题的新方法。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如，最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划法比用其他方法求解更为方便。动态规划程序设计是解决最优化问题的一种途径和方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，在正确理解根本概念和方法的根底上，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。1．动态规划法所能解决的问题特征

(1)最优子结构性质：一个最优化策略具有这样的性质，不管过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。

(2)无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后效性，又称为无后向性。(3)子问题的重叠性：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被屡次使用到。该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。2．动态规划算法的根本思路

动态规划算法的根本思想与分治法类似，也是将待求解的问题分解为假设干个子问题(阶段)，按顺序求解子阶段，前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保存那些有可能到达最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。动态规划法与分治法最大的差异是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的根底上，进行进一步的求解)。3.动态规划算法的求解步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，到达结束状态。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

(1)划分阶段：按照问题的时间或空间特征，把问题分为假设干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否那么问题就无法求解。

(2)确定状态和状态变量：将问题开展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

实际应用中可以按以下简化的步骤进行设计：

(1)分析最优解的性质，并刻画最优解的结构特征。

(2)递归定义最优值。

(3)自底向上计算出最优值，并记录相关信息。

(4)根据计算最优值时得到的信息，构造出最优解。

4．动态规划算法设计模式

根据上述动态规划设计的步骤，可得到大体解题框架如下:

(1)初始化(边界条件)。

(2)fori:=2ton(顺推法)或fori:=n－1to1(逆推法)，对i阶段的每一个决策点求局部最优。

(3)确定和输出结束状态的值。

例5-6一个有N个整数元素的一位数组(A[0]，A[1]，…,A[n－1]，A[n])，这个数组当然有很多子数组，那么数组之和的最大值是什么呢？明确一下题意：

(1)子数组必须是连续的。

(2)不需要返回子数组的具体位置。

(3)数组中包含正整数、零和负整数。

例如：

数组{1，－2，3，5，－3，2}的返回值为8；

数组{0，－2，3，5，－1，2}的返回值为9；

数组{－9，－2，－3，－5，－6}的返回值为－2，注意子数组不能为空。根据题意，可以考虑数组的第一个元素，以及最大的一段数组(A[i]，…，A[j])和A[0]的关系，有以下几种情况：

(1)当0=i=j时，元素A[0]本身构成和最大的一段；

(2)当0=i<j时，和最大的一段以A[0]开始；

(3)当0<i时，元素A[0]和最大的一段没有关系。

从上面三种情况看出：可以将一个大问题(N个元素数组)转化为一个较小的问题(N－1个元素的数组)。假设已经知道(A[1]，…，A[n－1])中和最大的一段数组之和为All[1]，并且已经知道(A[1]，…，A[n－1])中包含A[1]的和最大的一段数组为Start[1]，那么不难看出(A[0]，…，A[n])中问题的解All[0]=max{A[0]，A[0]+start[1]，All[1]}。通过这样的分析，可以看出这个问题无后效性，可以用动态规划来解决，算法如下：5.3.4志在四方—周游法

1．遍历方案

从二叉树的递归定义可知，一棵非空的二叉树由根节点及左、右子树这三个根本局部组成，如下图，因此，在任一给定节点上，可以按某种次序执行三个操作：

(1)访问节点本身(N)。

(2)遍历该节点的左子树(L)。

(3)遍历该节点的右子树(R)。

以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。图5.1遍历二叉树的搜索路线

2．三种遍历的命名

根据访问节点操作发生位置命名：

(1)NLR：前序遍历(PreorderTraversal，亦称先序遍历)—访问节点的操作发生在遍历其左右子树之前。

(2) LNR：中序遍历(InorderTraversal)—访问节点的操作发生在遍历其左右子树之中(间)。

(3)LRN：后序遍历(PostorderTraversal)—访问节点的操作发生在遍历其左右子树之后。

注意：由于被访问的节点必是某子树的根，所以N(Node)、L(Leftsubtlee)和R(Rightsubtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。3．遍历算法

1)中序遍历的递归算法

假设二叉树非空，那么依次执行如下操作：

(1)遍历左子树；

(2)访问根节点；

(3)遍历右子树。

中序遍历图所示的二叉树时，得到的中序序列为DBAECF。2)先序遍历的递归算法

假设二叉树非空，那么依次执行如下操作：

(1)访问根节点；

(2)遍历左子树；

(3)遍历右子树。

先序遍历图所示的二叉树时，得到的中序序列为ABDCEF。3)后序遍历得递归算法定义

假设二叉树非空，那么依次执行如下操作：

(1)遍历左子树；

(2)遍历右子树；

(3)访问根节点。

后序遍历图所示的二叉树时，得到的中序序列为DBEFCA。本卷须知：

(1)在搜索路线中，假设访问节点均是第一次经过节点时进行的，那么是前序遍历；假设访问节点均是在第二次(或第三次)经过节点时进行的，那么是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的节点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。

(2)上述三种序列都是线性序列，有且仅有一个开始节点和一个终端节点，其余节点都有且仅有一个前趋节点和一个后继节点。为了区别于树形结构中前趋(即双亲)节点和后继(即孩子)节点的概念，对上述三种线性序列，要在某节点的前趋和后继之前冠以其遍历次序名称。

例5-7图所示的二叉树中节点C，其前序前趋节点是D，前序后继节点是E；中序前趋节点是E，中序后继节点是F；后序前趋节点是F，后序后继节点是A。但是就该树的逻辑结构而言，C的前趋节点是A，后继节点是E和F。

4．算法递归实现

在这里，假设所有的二叉树都以数组的形式储存。

(1)中序遍历。

procedure

mid(i:longint);

begin

if

a[i*2]<>0

then

mid(i*2)；

write(a[i]);

if

a[i*2+1]<>0

then

mid(i*2+1)；

end;(2)先序遍历。

procedure

first(i:longint);

begin

write(a[i]);

ifa[i*2]<>0then

first(i*2)；

ifa[i*2+1]<>0then

first(i*2+1)；

end;(3)后序遍历。

procedure

last(i:longint);

begin

if

a[i*2]<>0

then

last(i*2)；

if

a[i*2+1]<>0

then

last(i*2+1)；

write(a[i]);

end;5.3.5迷途知返—回溯法

1．回溯法所能解决的问题特征

可用回溯法求解的问题P，通常要能表达为：对于的由n元组(x1，x2，…，xn)组成的一个状态空间E={(x1，x2，…，xn)∣xi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且|Si|有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组(x1，x2，…，xi)满足D中仅涉及x1，x2，…，xi的所有约束意味着j(j<=i)元组(x1，x2，…，xj)一定也满足d中仅涉及x1，x2，…，xj的所有约束，其中i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得(x1，x2，…，xj)违反d中仅涉及x1，x2，…，xj的约束之一，那么以(x1，x2，…，xj)为前缀的任何n元组(x1，x2，…，xj，xj+1，…，xn)一定也违反d中仅涉及x1，x2，…，xi的一个约束(j≤i≤n)。因此，对于约束集d具有完备性的问题P，一旦检测断定某个j元组(x1，x2，…，xj)违反d中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以(x1，x2，…，xj)为前缀的任何n元组(x1，x2，…，xj，xj+1，…，xn)都不会是问题P的解，因而就不必去搜索、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出的比枚举法效率更高的算法。

2．回溯法的根本要素

(1)约束条件：包括隐性的和显性的，显约束指对问题的解的取值范围限定，隐约束指为满足问题的解而对不同分量之间施加的约束。

(2)解空间：对于问题的一个实例，解向量满足显约束的所有n元组构成该实例的一个解空间。为了搜索方便，一般用树或图的形式将问题的解空间有效地组织起来，称为状态树，它是构造深度搜索过程的依据，整个搜索以此树展开。

注意：同一个问题的显约束可能有多种，相应解空间的大小就会不同，通常情况下，解空间越小，算法的搜索效率越高。3．回溯法算法的求解步骤

(1)针对所给问题，确定问题的解空间。

首先应明确问题的解空间，问题的解空间应至少包含问题的一个(最优)解。

(2)确定节点的扩展搜索规那么。

搜索思想：从根节点开始，以深度优先搜索的方式进行搜索。在搜索过程中，当前的扩展节点延纵深方向移向一个新节点，判断新节点是否满足隐约束。如果满足，那么新节点成为当前的扩展节点，继续深一层的搜索；如果不满足，那么换到扩展节点的兄弟节点(其他分支)继续搜索。如果新节点没有兄弟节点，或兄弟节点已全部搜索完毕，那么扩展节点成为死节点，搜索回溯到其父节点处继续进行。搜索过程直到找到问题的解或根节点变成死节点为止。(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数防止无效搜索。

在深度优先搜索的过程中，不满足隐约束的分支被剪掉，只沿着满足隐约束的分支搜索问题的解，从而防止了无效搜索，加快了速度。因此，隐约束又称为剪枝函数。剪枝函数一般有两种：一是判断是否能够得到可行解的隐约束，称为约束函数；二是判断是否有可能得到最优解的隐约束，称为限界函数。回溯法是一种具有约束函数或限界函数的深度优先搜索法。4．回溯算法设计模式

回溯算法通常采用递归技术，也可以选用非递归技术。在设计过程中，参数t代表当前扩展节点在解空间树中所处的层次；变量n代表问题的规模，也是解空间的深度；s(n，t)代表当前扩展节点处未搜索的子树的起始编号，e(n，t)代表当前扩展节点处未搜索的子树的终止编号；d(i)代表当前扩展节点可选分支上的数据；X是用来记录问题当前解的数组；constraint(t)代表当前扩展节点处的约束函数；bound(t)代表当前扩展节点处的限界函数。满足约束和限界函数那么继续深一层次的搜索，否那么就剪掉相应的子树。Backtrack(t)代表从第t层开始搜索问题的解。(1)递归回溯模式。

例5-8数的划分(noip2001tg)。

问题描述：将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如，n=7，k=3，下面三种分法被认为是相同的：1，1，5；1，5，1；5，1，1。有多少种不同的分法？

输入：n，k(6<n<=200，2<=k<=6)；

输出：一个整数，即不同的分法。

例如：

输入：7

3；

输出：4

{四种分法为：1，1，5；1，2，4；1，3，3；2，2，3}。算法分析：此题可以用回溯法求解，设自然数n拆分为a1，a2，…，ak，必须满足以下两个条件：

(1) n=a1+a2+…+ak；

(2) a1<=a2<=…<=ak(防止重复计算)。

现假设己求得的拆分数为a1，a2，…，ai，且都满足以上两个条件，设sum=n-a1-a2-…-ai，可根据不同的情形进行处理：

(1)如果i=k，那么得到一个解，那么计数器t加1，并回溯到上一步，改变ai-1的值；

(2)如果i<k且sum>=ai，那么添加下一个元素ai+1；

(3)如果i<k且sum<ai，那么说明达不到目标，回溯到上一步，改变ai-1的值。算法实现步骤如下：

(1)输入自然数n，k并初始化：t:=0;

i:=1;a[i]:=1;

sum:=n-1;

nk:=n

div

k。

(2)如果a[1]<=nk重复：假设i=k，搜索到一个解，计数器t=t+1;并回溯；否那么，假设sum>=a[i]那么继续搜索，假设sum<a[i]那么回溯。搜索时，inc(i);a[i]:=a[i-1];sum:=sum-a[i];；回溯时，dec(i);

inc(a[i]);

sum:=sum+a[i+1]-1。

(3)输出。5.3.6画地为牢—分枝限界法

1．分枝限界算法的根本思路

分枝限界算法常以广度优先或以最小消耗(最大收益)优先的方式搜索问题的解空间树。问题的解空间树是表示解空间的一棵有序树。在搜索问题的解空间树时，分枝限界算法与回溯法对当前节点所采用的扩展方式不同：在分枝限界算法中，每一个活节点(一个自身已生成但其子节点还没有全部生成的节点)只有一次时机成为扩展节点，某节点成为扩展节点后，就一次性产生所有子节点。在这些子节点中，那些导致不可行解或导致非最优解的子节点被舍弃，其余子节点被参加活节点表中。此后，从活节点表中取下一节点成为当前扩展节点，并重复上述节点扩展过程，直到找到所需的解或活节点表为空时为止。2．分枝节点的选择

对搜索树上的某些点必须作出分枝决策，即但凡界限小于迄今为止所有可行解最小下界的任何子集(节点)，都有可能作为分枝的选择对象(对求最小值问题而言)。怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原那么：

(1)从最小下界分枝(优先队列式分枝限界法)：每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点，此节点即为下次分枝的节点。

优点：检查子问题较少，能较快地求得最正确解。

缺点：要存储很多叶节点的界限及对应的消耗矩阵，会花费很多内存空间。(2)从最新产生的最小下界分枝(队列式(FIFO)分枝限界法)：从最新产生的各子集中按顺序选择各节点进行分枝，对于下界比上界还大的节点不进行分枝。

优点：节省了空间。

缺点：需要较多的分枝运算，消耗的时间较多。

这两个原那么更进一步说明了在算法设计中的时空转换概念。

分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其他问题