找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

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

admin 2019-6-4 22:06 200人围观 C++相关

点击上面微信号关注我

关注我哟
定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!有任何问题请联系小编!

NOI2019 夏令营课程报名中!<点击查看




摘要

    本次系列文章主要介绍信息学以下知识点:



今天我们主要看信息学基本解题流程:

一、 基本解题流程

1.概述:


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

2. 知识点梳理:


Ø 题意理解与模型建立

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

Ø 算法设计与复杂度分析

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

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



Ø 代码编写

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

Ø 代码调试

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

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

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

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

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

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

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

3. 重难点分析:


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

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

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

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

4. 例题解析:

例题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)的条件下,插入到最前面的一个空档。


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





往期精选内容

(点击标题即可查看)

NOI2019 夏令营课程报名中!

2019年NOI省队选拔规定及NOI2019名额分配方案发布!

信息学竞赛入选!2019年度面向中小学生全国性竞赛活动名单公示

关于举办第34届全国青少年科技创新大赛的通知

最详细解析低分进名校三大途径:自主招生、综合评价、高校专项计划!

2018年自主招生高校对信息学奖项报考要求及优惠政策参考!报考时要注意哪些问题?


2019年保送生资格名单公示

NOIP2018复赛提高组各省中学 获一等奖人数排行榜及分析!

NOIP2018复赛提高组各省各中学获奖总数排行榜

NOIP2018各省各中学复赛普及组获奖总数分析!

CCF NOI2019冬令营报到通知及冬令营名额分配方案!

再见,OI-大牛HZW亲笔,分享OI生涯记录,不变的是坚持和热爱!

NOIP复赛知识点简述及复赛算法总结!

重磅!NOIP2018初赛普及组提高组真题及答案发布

NOIP2018提高组试题解析


根据信息学竞赛之路带你了解信息学竞赛流程

清华“姚班”2018级名单-看50名学霸到底多牛,同学们又如何能进姚班?

全国自主招生高校对各项学科竞赛奖项要求大汇总!签约路径

教育部出台高中新课标,信息学竞赛相关内容被编入必修课程!


北京大学自主招生初审通过1719人名单公布,看清华北大更青睐哪些省市中学?

IOI 2018国际信息学奥林匹克竞赛中国代表队选拔结果揭晓,看大牛们的竞赛之路!
2018年五大学科竞赛国家队名单全部出炉,各省中学大比拼!

从搜狗CEO王小川(信息学金牌),看这二十几年中国奥赛金牌的去向

揭晓高薪专业排行榜,计算机专业薪资最高!哪些专业最具潜力?

2018中国大学排行榜出炉,北大清华连续11年蝉联冠亚军


一个清华保送生妈妈对竞赛的感受,自主招生家长都要看看!

计算机科学与技术专业全国大学排行榜!


为什么这些孩子初中就能被清华北大签约

2018五大学科竞赛国家集训队成员及所在学校名单


(1)为什么有“编程思维”和数学能力强的人更优秀?
(2)清北独家录制NOIP成功者说学习视频!!!

(3)我们为什么要对孩子进行编程教育?

(4)信息学竞赛答家长问题

1.信息学竞赛,你想了解的知识都在这里

2.信息学奥赛(NOIP)初赛学习方法推荐

3.信息学奥赛(NOIP)复赛学习方法推荐

4.大牛为你推荐十本最适合信息学竞赛的书籍

5.信息学奥赛有那么重要吗?

6.参加编程竞赛对实际工作的用处

7.清北学堂独家录制NOIP考试技巧讲座

8.在线编程挑战赛第一名:我是这么学算法的

9.信息学竞赛如何学习及准备攻略!

10.凭什么我得了信息学奥赛国家一等奖

11.榜样 | 北大降200分要这个诸暨天才少年

12.OI金牌教练胡芳:爱和成长的故事

13.信息学竞赛,一个让孩子不需要再去挤独木桥的方向

14.新学期必须了解的学科竞赛与自主招生时间!

15.北大录取生陈代超:在信息学中找到“思维图谱”

16.国务院发文支持编程教育进入中小学,中国人工智能厚积薄发

(1)NOIP报名,申诉,查成绩方式介绍

(2)NOIP复赛考前需要注意的那些事儿!!!

(3)NOIP测评环境,数据提交你都了解吗?请注意这些问题!

(4)关于NOI系列赛编程语言使用限制的规定



关注「信息学竞赛」

看更多信息学趣闻与知识

↓↓↓




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:信息学竞赛,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......