编程中常用算法解读

通过比较经典的例题去讲解一些常用的算法思想，常用的算法思想包括：枚举、递归、分治、贪心、试探、动态迭代和模拟等。下面对最为常见的算法思想进行解读，包括：枚举、递归、分治、贪心。

1.枚举算法

枚举算法我们也称之为穷举算法，就是“逐个测试”，这种算法就是在解决问题的时候去使用所有的方式去解决这个问题，会通过推理去考虑事件发生的每一种可能，最后得出结论。

关于枚举，它的优点在于枚举法一般是现实生活中问题的“直译”，因此比较直观，易于理解；枚举法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明，当然它的缺点也比较明显，用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。

例如：判断水仙花数
首先我们来了解一下什么是水仙花数，所谓”水仙花数”是指一个三位数，其各位数字立方和等于该本身。例如：153是一个水仙花数，因为153=1^3+5^3+3^3。

以python为例，代码如下：

count = 0
for i in range(100,1000):
count += 1
a = int(i / 100)
b = int(i / 10 % 10)
c = int((i % 10))
if pow(a,3)+pow(b,3)+pow(c,3)==i:
print(‘水仙花数:’,i)
print(‘枚举次数:’,count)

2.递归算法

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念，递归算法有三个特点：

1) 递归的过程一般通过函数或者子过程来实现。

2) 递归算法在它内部来直接或者间接的调用自身的算法。

3) 递归算法就是把规模大的问题转换为规模小的问题，然后递归调用函数来求解的过程。

递归算法也有几点需要注意的事项，在前面递归函数中我们也提到过，分别是：

1) 递归是在函数本身调用函数本身。

2) 递归的效率比较低，如果有时间限制不建议使用。

3) 递归过程中需要有一个明确的结束条件，即递归出口。

例如：一个正整数n的阶乘用符号“n!”表示，例如：1! = 1; 2!= 2 * 1 = 2; 3! = 3 * 2 * 1 = 6; 4! = 4 * 3 * 2 * 1 = 24。阶乘的运算是最为明显使用递归解决问题。

3.分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

经典问题主要包括：

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔

例如：二分搜索

它是分治的一个实例，二分搜索也称之为“二分查找法”，只不过二分搜索有着自己的特殊性，正常二分将一个完整的区间分成两个区间，两个区间本应单独找值然后确认结果，但是通过有序的区间可以直接确定结果在那个区间，所以分的两个区间只需要计算其中一个区间，然后继续进行一直到结束。实现方式有递归和非递归，但是非递归用的更多一些。

再例如：求n个元素中的最小值

一个列表中存在n个数据的时候，找到其中的最大值，当然这个问题我们使用Python可以直接通过max()函数和min()函数来解决，在这里我们使用分治算法来解决这个问题。问题分析，如果这个问题的数据规模小于等于2的时候，我们可以经过一个判断就找到其中的最小值，所以我们需要做的就是想办法把这若干个数据变成两个数据进行比较，那么我们可以先把数据从中间划分为左右两部分，然后通过递归再把每一部分再划分为左右两部分，直到数据规模小于等于2的时候，返回结果，然后通过递归到最后为两个数据对比，我们就可以找到最小值。

关于分治算法，它的实质就是将每个子问题独立，然后递归求解，来帮助我们解决数据规模较大的问题，它的缺点在于当子问题不独立的时候就需要求公共子问题，所以我们在运用的时候一定要考虑一下是否适合分治算法。