算法竞赛入门经典

所需积分/C币:10 2013-06-21 16:40:35 22.01MB PDF
收藏 收藏
举报

算法竞赛入门经典。C或C++,数据结构的综合,很有指导意义
算法艺术与信息学竞赛 算法竞赛入门经典 刘汝佳编著 清华大学出版社 化京 内容简介 本书是一本算法竞赛的入门教材,把CC++语言、算法和解题有机地结合在了一起,淡化理论,注重 学习方法和实践技巧。全书内容分为11章,包括程序设计入门、循环结构程序设计、数组和字符串、函 数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、 图论模型与算法,覆盖了算法竞赛入门所需的主要知识点,并附有大量习题。书中的代码规范、简洁、易 懂,不仅能帮助读者理解算法原理,还能教会读者很多实用的编程技巧。另外,书中包含的各种开发、测 试和调试技巧也是在传统的语言、算法类书籍中难以见到的。 本书可作为全国青少年信息学奥林匹克联赛(NOIP)的复赛教材及ACM国际大学生程序设计竞赛 ( ACMAICPC)的入门参考,还可作为T工程师与科研人员的参考用书。 本书封面贴有清华大学出版杜防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:010-6278298913701121933 图书在版编目(c|P)数据 算法竞赛入门经典/闵刘汝佳编著.一北京:清华大学出版社,2009,1 算法艺术与信息学竞赛) ISBN978-730220608-8 L.算…Ⅱ.刘…Ⅲ①电子计算机-算法理论-教材②C语言-程序设计-教材IV.TP301.6TP312 中国版本图书馆CIP数据核字(2009)第118407号 责任编辑:朱英彪郭伟 封面设计;张岩 版式设计:王世情 责任校对:王云 责任印制:杨艳 出版发行:清华大学出版社 地址:北京清华大学学研大厦A座 hp:∥www.tup.com.cn 邮编:100084 社总机:010-62770175 邮购:010-62786544 投稿与读者服务:010-62776969,service@tup.tsinghua.edu.cn 质量反馈:010-62772015,zhiliang@tup.tsinghua.edu.cn 印刷者:清华大学印刷厂 装订者:三河市李旗庄少明装订「 经销:全国新华书店 开本:185×260印张:15字数:347千字 版次:2009年11月第1版 印次:2009年11月第1次印刷 印数:1~5000 定价:24.00元 木书如存在文字不清、漏印、缺页、倒页、脱页等印装质量问题,请与清华大学出版社出版部联系 调换。联系电话;(010)62770177转3103产品编号:03224201 前言 “听说你最近在写一本关于算法竞赛入门的书?”朋友问我 “是的。”我微笑道。 “这是怎样的一本书呢?”朋友很好奇。 “C语言、算法和题解。”我回答。 “什么?几样东西混着吗?”朋友很吃惊。 “对。”我笑了,“这是我思考许久后做出的决定。” 大学之前的我 12年前,当我翻开 Sam A. abolrous所著《C语言三日通》的第一页时,我不会想到自 己会有机会编写一本讲解C语言的书籍。当时,我真的只花了3天就学完了这本书,并且 自信满满:“我学会C语言啦!我要用它写出各种有趣、有用的程序!”但渐渐地,我认 识到了:虽然浅显易懂,但书中的内容只是语言入门,离实际应用还有较大差距,就好比 小学生学会造句以后还要下很大功夫才能写出像样的作文。 第二本对我影响很大的书是Sun公司的 Peter van der Linden(PvL)所著的《C程序设 计奥秘》。作者称该书应该是每一个程序员“在C语言方面的第二本书”,因为“书中绝 大部分内容、技巧和技术在其他任何书中都找不到”。原先我只是把自己当成是程序员, 但在阅读的过程中,我开始渐渐了解到硬件设计者、编译程序开发者、操作系统编写者和 标准制定者是怎么想的。继续的阅读增强了我的领悟:要学好C语言,绝非熟悉语法和语 义这么简单。 后来,我自学了数据结构,懂得了编程处理数据的基本原则和方法,然后又学习了8086 汇编语言,甚至曾没日没夜地用 SoftIce调试《仙剑奇侠传》,并把学到的技巧运用到自己 开发的游戏引擎中。再后来,我通过《电脑爱好者》杂志上的一则不起眼的广告了解到了 全国信息学奥林匹克联赛(当时称为分区联赛,NOP是后来的称谓)。“学了这么久编程, 要不参加个比赛试试?”想到这里,我拉着学校里另外一个自学编程的同学,找老师带我 们参加了1997年的联赛——在这之前,学校并不知道有这个比赛。凭借自己的数学功底和 对计算机的认识,我在初赛(笔试)中获得全市第二的成绩,进入了复赛(上机)。可我 的上机编程比赛的结果是“惨烈”的:第一题有一个测试点超过了整数的表示范围;第二 题看漏了一个条件,一分都没得;第三题使用了穷举法,全部超时。考完之后我原以为能 得满分的,结果却只得了100分中的20多分,名落孙山 痛定思痛,我开始反思这个比赛。一个偶然的机会,我拿到了一本联赛培训教材。书 上说,比赛的核心是算法( algorithm),并且推荐使用 Pascal语言,因为它适合描述算法。 我从别人那里复制来了 Turbo Pascal7.0(那时网络并不发达),开始研究起来。由于先学 算法竞赛入门经典 的是C语言,所以我刚开始学习 Pascal时感到有些不习惯:赋值不是“=”而是“:=”,简 洁的花括号变成了累赘的 begin和end,if之后要加个then,而且和else之间不允许写分 号 但很快我就发现,这些都不是本质问题。在编写竞赛题的程序时,我并不会用到太 多的高级语法。 Pascal的语法虽然稍微啰嗦一点,但总体来说是很清晰的。就这样,我只花 了不到一天时间就把语法习惯从C转到了 Pascal,剩下的知识就是在不断编程中慢慢地学 习和熟练——学习c语言的过程是痛苦的,但收益也是巨大的,“轻松转到 Pascal”只是 其中一个小小的例子。 我学习计算机,从一开始就不是为了参加竞赛,因此,在编写算法程序之余,我几乎 总是使用熟悉的C语言,有时还会用点汇编,并没有觉得有何不妥。随着编写应用程序的 经验逐渐丰富,我开始庆幸自己先学的是C语言——在我购买的各类技术书籍中,几乎全 部使用的是C语言而不是 Pascal语言,尽管偶尔有用 Delphi的文章,但这种语言似乎除了 构建漂亮的界面比较方便之外,并没有太多的“技术含量”。我始终保持着对C语言的熟 悉,而事实证明这对我的职业生涯发挥了巨大的作用。 中学竞赛和教学 在大学里参加完 ACM/ICPC世界总决赛之后(当时 ACMICPC还可以用 Pascal,现在 已经不能用了),我再也没有用 Pasca语言做过一件“正经事”(只是偶尔用它给一些只 懂 Pascal的孩子讲课)。后来我才知道,国际信息学奥林匹克系列竞赛是为数不多的几个 允许使用Pasa语言的比赛之一。IT公司举办的商业比赛往往只允许用CC++或Java、C# Python等该公司使用较为频繁的语言(顺便说一句,C语言学好以后,读者便有了坚实的 基础去学习上述其他语言),而在做一些以算法为核心的项目时,一般来说也不能用 Pascal 语言——你的算法程序必须和已有的系统集成,而这个“现有系统”很少是用 Pascal写成 的。为什么还有那么多中学生非要用这个“以后几乎再也用不着”的语言呢? 于是,我开始在中学竞赛中推广C语言。这并不是说我希望废除 Pascal语言(事实上, 我希望保留它),而是希望学生多一个选择,毕竟并不是每个参加信息学竞赛的学生都将 走入I界。但如果简单地因为“C语言难学难用,竞赛中还容易碰到诸多问题”就放弃学 习C语言,我想是很遗憾的。 然而,推广的道路是曲折的。作为五大学科竞赛(数学、物理、化学、生物、信息学) 中唯一一门高考中没有的“特殊竞赛”,学生、教师、家长所走的道路要比其他竞赛要艰 辛得多。 第一,数理化竞赛中所学的知识,多是大学本科要学习的,只不过是提前灌输给高中 生,但信息学竞赛中所涉及的很多东西甚至连本科都不会学到,即使学到了,也只是“简 单了解即可”,和“满足竞赛的要求”有着天壤之别,这极大地增加了中学生学习算法和 编程的难度。 第二,学科发展速度快。辅导信息学竞赛的教师常常有这样的感觉:必须不停地学习 学习再学习,否则很容易跟不上“潮流”。事实上,学术上的研究成果常常在短短几年之 内就体现在竞赛中。 前言偷 第三,质量要求高。想法再伟大,如果无法在比赛时间之内把它变成实际可运行的程 序,那么所有的心血都将是白费。数学竞赛中有可能在比赛结束前15分钟找到突破口并在 交卷前一瞬间把解法写完——就算有漏洞,还有部分分数呢;但在信息学竞赛中,想到正 确解法却5个小时都写不完程序的现象并不罕见。连程序都写不完当然就是0分,即使程 序写完了,如果存在关键漏洞,往往还是0分。这不难理解——如果用这个程序控制人造 卫星发射,难道当卫星爆炸之后你还可以向人炫耀说:“除了有一个加号被我粗心写成减 号从而引起爆炸之外,这个卫星的发射程序几乎是完美的。” 在这样的情况下,让学生和教师放弃自己熟悉的 Pascal语言,转向既难学又容易出错 的C语言确实难为他们了—一尤其是在C语言资料如此缺乏的情况下。等一下!C语言资 料缺乏?难道市面上不是遍地都是C语言教材吗?对,C语言教材多,但和算法竞赛相结 合的却几乎没有。不要以为语言入门以后就能轻易地写出算法程序(这甚至是很多T工程 师的误区),多数初学者都需要详细的代码才能透彻地理解算法,只了解算法原理和步骤 是远远不够的。 大家都知道,编程需要大量的练习,只看只听是不够的。反过来,如果只是盲目练习, 不看不听也是不明智的。本书的目标很明确——提供算法竞赛入门所必需的一切“看”的 蓝本。有效的“听”要靠教师的辛勤劳动,而有效的“练”则要靠学生自己。当然,就算 是最简单的“看”,也是大有学问的。不同的读者,往往能看到不同的深度。请把本书理 解为“蓝本”。没有一本教材能不加修改而适用于各种年龄层次、不同学习习惯和悟性的 学生,本书也不例外。我喜欢以人为本,因材施教,不推荐按照本书的内容和顺序填鸭式 地教给学生。 内容安排 前面花了大量篇幅讨论了语言,但语言毕竟只是算法竞赛的工具—尽管这个工具非 常重要,却不是核心。正如前面所讲,算法竞赛的核心是算法。我曾考虑过把C语言和算 法分开讲解,一本书讲语言,另一本书讲基础算法。但后来我发现,其实二者难以分开。 首先,语言部分的内容选择很难。如果把C语言的方方面面全部讲到,篇幅肯定不短, 而且和市面上已有的C语言教材基本上不存在区别;如果只是提纲挈领地讲解核心语法, 并只举一些最为初级的例子,看完后读者将会处于我当初3天看完《C语言三日通》后的状 态——以为自己都懂了,慢慢才发现自己学的都是“玩具”,真正关键、实用的东西全都 不懂。 其次,算法的实现常常要求程序员对语言熟练掌握,而算法书往往对程序实现避而不 谈。即使少数书籍给出了详细代码,但代码往往十分冗长,不适合用在算法竞赛中。更重 要的是,这些书籍对算法实现中的小技巧和常见错误少有涉及,所有的经验教训都需要读 者自己从头积累。换句话说,传统的语言书和算法之间存在着不小的鸿沟。 基于上述问题,本书采取一种语言和算法结合的方法,把内容分为如下3部分: 第1部分是语言篇(第1~4章),纯粹介绍语言,几乎不涉及算法,但逐步引入 一些工程性的东西,如测试、断言、伪代码和迭代开发等 算法竞赛入门经典 日第2部分是算法篇(第5~8章),在介绍算法的同时继续强化语言,补充了第1 部分没有涉及的语言特性,如位运算、动态内存管理等,并延续第一部分的风格, 在需要时引入更多的思想和技巧。学习完前两部分的读者应当可以完成相当数量 的练习题。 口第3部分是竞赛篇(第9~1章),涉及竞赛中常用的其他知识点和技巧。和前两 部分相比,第3部分涉及的内容更加广泛,其中还包括一些难以理解的“学术内 容”,但其实这些才是算法的精髓。 本书最后有一个附录,介绍开发环境和开发方法,虽然它们和语言、算法的关系都不 大,却往往能极大地影响选手的成绩。另外,本书讲解过程中所涉及的程序源代码可登录 网站htp:/www.tup.tsinghua.edu.cn/下载。 致谢 在真正动笔之前,我邀请了一些对本书有兴趣的朋友一起探讨本书的框架和内容,并 请他们撰写了一定数量的文字,他们是赖笠源(语言技巧、字符串)、曹正(数学)、邓 凯宁(递归、状态空间搜索)、汪堃(数据结构基础)、王文一(算法设计)、胡昊(动 态规划)。尽管这些文字本身并没有在最终的书稿中出现,但我从他们的努力中获得了很 多启发。北京大学的杨斐瞳完成了本书中大部分插图的绘制,清华大学的杨锐和林芝恒对 本书进行了文字校对、题目整理等工作,在此一并感谢。 在本书构思和初稿写作阶段,很多在一线教学的老师给我提出了有益的意见和建议, 他们是绵阳南山中学的叶诗富老师、绵阳中学的曾贵胜老师、成都七中的张君亮老师、成 都石室中学的文仲友老师、成都大弯中学的李植武老师、温州中学的舒春平老师,以及我 的母校——重庆外国语学校的官兵老师等。 本书的习题主要来自UVa在线评测系统,感谢 Miguel Revilla教授和 Carlos M. Casas Cuadrado的大力支持。 最后,要特别感谢清华大学出版社的朱英彪编辑,与他的合作非常轻松、愉快。没有 他的建议和鼓励,或许我无法鼓起勇气把“算法艺术与信息学竞赛系列”以丛书的全新面 貌展现给读者。 刘汝佳 目录 第1部分语言篇 第1章程序设计入门 ,、.,,,,,,,,,.,,,,、.,,.,,,、,,,,9,,,,,,,,,,,, 1.1算术表达式 1.2变量及其输入…… 13顺序结构程序设计 11369 14分支结构程序设计 1.5小结与习题……13 151数据类型实验 13 152 scanf输入格式实验….13 153prin语句输出实验,, 13 154测测你的实践能力… 1.55小结 144 15.6上机练习 15 第2章循环结构程序设计……16 2.1for循环 16 22循环结构程序设计… 19 23文件操作 24小结与习题 27 241输出技巧 28 24.2浮点数陷阱 28 24364位整数…18 244C++中的输入输出. ,B,,B,,,,,书,,,,,,,, 29 24.5小结.…30 24.6上机练习 第3章数组和字符串 33 31数组 33 32字符数组… 37 33最长回文子串 …………………………………………………"………………≮ 34小结与习题…145 341必要的存储量….5 34.2用ASCⅡ编码表示字符 45 算法竞赛入门经典 343补码表示法 …46 344重新实现库函数…47 34.5字符串处理的常见问题…47 346关于输入输出…...47 347O的效率 47 348小结… 49 349上机练习…50 第4章函数和递归 51 4.1数学函数 51 4.1.1简单函数的编写 4.12使用结构体的函数 4.1.3应用举例 53 42地址和指针 421变量交换.…156 4.22调用栈 57 4.23用指针实现变量交换.19 424初学者易犯的错误 61 4.3递归….162 4.3.1递归定义 62 43.2递归函数.63 433C语言对递归的支持. 43.4段错误与栈溢出 66 44本章小结…… 67 44.1小问题集锦. 442小结. 第己部分算法篇 第5章基础题目选解…… 69 ,,,,、,,,,,,,.,、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, 51字符串 5.1.1 WERTYU 69 512TeX括号… 513周期串 71 52高精度运算…… 71 521小学生算术.172 522阶乘的精确值. 112 523高精度运算类bgn 73 524重载bign的常用运算符.... 75 ⅥI·

...展开详情
试读 127P 算法竞赛入门经典
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    算法竞赛入门经典 10积分/C币 立即下载
    1/127
    算法竞赛入门经典第1页
    算法竞赛入门经典第2页
    算法竞赛入门经典第3页
    算法竞赛入门经典第4页
    算法竞赛入门经典第5页
    算法竞赛入门经典第6页
    算法竞赛入门经典第7页
    算法竞赛入门经典第8页
    算法竞赛入门经典第9页
    算法竞赛入门经典第10页
    算法竞赛入门经典第11页
    算法竞赛入门经典第12页
    算法竞赛入门经典第13页
    算法竞赛入门经典第14页
    算法竞赛入门经典第15页
    算法竞赛入门经典第16页
    算法竞赛入门经典第17页
    算法竞赛入门经典第18页
    算法竞赛入门经典第19页
    算法竞赛入门经典第20页

    试读已结束,剩余107页未读...

    10积分/C币 立即下载 >