计算机编程能给人带来很多特殊的快乐。 付出总会有回报，亲手做出一个有用的东西并看着它成功运转时，你为之满足； 灵光一现，于是轻松解决一个困扰你多年的问题时，你为之兴奋； 对美的执着追求能让一名普通黑客成为艺术家，而吝啬已然成为了一种美德， 尤其是从那些经过锤炼后的精巧算法和简洁代码中榨取最后一滴``性能之油''。 国际编程竞赛题目中的游戏、谜题和挑战是体验这些快乐的绝佳途径，同时还能提高你的算法能力和编程技巧。 %such as the %ACM International Collegiate Programming Contest %and the International Olympiad in Informatics 本书包含了百余个历届比赛中出现的题目，并讨论了解决这些题目所需的理论和思维方式。 读者可以在两个在线评测系统中提交其中任何一道题目的程序，并获得即时的自动评分。 若能将评测系统和本书有机结合，你会亲身体会到：迎接挑战和提升编程水平是一件多么新奇、刺激的事啊！ 本书可用于自学、讲授算法、编程类创新课程以及比赛的训练。 \subsection*{致读者} 本书中的题目选自Valladolid大学在线评测系统({\it http://uva.onlinejudge.org/})中的上千道编程题目。 \review{找找新数据噢} 到目前为止，该系统已经评测了来自27 000个注册用户的超过一百万份提交。 我们只选择了精品中的精品，即那些最好玩、最刺激和最有意思的题目。 我们把这些题目分成若干个类别，然后提供了足够的教学材料(主要是数学和算法)来帮助你解决它们。 书中配备了很多参考程序来更好地讲解重要的概念。阅读本书并尝试解决这些题目， 你会对回溯法、动态规划等算法技巧以及数论、计算几何等高级话题有更加具体和深刻的理解。 即使不参加编程竞赛，关注这些东西也是十分有益的。 %Beyond their educational value, these problems are suggestive of the %interview `puzzle' problems most advanced companies %give all new job applicants. %You can see them now, or you can see them later. %We annotate each problem as to difficulty, %and provide hints for certain problems in case you get stuck. %However, we encourage you to try each problem first before peeking at the hint. %Our goal is to help as many people as possible take advantage of this %unique educational resource. \review{fun和interesting的区别...} 多数题目都很生动。它们展示了计算机科学和数学中令人着迷的话题，有时还会以搞笑故事的面目出现。 它们往往涉及一些有意思的领域来深入学习研究，因此在合适的时候，我们总是给出注解和进一步的阅读材料。 %Although the problem statements are all available on line, they are %not organized by topics as in this book. Further, we find it much %easier to browse through a printed book than face international %transmission delays each time we want to turn the page. 我们发现，主要接受项目开发和软件工程方面训练的人们通常忽视了算法的重要性。 类似地，理论派算法研究者往往低估了把算法转化为程序的难度，也不清楚编程智慧如何化繁为简。 基于上述原因，本书的第一个部分主要关注编程技巧，包括数据类型和库函数的合理运用。 这些是书中第二部分那些以算法为主线， 难度更大章节的基础。要想成为一名全能的问题求解大师，必须同时精通这两个部分。 \subsection*{致教师} 本书被设计为以下三种类型的课程教材：\vspace{0.15mm} \begin{itemize} \item 偏重编程的算法课程。\vspace{0.15mm} \item 偏重算法的编程课程。\vspace{0.15mm} \item 训练学生参加 ACM/ICPC(ACM 国际大学生程序设计竞赛) 或 IOI(国际信息学奥林匹克)的选修课。\vspace{0.15mm} \end{itemize} 这样的课程对所有相关人士来说都是愉快的。\vspace{0.15mm} 学生的潜能很容易被比赛本身的刺激所激发，\vspace{0.15mm}并且每次提交通过一道题目时都将得到增强。 最直白的程序可能会被测试系统返回``超时''信息，\vspace{0.15mm}于是学生会很自然地寻找更有效的解法。 正确的洞察力会让一个十余行的小程序取代一大片杂乱无章的代码。\vspace{0.15mm}最优秀的学生甚至自愿尝试更多的题目来获得快感。 讲授这样的课程也是愉快的。很多题目十分精巧，\vspace{0.15mm}尽管在算法和编程本质上并无特殊之处，但题目却令人耳目一新。 对于这样的问题，要找到最佳解法需要洞察力和灵感。\vspace{0.15mm}寻找这些题目的解法是令人兴奋的， 而当我们所教的学生独立找到解法时，我们会更加兴奋。\vspace{0.15mm} 从教育学的角度讲，本书的特点包括：\vspace{0.15mm} \begin{itemize} %\newitem{New Motivations for Traditional Algorithmics} \item{\kaishu 作为标准算法教材的补充}------ 尽管本书体系完整，写作时仍然考虑到大多数学生已有了一些算法基础。\vspace{0.15mm} 本书是作为传统算法课程的补充教材来设计(与定价)的，\vspace{0.15mm}它用具体实现补充抽象描述， 用实践经验补充理论体系。另外，\vspace{0.15mm}它还涉及一些多数标准教材中都没有提到的有趣主题。\vspace{0.15mm} %(e.g., backtracking, number theory, and computational geometry) \item{\kaishu 提供经典算法的完整实现}------ 很多学生在把抽象的算法描述转化成能正确运行的代码时困难重重。\vspace{0.15mm} 为了帮助他们，我们精心编写了书中所讨论的所有重要算法的程序。\vspace{0.15mm}这些程序只用到~C~语言的一个子集， 因此~C++~和~Java~程序员也能轻易看懂。\vspace{0.15mm} 书中的不少习题都只需适当修改这些例程即可解决，\vspace{0.15mm}从而为初学者提供了一条宽敞的入门之路。\vspace{0.15mm} \item{\kaishu 内置课程管理系统}------ 我们已经打造了一个特别的课程管理系统，\vspace{0.15mm}使得管理一门这样的课程易如反掌。 所有测试和评分都是自动进行的，\vspace{0.15mm}你完全不必操心！ 用我们的网站 \oururl\ 可以轻松管理花名册、布置作业、查看学生的程序和分数，\vspace{0.15mm}甚至还能检测到疑似作业！ %However, our experience suggests that the competitive challenge of %such courses minimizes problematic behavior. \item{\kaishu 帮助程度参差不齐的学生}------ 本书在题目选择时有意覆盖了一个较宽的难度范围。\vspace{0.15mm}多数题目适合初学者，而其他题目即使对于备战国际竞赛的选手来说也是富有挑战的。 我们为多数题目提供了解题提示。\vspace{0.15mm} 为了帮助学生挑选适合自己的题目，我们给每道题目标注了三种类型的难度值。 题目的 {\em 流行度} (A, B, 或 C) 是指有多少人提交过此题，而{\em 成功率}(low~表示低，high~表示高)是指这些人中正确解决此题的比率。 最后，题目的{\em 等级} (从1 到 4，大致表示从新手到高水平读者)表示解题者应具有的水平等级。 \end{itemize} \swallow{ Have each student register at the online judge, and mail you their assigned ID number. Plugging this ID (say 8826) into the AuthorInfo file \url{http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:8826} gives you a link to the student's complete record. After building a web page with all these links, class performance can be monitored simply by clicking through the links. Sufficiently paranoid instructors may wish to collect solutions and run them through plagiarism detection programs such as Moss (see \url{http://www.cs.berkeley.edu/$\sim$aiken/moss.html}), since the judge isn't checking. However, our experience suggests the competitive challenge aspect of such courses minimizes such problems. } \secondedition{ \question{Can you set up a special course management WWW page for instructors to make it even easier for them (e.g. do cheat checking, impose calendar deadlines, and let the instructor view the student's solutions)? Let's talk about this.} } \subsection*{致竞赛选手与教练} 本书尤其适合作为高中和大学的编程竞赛培训材料。 我们为数学和算法中的重要主题提供方便的总结和参考，还配备了合适的挑战题目来帮助你掌握这些内容。 自动评测系统像ACM/ICPC中的真人裁判一样检查所提交程序的正确性。只要你拥有该系统的个人账号， 你就可以提交~C、C++、Pascal或Java~程序，然后等待系统告诉你这个程序是对还是错。 系统还会为你保存一份统计信息，让你有机会与成千上万的其他用户进行对比。 为了帮助竞赛选手，我们请到了三个重要编程比赛------ACM国际大学生程序设计竞赛(ICPC)、 国际信息学奥林匹克(IOI)、TopCoder编程挑战赛------的决赛选手分享经验，并把这些成功的秘密写在附录中。 我们还介绍了这三项赛事的历史和参赛方法，最大限度地帮助你施展才华。 \review{过期否} 大约有80\% 的~ACM/ICPC~决赛选手用~Valladolid~在线评测系统进行训练。 ICPC~全球总决赛常常在夏威夷这样令人神往的异国他乡举行，这无疑为选手们提供了额外的精神动力。加油吧！ \subsection*{相关网站} 本书有两个配套网站。书中的所有题目均可在 \oururl\,\linebreak 提交，该网站还提供了一些辅助材料， 包括书中所有程序的电子版以及帮助教师们把书中的材料融入课堂的课程笔记。 本书中的所有题目(以及很多其他题目)也可以在~Valladolid~大学在线评测系统 {\it http://}\linebreak{\it uva.onlinejudge.org/} 中提交。书中的所有习题均同时标注两个评测系统的ID号，供读者\linebreak 选择。 \subsection*{致谢} 本书的成书在很大程度上归功于那些欣然授权把他们设计的竞赛题目用在本书和在线评测系统中的人们。 本书中的题目由来自四大洲的至少17位命题者提供，尤其是Gordon Cormack和Shahriar Manzoor， 就好比Sam Loyd和H. E. Dudeney$^1$\footnotetext{\ \footnotesize\zihao{6}$^1$译者注：两位都以提出了大量有趣但富有挑战性的数学谜题而著称。}一样！ 作者和题目的完整列表见附录，但我们要在这里特别感谢如下的竞赛组织者： Gordon Cormack (38题), Shahriar Manzoor (28), Miguel Revilla (10), Pedro Demasi (8), Manuel Carro (4), Rujia Liu(刘汝佳) (4), Petko Minkov (4), Owen Astrakan (3), Alexander Denisjuk (3), Long Chong(龙翀) (2), Ralf Engels (2), Alex Gevak (1), Walter Guttmann (1), Arun Kishore (1), Erick Moreno (1), Udvranto Patik (1) 以及 Marcin Wojciechowski (1)。 其中的部分题目由第三方设计，我们已在附录中向他们致谢。 其中一些题目的原作者已经难以考证。我们想尽办法找到每道题目的原作者， 并得到了能代表作者发言的人授权。如有疏漏，在敬请原谅的同时还希望能告知我们，以便在致谢中补充。 在线评测系统项目是许多人辛勤劳动的结晶。 Ciriaco Garc\'\i a 是评测系统软件的主要开发人员，也是项目的核心支持人员。 \review{that help the judge in a friendly manner到底是?} Fernando P. N\'{a}jera 开发了一系列辅助工具，使得评测系统更加友好。 Carlos M. Casas 维护测试数据，确保它们在正确的前提下既公平又严格。 Jos\'e A. Caminero 和 Jes\'{u}s Pa\'{u}l 负责检查和完善题目描述，并测试参考程序。 我们还要特别感谢 Miguel Revilla, Jr，他建立并维护着\oururl。 %\todo{Acknowledge all robot judge people and anyone else you think appropriate.} 本书曾作为Stony Brook~2002年春季学期的一门课程的教材。 该课程由Vinhthuy Phan和Pavel Sumazin任教，并修改了诸多错误。 我们今年很棒的两支参赛队伍的成员(Larry Mak, Dan Ports, Tom Rothamel, Alexey Smirnov, Jeffrey Versoza和Charles Wright) 帮忙评阅了手稿，感谢他们的兴趣和反馈。 Haowen Zhang 仔细阅读了手稿，测试了书中的程序，并简化了代码，为本书的修改做出了重要贡献。 %\todo{Acknowledge all of the publisher's people.} 感谢Springer-Verlag的Wayne Yuhasz, Wayne Wheeler, Frank Ganz, Lesley Poliner 和 Rich Putter。没有他们的帮助，本书无法从手稿最终变成出版物。 我们还要感谢 Gordon Cormack, Lauren Cowles, David Gries, Joe O'Rourke, Saurabh Sethia, Tom Verhoeff, Daniel Wright 和 Stan Wagon。他们认真仔细的评阅极大地提高了最终成品的质量。 Fulbright Foundation 和 Valladolid大学应用数学与计算系为两位作者面对面交流和一起工作提供了必要的支持。 Citigroup CIB，通过 Peter Remch 和 Debby Z. Beckman 所做出的努力，为Stony Brook大学的 ACM ICPC产生了深远的影响。它的参与促成了本书的写作。

• 暂无课件
• 暂无样章
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接