您好、欢迎来到现金彩票网!
当前位置:在线斗牛棋牌游戏 > 伪代码 >

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

发布时间:2019-07-22 04:25 来源:未知 编辑:admin

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

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

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

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

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

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

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

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

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

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

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

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

  【分析】本题题目描述比较清晰,可按照题目意思直接理解题意,也可构建模型。模型构建后,本题可抽象为一个图,图中共有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 1 2 3 3 2”。

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

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

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

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

  第一行为两个数:m n(其中m20表示机器数,n20表示工件数)

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

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

  理解了这些约束与约定,本题就是一个简单的模拟题。按照题目所给的安排顺序进行模拟,对于顺序中的每一个工件,根据约束与约定,插入到机器中。返回搜狐,查看更多

http://missartypants.com/weidaima/361.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有