几种常见的算法

1、 穷举法

穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出满足条件的解.

穷举法的运用关键在于解决两个问题：

在运用穷举法时,容易出现的问题是可能解过多,导致算法效率很低,这就需要对列举可能解的方法进行优化.

以题1041--纯素数问题为例,从1000到9999都可以看作是可能解,可以通过对所有这些可能解逐一进行判别,找出其中的纯素数,但只要稍作分析,就会发现其实可以大幅度地降低可能解的范围.根据题意易知,个位只可能是3、5、7,再根据题意可知,可以在3、5、7的基础上,先找出所有的二位纯素数,再在二位纯素数基础上找出三位纯素数,最后在三位纯素数的基础上找出所有的四位纯素数.

2、 分治法

分治法也是应用非常广泛的一种算法设计策略,其思想是将问题分解为若干子问题,从而可以递归地求解各子问题,再综合出问题的解.

分治法的运用关键在于解决三个问题：

我们熟知的如汉诺塔问题、折半查找算法、快速排序算法等都是分治法运用的典型案例.

以题1045--Square Coins为例,先对题意进行分析,可设一个函数f(m,n)等于用面值不超过n2的货币构成总值为m的方案数,则容易推导出：

f(m,n) = f(m-0*n*n,n-1)+f(m-1*n*n,n-1)+f(m-2*n*n,n-1)+...+f(m-k*n*n,n-1)

这里的k是币值为n2的货币最多可以用多少枚,即k=m/(n*n).

也很容易分析出,f(m,1) = f(1,n) = 1

对于这样的题目,一旦分析出了递推公式,程序就非常好写了.所以在动手开始写程序之前,分析工作做得越彻底,逻辑描述越准确、简洁,写起程序来就会越容易.

3、 动态规划法

动态规划法多用来 计算最优问题,动态规划法与分治法的基本思想是一致的,但处理的手法不同.动态规划法在运用时,要先对问题的分治规律进行分析,找出终结子问题,以及子问题向父问题归纳的规则,而算法则直接从终结子问题开始求解,逐层向上归纳,直到归纳出原问题的解.

动态规划法多用于在分治过程中,子问题可能重复出现的情况,在这种情况下,如果按照常规的分治法,自上向下分治求解,则重复出现的子问题就会被重复地求解,从而增大了冗余计算量,降低了求解效率.而采用动态规划法,自底向上求解,每个子问题只计算一次,就可以避免这种重复的求解了.

动态规划法还有另外一种实现形式,即备忘录法.备忘录的基本思想是设立一个称为备忘录的容器,记录已经求得解的子问题及其解.仍然采用与分治法相同的自上向下分治求解的策略,只是对每一个分解出的子问题,先在备忘录中查找该子问题,如果备忘录中已经存在该子问题,则不须再求解,可以从备忘录中直接得到解,否则,对子问题递归求解,且每求得一个子问题的解,都将子问题及解存入备忘录中.

例如,在题1045--Square Coins中,可以采用分治法求解,也可以采用动态规划法求解,即从f(m,1)和f(1,n)出发,逐层向上计算,直到求得f(m,n).

在竞赛中,动态规划和备忘录的思想还可以有另一种用法.有些题目中的可能问题数是有限的,而在一次运行中可能需要计算多个测试用例,可以采用备忘录的方法,预先将所有的问题的解记录下来,然后输入一个测试用例,就查备忘录,直接找到答案输出.这在各问题之间存在父子关系的情况下,会更有效.例如,在题1045--Square Coins中,题目中已经指出了最大的目标币值不超过300,也就是说问题数只有300个,而且各问题的计算中存在重叠的子问题,可以采用动态规划法,将所有问题的解先全部计算出来,再依次输入测试用例数据,并直接输出答案.

4、 回溯法

回溯法是基于问题状态树搜索的求解法,其可适用范围很广.从某种角度上说,可以把回溯法看作是优化了的穷举法.回溯法的基本思想是逐步构造问题的可能解,一边构造,一边用约束条件进行判别,一旦发现已经不可能构造出满足条件的解了,则退回上一步构造过程,重新进行构造.这个退回的过程,就称之为回溯.

回溯法在运用时,要解决的关键问题在于：

回溯法的经典案例也很多,例如全排列问题、N后问题等.

5、 贪心法

贪心法也是求解最优问题的常用算法策略,利用贪心法策略所设计的算法,通常效率较高,算法简单.贪心法的基本思想是对问题做出目前看来最好的选择,即贪心选择,并使问题转化为规模更小的子问题.如此迭代,直到子问题可以直接求解.

基于贪心法的经典算法例如：哈夫曼算法、最小生成树算法、最短路径算法等