1.5 程序设计的基本算法与应用

算法是解决问题方法的精确描述，程序＝数据结构＋算法。计算机在解决数学和工程问题时，形成了很多经典的算法，这些算法能为特定类型的问题提供快速解决方案。对这些算法的了解有助于人们提升兴趣、开阔视野，同时对计算机解决实际问题的能力形成较直观的概念。

1.5.1 迭代法与应用

迭代法是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。迭代法又分为精确迭代和近似迭代。比较典型的迭代法如“二分法”和“牛顿迭代法”属于近似迭代法。

（1）运用迭代法的基本步骤

1）确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接的不断由旧值递推出新值的变量，这个变量就是迭代变量。

2）建立迭代关系式。迭代关系式是指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

3）对迭代过程进行控制。不能让迭代过程无休止地重复执行下去，结束迭代过程的时间是编写迭代程序必须考虑的问题。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

（2）利用迭代法来求方程的根

例如，设方程为f（x）＝0，用某种数学方法导出等价的形式x＝g（x），然后按以下步骤执行：

1）选方程的一个近似根，赋给变量x0。

2）将x0的值保存于变量x1，然后计算g（x1），将结果存于变量x0。

3）当x0与x1差的绝对值小于指定的精度要求时，重复步骤2）的计算。

若方程有根并且用上述方法计算出来的近似根收敛，那按上述方法计算得的x0就是方程的根。

根据上面的叙述用C语言来表示求方程根的程序代码如下：

在使用迭代法求方程的根时，应该注意下面两种可能发生的情况：

1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制。

2）方程虽然有解，但若迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

【例1-1】 利用牛顿迭代法求方程的根。方程为ax3＋bx2＋cx＋d＝0，系数a，b，c，d由主函数输入。求x在1附近的一个实根，求出的根由主函数输出。

分析：对于方程f（x）＝ax3＋bx2＋cx＋d＝0，通过牛顿迭代公式：xk＋1＝xk-f（xk）／f′（xk），可以推出迭代公式为x＝x-（ax3＋bx2＋cx＋d）／（3ax2＋2bx＋c），其中f′（x）＝3ax2＋2bx＋c。根据上面分析，利用C语言编写的程序代码如下：

1.5.2 递推法与应用

递推法是利用问题本身所具有的递推关系求问题解的一种方法。设要求问题规模为N的解，当N＝1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题必须要有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为i的解。这样，程序可从i＝0或i＝1出发，重复地，由已知i-1规模的解，通过递推获得规模为i的解，直至得到规模为N的解。

【例1-2】 使用递推法来输出费波那契（Fibonacci）数列的前20项值。Fibonacci系列：

这个数列利用递推过程可以得到如下公式：f（0）＝0；f（1）＝1；f（n）＝f（n-2）＋f（n-1）（n＞1）。

通过上面的分析，可以用C语言程序来输出Fibonacci数列（输出前20项）。

1.5.3 递归法与应用

递归法是设计和描述算法的一种有力的工具，它在复杂算法的描述中被经常采用，能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N＝1时，能直接得解。

【例1-3】 编写计算Fibonacci数列的第n项函数fib（n）。Fibonacci数列：0，1，1，2，3，…，即

写成递归函数如下：

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如，在【例1-3】中求解fib（n），把它推到求解fib（n-1）和fib（n-2）。也就是说，为计算fib（n），必须先计算fib（n-1）和fib（n-2），而计算fib（n-1）和fib（n-2），又必须先计算fib（n-3）和fib（n-4）。依此类推，直至计算fib（1）和fib（0），分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如，在函数fib中，当n为1和0的情况。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。例如，得到fib（1）和fib（0）后，返回得到fib（2）的结果，……，在得到了fib（n-1）和fib（n-2）的结果后，返回得到fib（n）的结果。

在编写递归函数时要注意，函数中的局部变量和参数局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。

由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如，【例1-3】计算Fibonacci数列的第n项的函数fib（n）应采用递推算法，即从Fibonacci数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。

1.5.4 穷举法与应用

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

【例1-4】　百钱买百鸡问题。

问题描述：一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，小鸡一钱3只，问一百只鸡中公鸡、母鸡、小鸡各多少。

这是一个古典数学问题，设一百只鸡中公鸡、母鸡、小鸡分别为x，y，z，问题化为三元一次方程组：

这里x，y，z为正整数，且z是3的倍数；由于鸡和钱的总数都是100，可以确定x，y，z的取值范围：x的取值范围为1～20，y的取值范围为1～33，z的取值范围为3～99，步长为3。

对于这个问题可以用穷举的方法，遍历x、y、z的所有可能组合，最后得到问题的解。

初始算法：

1）x，y初始化为1，z初始化为3。

2）计算x循环，找到公鸡的只数。

3）计算y循环，找到母鸡的只数。

4）计算z循环，找到小鸡的只数。

5）结束，程序输出结果后退出。

具体分析：

算法的步骤1）实际上是分散在程序之中的，由于用的是for循环，初始条件放到了表达式之中。

步骤2）和步骤3）是按照步长1去寻找公鸡和母鸡的个数。

对于步骤4）：

①z＝3。

②是否满足百钱买百鸡：

●满足，输出最终百钱买到的百鸡的结果。

●不满足，不做处理。

③变量增加，这里注意步长为3。

算法流程如图1-4所示。

运行结果：

1.5.5 回溯法与应用

回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

【例1-5】 填字游戏。

问题描述：在3×3个方格的方阵中要填入数字1～N（N≥10）内的某9个数字，每个方格填一个整数，所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。

可用回溯法找到问题的解，即从第1个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填，就要回退到前一方格，调整前一方格的填入数。当第9个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第9个填入的整数，寻找下一个解。

为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。

回溯法找一个解的算法：

如果程序要找全部解，则在将找到的解输出后，继续调整最后位置上填放的整数，试图去找下一个解。

回溯法找全部解的算法：

为了确保程序能够终止，调整时必须保证曾被放弃过的填数序列不会再次实验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一形成候选者并检验。从小到大或从大到小，都是可以采用的方法。如扩展时，先在新位置填入整数1，调整时，找当前候选解中下一个还未被使用过的整数。将上述扩展、调整、检验都编写成程序，细节见找全部解的算法程序。

1.5.6 贪婪法与应用

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

例如，平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是在使用贪婪法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币。按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解应是3个5单位面值的硬币。

【例1-6】 装箱问题。

问题描述：设有编号为0，1，…，n-1的n种物品，体积分别为v0，v1，…，vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。

若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到，但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。不失一般性，设n件物品的体积是按从大到小排好序的，即有v0≥v1≥…≥vn-1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。

装箱算法简单描述如下：

上述算法能求出需要的箱子数box＿count，并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解，设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需3只箱子，各箱子所装物品分别为：第1只箱子装物品1、3；第2只箱子装物品2、4、5；第3只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。

若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。

1.5.7 分治法与应用

1.分治法的基本思想

任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n＝1时，不需任何计算；n＝2时，只要作一次比较即可排好序；n＝3时只要作2次比较即可。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题（1＜k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解，这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

2.分治法的适用条件

分治法所能解决的问题一般具有以下几个特征：

1）该问题的规模缩小到一定的程度就可以容易解决。

2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3）利用该问题分解出的子问题的解可以合并为该问题的解。

4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第1）条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第2）条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第3）条特征是关键，能否利用分治法完全取决于问题是否具有第3）条特征，如果具备了第1）条和第2）条特征，而不具备第3）条特征，则可以考虑贪婪法或动态规划法；第4）条特征涉及分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

3.分治法的基本步骤

分治法在每一层递归上都有以下3个步骤：

1）分解。将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

2）解决。若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。

3）合并。将各个子问题的解合并为原问题的解。

4.分治法的算法设计模式

它的一般算法设计模式如下：

其中，｜P｜表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题容易直接解出，不必再继续分解；ADHOC（P）是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC（P）求解。

算法MERGE（y1，y2，…，yk）是该分治法中的合并子算法，用于将P的子问题P1，P2，…，Pk的相应解y1，y2，…，yk合并为P的解。

根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k＝2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。

【例1-7】 循环赛日程表。

问题描述：设有n＝2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：

1）每个选手必须与其他n-1个选手各赛一次。

2）每个选手一天只能参赛一次。

3）循环赛在n-1天内结束。

请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中，1≤i≤n，1≤j≤n-1。

分治法分析：

按分治策略，可以将所有的选手分为两队，则n个选手的比赛日程表可以通过n／2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。

图1-5c所列出的正方形表是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。