信息学奥赛知识点(十一)程序基本常识
计算机的应用已不再局限于科学计算，而更多地用于控制、管理和数据处理等非数值计算的处理工作。为了编写一个"好"的程序，必须分析待处理的对象特性以及各处理对象之间存在的关系。
1．算法
算法是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。简单地说，算法就是解决问题的操作步骤。
一个算法必须满足以下五个重要的特征。
(1）有穷性
对于任意一组合法的输入值，算法的每个操作步骤都能在有限的时间内完成，这包括合理的执行时间的含义。如果一个算法执行耗费的时间太长，即使最终得出了结果，也是没有意义的。
(2）确定性
算法中的每一步都必须有明确的定义，不允许有歧义性和多义性。确定性使算法的执行者或者阅读者能够明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径。
(3）输入
一个算法应该有0个或多个输人，以刻画运算对象的初始情况。所谓0个输入，是指有的算法表面上可以没有输人，实际上已被嵌入算法之中。
(4）输出
一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
(5）可行性
一个算法必须遵循特定条件下的解题规则，算法描述的每一个操作都应该是特定的解题规则中允许使用的、可执行的，并可以通过执行有限次来实现。
2．算法的复杂度
同一个问题可用不同的算法来解决，而一个算法质量的优劣将影响算法乃至程序的效率。算法分析的目的在于选择合适的算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
(1）时间复杂度
基本运算次数来度量。算法的时间复杂度（ Time Complexity ）是指算法所需要的计算工作量，用算法所执行的
常见的时间复杂度有：常数阶 O (1)，对数阶 O (log2n)，线性阶 O ( n )，线性对数阶 O (nlog2n)，平方阶 O (n^2)，立方阶 O ( n^3),……，指数阶 O (2^n)。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率将越低。
(2）空间复杂度
算法的空间复杂度（ Space Complexity ）是指执行这个算法所需要的内存空间。算法执行期间所需的存储空间主要包括三部分：输入数据所占的存储空间、程序本身所占的空间和算法执行过程中所需的储存空间。
3.算法的基本结构
算法的结构不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一般一个算法可以用顺序、选择和循环三种基本结构组合而成。
(1）顺序结构
顺序结构是最简单、最常用的算法结构，语句与语句之间、框与框之间按从上到下的顺序进行。
(2）选择结构
选择结构是先根据条件做出判断，再决定执行哪一种操作的算法结构，它必须包含判断框。当条件 P 成立（或称为真）时执行 A ，否则执行 B ，不可能两者同时执行，但 A 或 B 两个框中可以有一个是空的，即不执行任何操作。
(3）循环结构
在一些算法中，经常会出现从某处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构。反复执行的处理步骤为循环体，它可以细分为两类：当型循环结构和直到型循环结构。
4．基础算法
(1）高精度计算
利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度不断提高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。主要涉及高精度的加、减、乘、除运算，实现的时候采用逐位加、减、乘、除即可。
常见问题有"汉诺塔的步数""国王的米粒"等。
(2）穷举算法
所谓穷举法，即枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的、哪些是有用的。能使命题成立，即为其解。
有些问题可以用循环语句和条件语句直接求解，有些问题用循环求解时循环次数太多，无法编写程序，则需要用到回溯、递归、分治等方法。
常见问题有"百钱买百鸡""素数判断"等。
(3）数据排序
排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。
排序的方法很多，下面根据初赛的要求，简单介绍各种常见排序算法在一些方面的比较，尤其是时间复杂度和稳定性两个方面。稳定性，指在原序列中相同元素的相对位置与排好序的新序列中相同元素的相对位置是否相同。若相同，则该算法是稳定的，否则不稳定。
时间复杂性比较：
插入排序、冒泡排序、选择排序的时间复杂性为 O (n2);
其他非线性排序的时间复杂性为 O ( nlogn );
线性排序的时间复杂性为 O ( n )。
稳定性比较：
插入排序、冒泡排序、二叉树排序、归并排序及其他线性排序是稳定的；
选择排序、希尔排序、快速排序、堆排序是不稳定的；
辅助空间的比较：
线性排序、归并排序的辅助空间为 O ( n )，其他排序的辅助空间为 O (1)。
其他比较：
①插人、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序慢了，时间复杂度会达到其上限。当数据为随机数据时，快速排序远远快于插入、冒泡、选择排序，时间复杂度接近其下限。
②当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插人或冒泡排序。
③若待排序的记录的关键字在一个明显有限范围内且空间允许时用桶排序。④当 n 较大时，关键字元素比较随机且对稳定性没要求，宜用快速排序。
⑤当 n 较大时，关键字元素可能出现本身是有序的且对稳定性有要求时，在空间允许的情况下，宜用归并排序。常见问题有"合并果子""逆序对问题"等。
(4）递推算法
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
常见问题有"斐波那契数列""过河卒"等。
(5）递归算法
递归程序设计是 C +＋语言程序设计中的一种重要方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将 A 调用 B , B 再调用 A 的递归叫作间接递归。
常见问题有"汉诺塔问题"" Ackerman 函数"等。
(6）搜索与回溯算法
搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其他方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其他方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
常见问题有"八皇后问题""骑士游历问题"等。
(7）贪心算法
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以，对所采用的贪心策略，一定要仔细分析其是否满足无后效性。
常见问题有"删数问题""排队打水问题"等。
(8）分治算法
分治就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。
常见问题有"归并排序""比赛日程安排"等。
(9）广度优先搜索
广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……如此依次扩展，检查下去，直到发现目标节点为止。这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。
常见问题有"分油问题""八数码问题"等。
(10）动态规划
动态规划程序设计是解决多阶段决策过程最优化问题的一种途径、一种方法，而不是一种特殊算法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。需要满足"最优子结构"和"无后效性"的两项基本条件。实现时主要分成几个步骤：划分阶段、确定状态和状态变量、确定决策并写出状态转移方程、寻找边界条件、程序设计实现。大致可以分为以下几类：线性、区间、背包形、树形等。
常见问题有"最长不下降序列""最长公共子序列"等。
