《佚名》萝卜and月灵

4、(3)算法设计的基本方法 计算机算法

　　计算机算法不同于人工处理的方法，下面是工程_上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。
　　①列举法
　　列举法是计算机算法中的一个基础算法。列举法的基本思想是,根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
　　列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此,在用列举法设计算法时，使方案优化,尽量减少运算工作量，是应该重点注意的。
　　②归纳法
　　归纳法的基本思想是，通过列举少量的特殊情况，经过分析,最后找出一般的关系。从本质_上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
　　③递推;
　　递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程.上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的,因此，递推关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。
　　④递归
　　人们在解决一些复杂问题时，为了降低问题的复杂程度(如问题的规模等)，-般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程,实际.上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。
　　递归分为直接递归与间接递归两种。
　　⑤减半递推技术
　　实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。工程上常用的分治法是减半递推技术。
　　所谓“减半”’，是指将问题的规模减半，而问题的性质不变;所谓“递推”，是指重复“减半”的过程。
　　⑥回溯法
　　在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题,一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探,若试探成功,就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。