开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2019.10.03
八大算法思想分别是：枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟算法思想。
1、比较“笨”的枚举算法思想
枚举最大的缺点是运算量比较大，解题效率不高。
2、聪明一点的递推算法思想
（1）顺推法：从已知条件出发，逐步推算出要解决问题的方法
（2）逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件。
3、充分利用自己的递归算法思想
使用递归算法时，应注意以下几点：
（1）递归时在过程或函数中调用自身的过程。
（2）在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
（3）递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡使用递归算法设计程序。
（4）在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。
【递推和递归的差异】
递推多想是多米诺骨牌，根据前面几个得到后面的；
递归是大事化小，比如汉诺塔（Hanoi）问题，就是典型的递归。
如果一个问题的求解既可以用递归算法求解，也可以用递推算法求解，此时往往选择递推算法，因为递推的效率比递归高。
4、各个击破的分治算法思想
先把各个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把他们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，依次类推，直至可以直接求出解为止。这就是分治策略的基本思想。
使用分治算法解题的一般步骤：
（1）分解：将要解决的问题划分成若干个规模较小的同类问题；
（2）求解：当子问题划分得足够小时，用较简单的方法解决；
（3）合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。
1)【！！！！】分治算法解决“大数相乘问题”用Java实现？！未完成
2)欧洲冠军杯比赛日程安排：n个对参赛，比赛n-1天，每个队都要比而且只能比一次，队伍的总数为2^n，请你安排比赛。用Java实现？！未完成
分析：参赛队伍比较多时，降低队伍的规模，直到能够直接进行求解为止，这样使用了分治的思想，同时又有递归的调用。
当为2个队的时候，直接赋值，大于2个队的时候，再进行细分，先确定左上角和右上角，然后再确定左下角和右下角！
分治法能解决的问题一般具有以下4个特征：
（1）当问题的规模缩小到一定的程度就可以容易地解决，此特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加的。
（2）问题可以分解为若干个规模较小的问题，即该问题具有最优子结构性质。此特征是应用分治法的前提。它也是大多数问题可以满足的，此特征反应了递归思想的应用。
（3）（关键）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）各个子问题是相互独立的，即子问题之间不包含公共的子问题。
5、贪心算法思想并不贪婪（追求最优求解，但不一定是能找到最优解）
贪心算法的3个问题：
（1）不能保证最后的解是最优的；
（2）不能用来求最大或最小解问题；
（3）只能求满足某些约束条件的可行解的范围。
贪心算法的思路：
（1）建立数学模型来描述问题；
（2）把求解的问题分成若干个子问题；
（3）对每一个子问题进行求解，得到子问题的局部最优解；
（4）把子问题局部最优解合并成为原来问题的解。
弹性算法的基本过程：
（1）从问题的某一个初始解出发；
（2）While能向给定总目标前进一步；
（3）求出可行解的一个解元素；
（4）由所有解元素组成问题的一个可行解。
贪心算法解决装箱问题，java实现未解决
贪心算法解决找零方案问题，java实现未解决
6、试探法算法思想是一种委婉的做法（也叫回溯法）
试探法解题的基本步骤：
（1）针对所给定问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
试探算法解决“八皇后”问题java实现未解决
试探算法解决“29选7彩票组合”问题java实现未解决
试探法3个要素：
（1）解空间
（2）约束条件
（3）状态树
7、迭代算法（辗转法）
精确迭代
近似迭代：二分法和牛顿迭代法
用迭代算法解决问题时，需要做好3个方面的工作
（1）确定迭代变量：至少存在一个迭代变量
（2）建立迭代关系式：即如何从变量的前一个值推出其下一个值的关系或公式