软考-算法-策略（下）

答案

1.1 - 1.3：B A A
2.1 - 2.9：B C D B B A B C B
3.1 - 3.9：A B C A D C B B C
4.1 - 4.6：A C C B D A

知识点分析

《分治法》
【思想】通过递归实现，每层有三个步骤：分解、求解、合并。并注意递归的边界/退出条件与递归模式。
例：快速排序、归并排序。
（1）分解。将原问题分解成一系列子问题。
（2）求解。递归地求解各子问题。若子问题足够小，则直接求解。
（3）合并。将子问题的解合并成原问题的解。

《动态规划法》
【思想】与分治法不同的是，经分解得到的子问题往往不是独立的。
例：0/1背包问题、最长公共子序列。
（1）找出最优解的性质，并刻画其结构特征。
（2）递归地定义最优解的值
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。

《贪心法》
【思想】局部最优解，过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。
例：找零问题、完全背包问题。
（1）最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
（2）贪选选择。指问题的整体最优解可以通过一系列局部最优的选择，即通过贪心选择来得到。

《回溯法》
【思想】以深度优化的方式系统地搜索问题的解决方法。界限函数的设计是回溯法的一个核心问题。
例：迷宫、八皇后。
（1）针对所给的问题，定义问题的解空间。
（2）确定易于搜索的解空间结构
（3）以深度优先的方式搜索解空间。

工作注意

目前工作中用的最多的策略是
【洗牌算法】随机打乱顺序、一维或二维数组转化、取前N个随机数等。
【深度优先】通常要比广度优先最新找到结果。
例：抢红包、扫雷。

image.png