八大算法思维方法

TIPS：本文共有 1295 个字，阅读大概需要 3 分钟。

枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟算法思想。

一、枚举算法思想（暴力算法）

将问题的所有可能答案一一列举，根据判断条件判断此答案是否合适，一般用循环实现。

经典运用：百钱买百鸡、填写运算符

二、递推算法思想

1.顺推法：从已知条件出发，逐步推算出要解决问题的方法。

2.逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

经典运用：斐波那契数列（顺推法）、银行存款（逆推法）

三、递归算法思想

1.递归过程一般通过函数或子过程实现

2.递归算法在函数或子过程的内部，直接或间接调用自己的算法

3.递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解

注意：必须有一个明确的递归结束条件如果递归次数过多，容易造成栈溢出。

经典运用：汉诺塔问题、阶乘问题

四、分治算法思想

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。

一般步骤：

1.分解，将要解决的问题划分成若干个规模较小的同类问题

2.求解，当子问题划分得足够小时，用较简单的方法解决

3.合并，按原问题的要求，将子问题的解逐层合并构成原问题的解

经典运用：大数相乘问题、比赛日程安排

五、贪心算法思想

从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。

局限：

不能保证最后的解是最优的

不能求最大最小解问题

只能求满足某些约束条件的可行解范围。

基本过程：

1.从问题的某一初始解出发

2.while能向给定总目标前进一步

3.求出可行解的一个解元素

4.由所有解元素组合成问题的一个可行解

经典运用：装箱问题、找零方案

六、试探算法（回溯法）

在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

（为求得问题的正确解，会先委婉地试探某一种可能情况。在进行试探过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探。反复进行，直到得到解或证明无解时才死心）

基本步骤：

1.针对所给问题，定义问题的解空间

2.确定易于搜索的解空间结构

3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

经典运用：八皇后问题、29选7彩票组合

七、迭代算法（辗转法）

是一种不断用变量的旧值递推新值的过程，解决问题时总是重复利用一种方法。

1.确定迭代变量：直接或间接地不断由旧值递推出新值的变量

2.建立迭代关系式：新值与旧值的公式或关系。（解决迭代问题的关系）

3.对迭代过程进行控制：确定迭代过程什么时候结束

所需的迭代次数是个确定值，可以计算出来：可以构建一个固定次数的循环来实现对迭代过程的控制

所需的迭代次数无法确定：需要进一步分析出用来结束迭代过程的条件。

经典运用：求平方根问题

八、模拟算法思想

对真实事物或者过程的虚拟。

经典运用：猜数字游戏、掷骰子问题

八大算法思维方法

    算法其实是一种思维模式，本文就简单介绍一下八种常用算法思想，分别是 枚举、递推、递归、分治、动态规划、贪心、回溯和模拟 。

如果觉得《八大算法思维方法》对你有帮助，请点赞、收藏，并留下你的观点哦！