让我们一同踏上收集算法的旅程吧

本书概要

本书是为攻克程序设计竞赛而撰写的参考书,书中讲解了大量竞赛相关的算法与数据结构。同时,本书又是一本入门图书,能带领初学者系统学习算法与数据结构的基础知识。

在程序设计竞赛中,优秀的数理能力是争取好名次的有力武器,但对于很多初学者而言,应用基础算法才是攻克眼前问题的最佳战略。也就是说,只要学会用“基础”解决问题,就能够提升自己的名次,在竞赛中获得更多乐趣。

另外,学习基础的过程并没有我们想象中那样痛苦乏味。将所学融会贯通、用技巧破解难题、收集算法网罗数据结构,这些乐趣都能在学习过程中体会得到。

为了让各位能在学习和解题过程中感受到上述乐趣,本书将借助在线评测(一种与程序设计竞赛系统相类似的自动评分系统)来讲解算法和数据结构。

enter image description here

通过在线评测掌握的算法与数据结构可以成为我们的知识储备,也可以作为库A 的一部分直接应用到程序设计竞赛之中。不过,要想在竞赛中名列前茅,还需要更加高超的算法以及灵活的思维和数理能力。本书虽然不能直接帮助各位在程序设计竞赛中跻身前列,但会在讲解在线评测使用技巧的同时,为各位简单介绍适用于竞赛的学习方法。

A 可直接调用的通用程序的集合称为库。

致教职员工

本书从算法的概要与计算效率的概念入手,涵盖了信息处理技术人员、程序员必备的通用算法、数据结构的相关问题,以及对这些问题的讲解和参考答案。因此,本书不但是一本专为程序设计竞赛服务的参考书,同时也是一本程序设计、算法与数据结构等相关科目的教材。

有效运用在线评测

算法和数据结构与单纯的知识不同,只靠阅读并不能将其转化为自己的东西。因此,我们需要将例题的答案(代码)落实到环境中,通过实际运行来检验其正误与性能。不过,我们根据算法编写的程序往往会含有Bug,或者算法效率达不到规格要求。这种情况下,在线评测会根据严格的测试数据(虽然我们也能亲自编写类似的测试数据,但这会浪费大量时间与精力)检查程序是否有缺陷,帮助我们在“正确实现程序”的过程中学习算法与数据结构。此外,反复学习还能给我们带来以下好处。

作为一名信息处理技术人员或程序员,必备的基础算法与数据结构的相关知识涉及面极广,而反复学习能帮助我们掌握这些知识

反复学习能帮助我们掌握程序员必备的技巧,具体说来就是准确理解文章要义,编写程序时能忠实于需求且极力避免Bug。此外,在设计和编写程序时还能够兼顾计算机资源、计算效率和内存使用量等

另外,每当我们独立解决一个问题,看到在线评测给出“正确”的评判时,都会自然而然地感到些许喜悦。保持人们的积极性,寓教于乐,这也是在线评测的魅力所在。通过累积经验来解决新的问题,再将解决新问题的经验化为武器进一步挑战更高难度,这与游戏并没有什么两样。在这一过程中,我们可以把学到的技巧转变为自己的收藏品,久而久之,程序设计便会成为一种爱好。

本书涉及的问题

本书的例题以在线评测系统中的各问题为原型,如图2 所示,以卡片形式提出。

enter image description here

这种卡片中包含了问题的概要,具体由以下信息组成。

基本信息。显示在线评测的问题ID、题目、CPU 和内存限制、正答率等基本信息。其中限制时间是指所提交程序的执行时间

输入与输出。用插图简要说明程序所需的输入以及输出结果

算法。用插图简要说明解题所需的算法。标为“?”时需要各位自行拟定算法,各位可以将这个过程视为一种思考的乐趣

难度。思考、实现的难度最高为5 颗★。★记1 分,☆记0.5 分。“思考”分数越高算法越难,“实现”分数越高代码量越大。不过,代码量是指算法和数据结构中没有使用标准库时的量

所需技能(图标)。表示解决该问题所必需的前提技能。本书虽然不要求各位严格按照顺序解题,但还是推荐各位在掌握各问题所需技能之后再进行挑战

可获得的技能(图标)。解决该问题后可以学到的技能。在后面的问题中,这些技能都会出现在“所需技能”之中。通过本书可以获得的技能一览表见附录1除“变量”和“四则运算”这两个编程基础之外,阅读本书首先要具备如图3 所示的七种技能。

enter image description here

只要学习过任何一门编程语言(C/C++ 或Java 等)的基础知识,这些技能就应该不在话下了。如果对这方面没有自信,建议各位先找一些入门书籍来预习一番。

本书涉及的都是信息处理中基础且通用的问题,其中一些问题在很多语言中已经被纳入程序库。不过,学习标准库的内部结构有助于我们对其性能和动作(能做什么不能做什么)有进一步了解,这对于使用库的程序员来说意义重大。

另一方面,本书将在各章节中适时穿插C++ 标准模板库(STL)通用算法和数据结构的介绍,并将其与基本算法和数据结构相结合,以挑战一些略有难度的问题。

如何有效运用本书

本书各章的组成项目如图4 所示(根据每章情况不同,第1 项和第4 项可能被省略)。

enter image description here

在各章的开头部分,我们会先简要说明与该章主题相关的用语及概念,同时介绍一些基础算法与数据结构的概要。之后的各小节则分别包含下述项目。

“问题”就是实际挑战的例题,“讲解”是对解题时所用算法的细节以及实现方法的详细说明。各位请将这两部分视为“一对儿”,然后根据自己的情况决定何时开始编写代码。比如,我们根据难度和经验构思了以下两种学习顺序。

问题→讲解→编码→考察和参考答案

本书涉及大量基础问题(帮助读者了解基础算法知识的问题),因此初学者往往很难在阅读问题之后立刻开始编写代码。这时不必勉强自己写出答案,可以在阅读过“问题”与“讲解”之后再进行挑战。如果无论如何都通不过在线评测,不妨看一下参考答案。另外,即便已经做出正确答案,也要记得与“考察”和“参考答案”进行对比,看看自己的实现方法有没有需要改善的地方。

问题→编码→讲解→考察和参考答案

阅读“问题”之后,如果觉得自己能够在没有任何提示的情况下解开问题,便可以直接尝试编码。如果能顺利通过在线评测,证明你已经掌握了这部分知识。不过,通过评测后也不要忘记查看“讲解”和“考察”,因为本书所给的解法或许能给各位带来新的发现。

“考察”部分中,我们会一同考察示例解法的复杂度,以及算法中值得一提的特征和需要注意的地方。

“参考答案”中将提供一份能实际通过在线测评的C 或C++ 语言代码,供各位读者参考。不过各位要清楚,每个程序设计问题的解法都不是唯一的,参考答案并不一定是最优秀的实现方法。

本书的支持网站

该网站上公布了本书的补充内容和勘误,请根据需要参考。

http://www.ituring.com.cn/book/1739

• 本书内容可灵活运用会津大学的Aizu Online Judge(会津大学在线评测,简称AOJ)

Aizu Online Judge(AOJ)http://judge.u-aizu.ac.jp

• AOJ 可免费使用,但是需要注册。详情请参考本书第1 章中的内容

  Aizu Online Judge Version 1.0 ©2004 - 2015 AIZU Competitive Programming Club,Database Systems Lab. University of Aizu

• 本书中的内容仅以提供信息为目的。在编写本书的过程中,我们力求准确表述,但在本书的使用过程中,著者和Mynavi 出版社、人民邮电出版社及译者均不对本书内容作任何保证,对于因对本书内容运用不当而导致的任何问题均不负责。对本书的使用由个人负责,请知悉

• 本书中的报道、产品名称和URL 等均为截止至2014 年12 月的内容。在使用过程中,这些内容可能会有变更,请知悉

• 本书中的公司名称和产品名称等多为各公司注册商标或商标。正文中将省略©、®、TM 等符号

评论

本文目前还没有评论……

我要评论

需要登录后才能发言
登录未成功,请修改提交。