1.1.2 算法设计基本方法

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

常用算法设计方法：

（1） 列举法

列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。

在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。

在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律；或对

所有可能的情况进行分类，引出一些有用的信息，是可以大大减少列举量的。

列举算法是计算机算法中的一个基础算法。

（2） 归纳法

归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。

归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

（3） 递推

所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。

其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。

递推关系式往往是归纳的结果。

（4） 递归

人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单

的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解

的逆过程逐步进行综合，这就是递归的基本思想。递归的基础也是归纳。

自己调用自己的过程称为递归调用过程。

递归分为直接递归与间接递归两种。如果一个算法P显式地调用自己则称为直接递归。

如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。

设计递归算法要比递推算法容易的多。但递归算法的执行效率比较低。

（5） 减半递推技术

实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。

所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

（6） 回溯法

通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。