基本信息
- 作者: 刘汝佳
- 丛书名: 算法艺术与信息学竞赛
- 出版社:清华大学出版社
- ISBN:9787302356288
- 上架时间:2014-6-5
- 出版日期:2014 年6月
- 开本:16开
- 页码:464
- 版次:2-1
- 所属分类:计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
编辑推荐
如果你是一名程序员,如果你参加NOIP、NOI、ACM/ICPC竞赛,只要你对算法感兴趣,那就来吧!就是这本被最多程序员所喜爱、被大量学校广泛作为教材的算法竞赛经典之作!
算法竞赛入门经典一书全新改版,页码翻倍,奇葩?非也,这是因为:
◆第一版内容太少,让人感觉意犹未尽。
◆有些内容有点过时,需要与时俱进。
◆C++的介绍太少,例题太少,学有余力的同学在入门完之后有些迷茫。
此次改版就是针对这些不足,所以很让人期待!
内容简介
计算机书籍
《算法竞赛入门经典(第2版)》是一本算法竞赛的入门与提高教材,把C/C++语言、算法和解题有机地结合在一起,淡化理论,注重学习方法和实践技巧。全书内容分为12 章,包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、C++与STL入门、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法、高级专题等内容,覆盖了算法竞赛入门和提高所需的主要知识点,并含有大量例题和习题。书中的代码规范、简洁、易懂,不仅能帮助读者理解算法原理,还能教会读者很多实用的编程技巧;书中包含的各种开发、测试和调试技巧也是传统的语言、算法类书籍中难以见到的。
《算法竞赛入门经典(第2版)》可作为全国青少年信息学奥林匹克联赛(NOIP)复赛教材、全国青少年信息学奥林匹克竞赛(NOI)和ACM国际大学生程序设计竞赛(ACM/ICPC)的训练资料,也可作为IT工程师与科研人员的参考用书。
作译者
学生时代曾为中国计算机学会NOI科学委员会学生委员,担任IOI2002-2008中国国家队教练,并为NOI系列比赛命题十余道。现为NOI竞赛委员会委员,并在NOI 25周年时获得中国计算机学会颁发的“特别贡献奖”。
2004年至今共为ACM/ICPC亚洲赛区命题二十余道,担任6次裁判和2次命题总监,并应邀参加IOI和ACM/ICPC相关国际研讨会,发表论文两篇。
2004年初作为第一作者出版专著《算法艺术与信息学竞赛》,2009年出版译著《编程挑战》,2009年出版《算法竞赛入门经典》,2012年出版《算法竞赛入门经典——训练指南》。
多年来在全国二十余个城市进行中学生竞赛培训工作,为北京、上海、吉隆坡等地的著名高校授课与宣讲,并多次与TopCoder、百度和网易有道等知名企业合作举办比赛,让更多的IT人才获得展示自我的平台。
目录
第1部分语言篇
第1章程序设计入门 1
1.1 算术表达式 1
1.2 变量及其输入 3
1.3 顺序结构程序设计 6
1.4 分支结构程序设计 9
1.5 注解与习题 13
1.5.1 C语言、C99、C11及其他 13
1.5.2 数据类型与输入格式 14
1.5.3 习题 15
1.5.4 小结 16
第2章循环结构程序设计 18
2.1 for循环 18
2.2 while循环和do-while循环 22
2.3 循环的代价 25
2.4 算法竞赛中的输入输出框架 27
2.5 注解与习题 34
2.5.1 习题 34
2.5.2 小结 36
前言
《算法竞赛入门经典》第1版出版至今已有四个年头。这四年间发生了很多变化,如NOI系列比赛终于对STL“解禁”,如C11和C++11标准出台,g++编译器升级(直接导致本书第1版中官方使用的<?和>?运算符无法编译通过),如《算法竞赛入门经典——训练指南》的出版弥补了本书第1版的很多缺憾,再如ACM/ICPC的蓬勃发展,使更多的大学生了解并参与到了算法竞赛中来……
看来,是时候给本书“升级”了。
主要的变化
我原本打算只是增加一章专门介绍C++和STL,用符合新语言规范的方式重写部分代码,顺便增加一些例题和习题,没想到一写就是100页——几乎让书的篇幅翻了一倍。写作第1版时,220页的篇幅是和诸位一线中学教师商量后定下来的,因为书太厚会让初学者望而生畏。不过这几年的读者反馈让我意识到:由于篇幅限制,太多的东西让读者意犹未尽,还不如多写点。虽然之后出版了《算法竞赛入门经典——训练指南》,但那本书的主要目标是补充知识点,即拓展知识宽度,而我更希望在知识宽度几乎不变的情况下增加深度——我眼中的竞赛应该主要比思维和实践能力,而不是主要比见识。
索性,我继续加大篇幅,用大量的例子(包括题目和代码)来表现我想向读者传达的信息。一位试读的朋友在收到第一份书稿片段时惊呼:“题目的质量比第1版提高太多了!”这正是我这次改版的主要目的。
具体来说,这次改版有以下变化:
在前4章中逐步介绍一些更实用的语言技巧,直接使用竞赛题目作为例子。
全新的第5章,讲解竞赛中最常用的C++语法,包括STL算法和容器。
第6~7章作为基础篇,加大代码和技巧的比例,并适当增加例题。
第8~11章作为中级篇,增加了各种例题,着重锻炼思维能力。
全新的第12章作为高级篇,在《算法竞赛入门经典——训练指南》的基础上补充少量知识点与大量精彩例题。
需要特别说明的是第12章出现的原因。这一章的内容很难,而且要求读者熟练掌握《算法竞赛入门经典——训练指南》的主要内容,看起来和“入门”二字是矛盾的。其实本书虽然名为“入门经典”,实际上却不仅只适合入门读者。根据这几年读者反馈的情况来看,有相当数量的有经验的选手也购买了本书。原因在于:很多有经验的选手属于“自学成才”,总觉得自己可能会漏掉点什么基础知识。事实也是如此:本书中提到的很多代码和分析技巧是传统教科书中见不到的,对于很多有经验的选手来说也是“新鲜事物”,并且他们能比初学者更快、更好地把这些知识运用到比赛中去。本书第12章就是为这些读者准备的。如果这样解释还不够直观,就把第12章作为一个游戏里通关后多出来的Hard模式吧!
阅读说明
既然内容有了较大变化,阅读方式也需要再次说明一下。首先,和本书第1版一样,本书最好是有人带着学习,如老师、教练或者学长。随着网络的发展,这个条件越来越容易满足了——就算是没人指导,也可以在别人的博客中留言,或者在贴吧中寻求帮助。
一定要重视书中的“提示”。书中有很多“提示”部分都是非常重要的知识点或者技巧,有些提示看似平凡无奇,但如果没有引起重视而导致赛场上丢分,可是会追悔莫及的。
接下来是关于新增第5章的。首先声明一点,这一章并不是C++语言速成——C++语言是不可能速成的。这一章不是说你从头读到尾然后就掌握C++了,而是提供一个纲要,告诉你哪些东西是算法竞赛中最常用的,以及这些东西应当如何使用。你可以先另外找一本书(或者阅读网上的文章)学习C++,然后再看本书第5章(目的是把那些又容易晕又不那么有用的知识从脑子里删除),也可以直接看本书第5章,每次遇到看不懂或者觉得不够详细的地方,再找其他参考书来学。顺便说一句,就算你已经非常熟悉C++了,也最好浏览一下第5章(特别是代码!)。这不会花费太多时间,但很可能学到有用的东西。
忍不住再说点题外话。有时学习算法的最好方法并不是编写程序,而是手算。“手算”这个词听上去有点枯燥,改成“玩游戏”如何?如《雷顿教授与不可思议的小镇》就是一个不错的选择——它包含了过河问题(谜题7、93)、找砝码(谜题6、131)、一笔画(谜题30、39)、n皇后(谜题80~83,130)、倒水问题(谜题23、24、78)、幻方(谜题95)、华容道(谜题97、132、135)等诸多经典问题。
致谢
虽然多出来了200多页,其实本书的改版工作并没有花费太长时间(不到半年),在此期间也没有麻烦太多朋友读稿和讨论。参与本书第2版读稿和校对工作的几位朋友分别是:陈锋(第8~11章)、王玉斌(第8~9章,第12章)、郭云镝(第12章)、曹海宇(第5章、第9章)、陈立杰(第12章)、叶子卿(第12章)、周以凡(第12章)。
序言
在我的书案上常年摆着一本蓝皮的书《算法艺术与信息学竞赛》,这是刘汝佳与黄亮合写的书,2003年12月我怀着喜悦的心情给这本书写了一页纸的序言。今天,时隔十年,我又拿起笔来为汝佳的新书作序,想到信息学奥林匹克的魅力,看到我们的学生能够承担起普及的责任和水平,此时此刻我的欣喜之情难以言表。“青出于蓝更胜于蓝”是我们当老师的最大愿望和期盼。汝佳之所以能写出这种内容和内涵丰富,文字也很难表达的思维艺术之美的好书,在于他对于信息学竞赛的热爱和他在青少年中普及计算机知识的强烈的责任感。汝佳为人低调诚实,做事认真负责,最可贵之处是那种“打破砂锅问到底”的求真务实精神,还有就是愿意和善于与人合作共事,能够真心听取别人的意见。
刘汝佳在中学参加信息学奥赛,进入清华大学后作为主力队员参加过ACM/ICPC世界大学生程序设计大赛,在本科和读研期间又长期担任国际信息学奥林匹克中国队的教练。很早以前他就说过:想写一本“从入门开始就能陪伴着读者的书”,意思是书的作用不仅是答疑、解惑,更是像朋友和知己,同读者一起探讨和研究问题。我当然赞成著书者的境界,在我给本科生上“程序设计基础”课时的感悟是:教学相长,发挥学生在学习中的主体作用,激发兴趣和调动积极性,创造条件,使其参与课程内容的研讨,并提出宝贵意见,是成就精品课的必由之路。汝佳说:“书的第12章就像是一个路标,告诉你每条路通往怎样的风景,但是具体还得靠读者自己走过去,在走之前也需要自己选择。”话说得很到位。闪光的东西蕴含在解决问题时的那些思维之美中,精妙的解题思路和策略有时令人拍案叫绝,一路学一路体味赏心悦目的风景,没有不爱学和学不会之理。
学会编程是一件相当重要的事,我在清华上课时对学生说“这是你们的看家本事”。一个国家,一个民族,要想不落伍,要想跻身于世界民族之林,关键在于拥有高素质的人才。学习和掌握信息科学与技术,在高水准人才的知识结构中占有重要的地位。讲文化要以科学为基础,讲科学要提高到文化的高度。学习计算机必须了解这一学科的内在规律和特征,“构造性”和“能行性”是计算机学科的两个最根本特征。与构造性相应的构造思维,又称计算思维,指的是通过算法的“构造”和实现来解决一个给定问题的一种“能行”的思维方式。
有些问题没有固定的解法,给读者留有广阔的发挥创造力的空间,经过思考构造出的算法能不能高效地解决问题,都得通过上机实践的检验,在这一过程中思维能力和行动能力会同步提升。我认为高手应该是这样炼成的。光说不练,纸上谈兵是绝对学不会的。
当前,有识之士已经认识到:大学计算机作为基础课,与数学、物理同样重要。培养计算机的应用能力,掌握使用计算机的思路和方法,必须既动手又动脑,体会和感悟蕴含于其中的计算思维要素,对于现代人是非常重要的。
当你拿到这本书时,建议你先看“阅读说明”。其中有两点,一是“本书最好是有人带着学习”,如果这一点做不到的话,建议你求助于网络,开展合作学习,向高人请教,让心得共享,这些都符合现代学习理念;二是“一定要重视书中的提示”,因为其中包含着需要掌握的重要知识点和编程技巧,你会发觉有些内容在一般教科书中是看不到的。
这是一本学习竞赛入门的书。我想说的是参加信息学竞赛入门不难,深造也是做得到的,关键是专心、恒心与信心,世上无难事,只要肯攀登!
全国信息学奥林匹克(NOI)科学委员会名誉主席
国际信息学奥林匹克中国队总教练
清华大学计算机科学与技术系
吴文虎
媒体评论
《算法竞赛入门经典(第2版)》要面世了。一方面高兴,一方面也想借题发挥,这是因为近年来我和我的团队致力于研究计算机教育的改革,对于应该如何提升学生的思维能力和行动能力有了新的认识。当然我会把握“不要离题太远”。
在我的书案上常年摆着一本蓝皮的书《算法艺术与信息学竞赛》,这是刘汝佳与黄亮合写的书,2003年12月我怀着喜悦的心情给这本书写了一页纸的序言。今天,时隔十年,我又拿起笔来为汝佳的新书作序,想到信息学奥林匹克的魅力,看到我们的学生能够承担起普及的责任和水平,此时此刻我的欣喜之情难以言表。“青出于蓝更胜于蓝”是我们当老师的最大愿望和期盼。汝佳之所以能写出这种内容和内涵丰富,文字也很难表达的思维艺术之美的好书,在于他对于信息学竞赛的热爱和他在青少年中普及计算机知识的强烈的责任感。汝佳为人低调诚实,做事认真负责,最可贵之处是那种“打破砂锅问到底”的求真务实精神,还有就是愿意和善于与人合作共事,能够真心听取别人的意见。
刘汝佳在中学参加信息学奥赛,进入清华大学后作为主力队员参加过ACM/ICPC世界大学生程序设计大赛,在本科和读研期间又长期担任国际信息学奥林匹克中国队的教练。很早以前他就说过:想写一本“从入门开始就能陪伴着读者的书”,意思是书的作用不仅是答疑、解惑,更是像朋友和知己,同读者一起探讨和研究问题。我当然赞成著书者的境界,在我给本科生上“程序设计基础”课时的感悟是:教学相长,发挥学生在学习中的主体作用,激发兴趣和调动积极性,创造条件,使其参与课程内容的研讨,并提出宝贵意见,是成就精品课的必由之路。汝佳说:“书的第12章就像是一个路标,告诉你每条路通往怎样的风景,但是具体还得靠读者自己走过去,在走之前也需要自己选择。”话说得很到位。闪光的东西蕴含在解决问题时的那些思维之美中,精妙的解题思路和策略有时令人拍案叫绝,一路学一路体味赏心悦目的风景,没有不爱学和学不会之理。
学会编程是一件相当重要的事,我在清华上课时对学生说“这是你们的看家本事”。一个国家,一个民族,要想不落伍,要想跻身于世界民族之林,关键在于拥有高素质的人才。学习和掌握信息科学与技术,在高水准人才的知识结构中占有重要的地位。讲文化要以科学为基础,讲科学要提高到文化的高度。学习计算机必须了解这一学科的内在规律和特征,“构造性”和“能行性”是计算机学科的两个最根本特征。与构造性相应的构造思维,又称计算思维,指的是通过算法的“构造”和实现来解决一个给定问题的一种“能行”的思维方式。
有些问题没有固定的解法,给读者留有广阔的发挥创造力的空间,经过思考构造出的算法能不能高效地解决问题,都得通过上机实践的检验,在这一过程中思维能力和行动能力会同步提升。我认为高手应该是这样炼成的。光说不练,纸上谈兵是绝对学不会的。
当前,有识之士已经认识到:大学计算机作为基础课,与数学、物理同样重要。培养计算机的应用能力,掌握使用计算机的思路和方法,必须既动手又动脑,体会和感悟蕴含于其中的计算思维要素,对于现代人是非常重要的。
当你拿到这本书时,建议你先看“阅读说明”。其中有两点,一是“本书最好是有人带着学习”,如果这一点做不到的话,建议你求助于网络,开展合作学习,向高人请教,让心得共享,这些都符合现代学习理念;二是“一定要重视书中的提示”,因为其中包含着需要掌握的重要知识点和编程技巧,你会发觉有些内容在一般教科书中是看不到的。
这是一本学习竞赛入门的书。我想说的是参加信息学竞赛入门不难,深造也是做得到的,关键是专心、恒心与信心,世上无难事,只要肯攀登!
全国信息学奥林匹克(NOI)科学委员会名誉主席