第二章 程序设计基础知识
第4节 基础算法
由于篇幅所限，这里主要对基础算法做一些简单的回顾总结，更详细的内容参考《信息学奥赛一本通》相应章节。
一、高精度计算
高精度数值处理是采用模拟算法对位数达到上百位甚至更多位数的数字进行各种运算，包括加法、减法、乘法、除法等基础运算。核心思想是对参与运算的两个数分别用两个数组进行存储。常见问题有“汉诺塔的步数”“国王的米粒”等。
二、穷举算法
穷举法即枚举法，是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立即为其解。常见问题有“百钱买百鸡”“素数判断”等。
三、递推算法
递推法是一种重要的数学方法，在数学的各个领域中都有广泛运用，也是计算机用于数值计算的一个重要算法。递推算法的首要问题是得到相邻数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。常见问题有“斐波那契数列”“过河卒”等。
四、递归算法
递归程序设计是C++语言程序设计中一种重要的方法，它使许多复杂的问题变得简单以及容易解决。递归特点是函数或过程调用自己本身，其中直接调用自己称为直接递归，而将A调用B，B调用A的递归叫做间接递归。常见问题有“汉诺塔问题”“Ackermann函数”等。
五、搜索与回溯算法
搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。常见问题有“八皇后问题”“骑士游历问题”等。
六、贪心算法
贪心算法是指对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。常见问题有“删数问题”“排队打水问题”等。
七、分治算法
分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的子问题，通过对较小规模子问题的求解达到对整个问题的求解。将问题分解成两个较小子问题求解时的分治方法称之为二分法。常见问题有“归并排序”“比赛日程安排”等。
八、广度优先搜索
广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……如此依次扩展，检查下去，直到发现目标节点为止。这种搜索的次序体现沿层次向横向扩展的趋势，称之为广度优先搜索。常见问题有“分油问题”“八数码问题”等。
九、动态规划
动态规划程序设计是解决多阶段决策过程最优化问题的一种途径。动态规划的设计方法对不同的问题，有各具特色的解题方法，不存在一种万能的动态规划算法，可以解决各类最优化问题。需要满足“最优子结构”和“无后效性”的两项基本条件。动态规划解决问题的步骤：
- 确定状态：状态是一个数学形式；
- 确定状态转移方程和边界条件：递归或递推；
- 程序实现。 动态规划大致可以分为以下几类：线性、区间、背包型、树型、数位、状态压缩等。常见问题有“最长不下降序列”“最长公共子序列”等。