算法专题 信息学基本解题流程

　　算法专题(1)-信息学基本解题流程!

　　一、 基本解题流程

　　1.概述：

　　信息学中解算法题跟数学中解应用题十分类似，大致分为以下四个步骤：题意理解与模型建立、算法设计与复杂度分析、代码编写、调试。

　　知识点梳理：

　　题意理解与模型建立

　　题意理解是算法设计的步，也是非常关键的一步。与做数学应用题一样，需要将原题抽象成相对应的数学或逻辑形式，再参考不同的模型进行建模。常见的模型有搜索模型、组合数学模型、动态规划模型、树图模型等。

　　算法设计与复杂度分析

　　设计算法与分析复杂度是整个解题过程中较重要的部分。设计算法时，需要考虑算法的正确性，尤其是对于贪心类型的题目求解时。分析复杂度可以大致确认算法能跑多快，在比赛中可以过多少个数据点。

　　通常来讲，计算机在一秒内的运算次数大致是107(千万)到108(亿)的量级，如果把n代入复杂度的表达式，得数大于107，就会有超时的可能。

　　代码编写

　　写代码之前，在纸上写一下伪代码，既可以帮助整理思路，也可以加快代码编写的速度。在代码的编写过程中，变量命名规则，循环中左右括号的分布(左括号是否换号)，缩进等需要有一个固定的格式。这样不仅可以使得代码更加美观，也可在后续调试中减少不必要的麻烦。关键代码部分应适当加些注释，方便自己调试。

　　代码调试

　　在代码编写完成后，不能增加其完全正确，这时候，需要对其进行调试。调试过程大致分为以下几点：

　　静态查错：不要运行程序。静下心来，慢慢地用你的思路、框图和伪代码检查代码，看是否有打错的或者漏打的内容。一般要先查局部，后查整体。(调试前先静态查错，如果忽略，很容易因为长时间找不到错误而造成紧张、焦虑的情绪，从而影响答题。)

　　黑箱测试：测试示例。如果示例的结果都不对，就应该考虑算法的正确性，并检查代码是否写错。

　　构造小数据：根据程序功能设计几个数据，检查程序是否计算出正确结果。

　　构造极端数据：在时间允许的情况下，按照题目中的数据要求，尝试构造极端数据，测试自己的程序。

　　输出中间结果：有时候程序的结果不正确，但通过直接观察代码无法找到问题，可在代码中的关键部分输出中间结果，以查看代码中哪部分有错。注意：在提交之前，需要将这些用于调试的输出注释掉。

　　单步调试：有些情况下，在输出中间结果调试时仍然找不到问题，可以进行单步调试。要注意耐心。

　　重难点分析：

　　• 题意必须理解透彻，模型需要建立正确。

　　• 算法设计时，需要把握其正确性(尤其是贪心算法)和可行性(算法复杂度)。

　　• 伪代码很重要，代码中适当的注释也是必要的。代码编写时需注意细节。

　　• 代码调试时，应先静态后动态，先整体后局部。

　　•

　　例题解析：

　　例题1-1：数字三角形

　　【问题描述】有一个层数为n (n≤1000) 的数字三角形(如下图)。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过数 字的总和的较大值。

　　1

　　6 3

　　8 2 6

　　2 1 6 5

　　3 2 4 7 6 较大值=1+3+6+6+7=23

　　【分析】本题题目描述比较清晰，可按照题目意思直接理解题意，也可构建模型。模型构建后，本题可抽象为一个图，图中共有n层顶点(n≤1000)，每个顶点有一个权重，第i层的顶点有i个，其中第i层中第k的顶点与i+1层中第k和k+1个顶点有路径。需要求解的是，从第1层走到第第n层的路径中，经过顶点权重和较大的路径的权重和。

　　题意理解后，接下来就是要设计算法。本例题中，一个朴素的算法是直接模拟。先从(1,1)点开始，每次向下左下或者右下走，记录路径上的数字和，当走到第n层的时候结束，记录可行解。继续模拟，直到所有可能情况都被计算过。记录较大的数字和，算法结束。

　　上述算法简单易懂，但是实现起来复杂度很高。对于i层第k个节点(i,k)，可以向左下走到(i+1,k)或向右下走到(i+1,k+1)，每个节点上都有两种可行方案，每一次模拟需要走n个节点。那么需要模拟的次数是2(n-1)，也就是说，时间复杂度是O(2(n-1))。这种复杂度下，显然不能在限定时间内出解。

　　当一开始设计的算法复杂度无法满足要求时，需要考虑更有效的算法。本例中，因为只要求解可行路径上的较大顶点和，那么对于节点(i,k)只要保存走到这个节点时，已走路径的较大顶点和，记作f(i,k)。由于蚂蚁只能往下走，不会再回头。对于节点(i,k)，它的较大值只可能从节点(i-1,k-1)或节点(i-1,k)中更新，即

　　较后只要求解第n层中f的较大值即可。由于每个节点只会被更新一次，时间复杂度变为O(n*(n+1)/2)，即O(n2)。该方法运用的是动态规划的思路，在之后动态规划的章节会具体讲述。

　　例题1-2：作业调度方案(NOIP2006)

　　【问题描述】我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

　　每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号;k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。

　　例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。

　　一方面，每个操作的安排都要满足以下的两个约束条件。

　　(1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始;

　　(2) 同一时刻每一台机器至多只能加工一个工件。

　　另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。

　　由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。

　　还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。

　　例如，取n=3,m=2，已知数据如下：

　　工件号 机器号/加工时间

　　工序1 工序2

　　1 1/3 2/2

　　2 1/2 2/5

　　3 2/2 1/4

　　则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。

　　当一个操作插入到某台机器的某个空档时(机器上较后的尚未安排操作的部分也可以看作一个空档)，可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在增加约束条件(1)(2)的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在增加约束条件(1)(2)的条件下，插入到较前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。

　　显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是的，请你计算出该方案完成全部任务所需的总时间。

　　【输入】

　　行为两个数：m n(其中m<20表示机器数，n<20表示工件数)

　　第2行：2n个用空格隔开的数，为给定的安排顺序。

　　接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。

　　其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。后n行依次表示每个工件的每个工序的加工时间。可以增加，以上各数据都是正确的，不必检验。

　　【输出】

　　输出只有一个正整数，为较少的加工时间。

　　【样例输入】

　　2 3

　　1 1 2 3 3 2

　　1 2

　　1 2

　　2 1

　　3 2

　　2 5

　　2 4

　　【样例输出】

　　10

　　【分析】本题题目冗长，需耐心读题，理解题意。本题中较重要的内容是两个约束与两个约定。

　　约束：

　　• 对同一个工件，每道工序必须在它前面的工序完成后才能开始;

　　• 同一时刻每一台机器至多只能加工一个工件。

　　约定：

　　• 增加约束条件(1)(2)的条件下，尽量靠前插入

　　• 如果有多个空档可以插入，就在增加约束条件(1)(2)的条件下，插入到较前面的一个空档。