### 八大算法思想 >[info]比较笨的枚举算法思想 聪明一点的递推算法思想 充分利用自己的递归算法思想 各个击破的分治算法思想 贪心算法思想并不贪婪 试探性算法思想是一种委婉的做法 迭代算法 模拟算法思想 ### 枚举算法 >将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适则保留，不合适则丢弃。 C语言中，枚举算法一般使用while循环实现。 使用枚举算法解题的基本思路是： 1. 确定枚举对象、枚举范围和判定条件 2. 逐一枚举可能的解，验证每个解是否是问题的解 枚举算法一般按照如下三个步骤进行： 1. 题解的可能范围，不能遗漏任何一个真正的解，也要避免重复 2. 判断是否是真正解的方法 3. 使可能解的范围降至最小，以便提高解决问题的效率  >缺点：当给定的范围太大的时候，一般不选择枚举法，效率太低 >优点：而给定范围比较小，且条件判断清晰简单，可以使用枚举法，程序简单，基本不用考虑效率问题 ### 递推算法 >“稳扎稳打”的策略，不断利用已有的信息导出新的东西。 日常应用中有如下两种递推算法： 1. 顺推法：从已知条件触出发，逐步推算出要解决问题的方法 2. 逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程 ### 递归算法 三个特点； 1. 递归过程一般通过函数或子过程来实现 2. 递归算法在函数或子过程的内部，直接或间接地调用自己的算法 3. 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解 使用递归算法的时候要注意如下4点： 1. 递归是在过程或函数中调用自身的过程 2. 在使用递归策略时，必须有一个明确的递归结束条件，称之为递归出口 3. 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序 4. 在递归调用的过程中，系统用栈来存储每一层的返回点和局部量，如果递归次数过多，则容易造成栈溢出，所以一般不提倡使用递归算法设计程序 ### 分治算法： >将问题分解为多个小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，再次分解为更小的子问题，以此类推，直到找出求解方式为止。 使用分治算法解题的一般步骤如下： 1. 分解，将要解决的问题划分为若干个规模较小的同类问题 2. 求解，当子问题划分得足够小的时候，用较简单的方法解决 3. 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解 ### 贪心算法 >从某一个初始解出发，逐步逼近给定的目标，当达到算法的某一步不能再继续前进时，就停止算法，给定一个近似解。 贪心算法存在以下3个问题： 1. 不能保证最后的解是最优的 2. 不能用来求最大或最小解的问题 3. 只能求满足某些约束条件的可行解的范围 贪心算法的基本思路： 1. 建立数学模型来描述问题 2. 把求解的问题分成若干个子问题 3. 把每一个子问题求解，得到子问题的局部最优解 4. 把子问题的解局部最优解合并成原来解问题的一个解 实现贪心算法的基本过程如下所示： 1. 从问题的某一初始解出发 2. while能向给定总目标前进异步 3. 求出可行解的一个解元素 4. 由所有解元素组合成问题的一个可行解 ### 试探法算法 基本步骤： 1. 针对所给的问题，定义问题的解空间 2. 确定易于搜索的解空间结构 3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索 ### 迭代算法 >用于计算机解决问题的一种基础方法。利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。 使用迭代算法要注意的三个方面： 1. 确定迭代变量 在可以使用迭代算法解决的问题中，至少要存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量 2. 建立迭代关系式 迭代关系式是指如何从变量的前一个值退出其下一个值的公式或关系，通常可以使用递推或倒推的方式来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键 3. 对迭代过程进行控制 在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去，通常可分为如下两种情况来控制迭代过程： ①所需的迭代次数是个确定值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制 ②所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件 ### 模拟算法 >一种最基本的算法思想，解决方法是根据题目给定的规则对题目要求的相关过程进行编程模拟。 在解决模拟问题时，需要注意字符串处理，特殊情况处理和对题目意思的理解。