算法竞赛入门经典（第2版）(txt+pdf+epub+mobi电子书下载)

作者：刘汝佳

出版社：清华大学出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

算法竞赛入门经典（第2版）试读：

前言

看来，是时候给本书“升级”了。

主要的变化

我原本打算只是增加一章专门介绍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）等诸多经典问题。

最后，需要特别指出的是，本书前11章中全部155道例题的代码都可以在代码仓库中下载：https://github.com/aoapc-book/aoapc-bac2nd/。书稿中因篇幅原因未能展开叙述的算法细节和编程技巧都可以在代码仓库中找到，请读者朋友们善加利用。

致谢

虽然多出来了200多页，其实本书的改版工作并没有花费太长时间（不到半年），在此期间也没有麻烦太多朋友读稿和讨论。参与本书第2版读稿和校对工作的几位朋友分别是：陈锋（第8～11章）、王玉斌（第8～9章，第12章）、郭云镝（第12章）、曹海宇（第5章、第9章）、陈立杰（第12章）、叶子卿（第12章）、周以凡（第12章）。

感谢给我发邮件以及在googlecode的wiki中留言指出本书第1版勘误的网友们：imxivid、zr95.vip、李智维、王玉、chnln0526、yszhou4tech、metowolf88、zhongying822、chong97993、tplee923、wtx20074587、chu.pang、code4101等，你们的支持和鼓励是我写作的重要动力。

另外，书中部分难题的题解离不开以下朋友的赐教和讨论：Md.Mahbubul Hasan、Shahriar Manzoor、Derek Kisman、Per Austrin、Luis Garcia、顾昱洲、陈立杰、张培超等。

第2版的习题全部（这次不仅仅是“主要”了）来自UVa在线评测系统，感谢Miguel Revilla教授、他的儿子Miguel Jr.和Carlos M. Casas Cuadrado对本书的大力支持。

最后，再次感谢清华大学出版社的朱英彪编辑在这个恰当的时机提出改版事宜，并容忍我把交稿时间一拖再拖。希望这次改版不会让你失望。刘汝佳前言“听说你最近在写一本关于算法竞赛入门的书？”朋友问我。“是的。”我微笑道。“这是怎样的一本书呢？”朋友很好奇。“C语言、算法和题解。”我回答。“什么？几样东西混着吗？”朋友很吃惊。“对。”我笑了，“这是我思考许久后做出的决定。”大学之前的我

12年前，当我翻开Sam A. Abolrous所著的《C语言三日通》的第一页时，我不会想到自己会有机会编写一本讲解C语言的书籍。当时，我真的只用了3天就学完了这本书，并且自信满满：“我学会C语言啦！我要用它写出各种有趣、有用的程序！”但渐渐地，我认识到了：虽然浅显易懂，但书中的内容只是C语言入门，离实际应用还有较大差距，就好比小学生学会造句以后还要下很大工夫才能写出像样的作文一样。

第二本对我影响很大的书是Sun公司Peter van der Linden（PvdL）所著的《C程序设计奥秘》。作者称该书应该是每一位程序员“在C语言方面的第二本书”，因为“书中绝大部分内容、技巧和技术在其他任何书中都找不到”。原先我只把自己当成是程序员，但在阅读的过程中，我开始渐渐了解到硬件设计者、编译程序开发者、操作系统编写者和标准制定者是怎么想的。继续的阅读增强了我的领悟：要学好C语言，绝非熟悉语法和语义这么简单。

后来，我自学了数据结构，懂得了编程处理数据的基本原则和方法，然后又学习了8086汇编语言，甚至曾没日没夜地用SoftICE调试《仙剑奇侠传》，并把学到的技巧运用到自己开发的游戏引擎中。再后来，我通过《电脑爱好者》杂志上一则不起眼的广告了解到全国信息学奥林匹克联赛（当时称为分区联赛，NOIP是后来的称谓）。“学了这么久的编程，要不参加个比赛试试？”想到这里，我拉着学校里另外一个自学编程的同学，找老师带我们参加了1997年的联赛——在这之前，学校并不知道有这个比赛。凭借自己的数学功底和对计算机的认识，我在初赛（笔试）中获得全市第二的成绩，进入了复赛（上机）。可我的上机编程比赛的结果是“惨烈”的：第一题有一个测试点超过了整数的表示范围；第二题看漏了一个条件，一分都没得；第三题使用了穷举法，全部超时。考完之后我原以为能得满分的，结果却只得了100分中的20多分，名落孙山。

痛定思痛，我开始反思这个比赛。一个偶然的机会，我拿到了一本联赛培训教材。书上说，比赛的核心是算法（Algorithm），并且推荐使用Pascal语言，因为它适合描述算法。我复制了一份Turbo Pascal 7.0（那时网络并不发达）并开始研究。由于先学的是C语言，所以我刚开始学习Pascal时感到很不习惯：赋值不是“=”而是“:=”，简洁的花括号变成了累赘的begin和end，if之后要加个then，而且和else之间不允许写分号……但很快我就发现，这些都不是本质问题。在编写竞赛题的程序时，我并不会用到太多的高级语法。Pascal的语法虽然稍微啰嗦一点，但总体来说是很清晰的。就这样，我只花了不到一天的时间就把语法习惯从C转到了Pascal，剩下的知识就是在不断编程中慢慢地学习和熟练——学习C语言的过程是痛苦的，但收益也是巨大的，“轻松转到Pascal”只是其中一个小小的例子。

我学习计算机，从一开始就不是为了参加竞赛，因此，在编写算法程序之余，我几乎总是使用熟悉的C语言，有时还会用点汇编，并没有觉得有何不妥。随着编写应用程序的经验逐渐丰富，我开始庆幸自己先学的是C语言——在我购买的各类技术书籍中，几乎全部使用的是C语言而不是Pascal语言，尽管偶尔有用Delphi的文章，但这种语言似乎除了构建漂亮的界面比较方便之外，并没有太多的“技术含量”。我始终保持着对C语言的熟悉，而事实证明这对我的职业生涯发挥了巨大的作用。中学竞赛和教学

在大学里参加完ACM/ICPC世界总决赛之后（当时ACM/ICPC还可以用Pascal，现在已经不能用了），我再也没有用Pascal语言做过一件“正经事”（只是偶尔用它给一些只懂Pascal的孩子讲课）。后来我才知道，国际信息学奥林匹克系列竞赛是为数不多的几个允许使用Pascal语言的比赛之一。IT公司举办的商业比赛往往只允许用C/C++或Java、C#、Python等该公司使用较为频繁的语言（顺便说一句，C语言学好以后，读者便有了坚实的基础去学习上述其他语言），而在做一些以算法为核心的项目时，一般来说也不能用Pascal语言——你的算法程序必须能和已有的系统集成，而这个“现有系统”很少是用Pascal写成的。为什么还有那么多中学生非要用这个“以后几乎再也用不着”的语言呢？

于是，我开始在中学竞赛中推广C语言。这并不是说我希望废除Pascal语言（事实上，我希望保留它），而是希望学生多一个选择，毕竟并不是每个参加信息学竞赛的学生都将走入IT界。但如果简单地因为“C语言难学难用，竞赛中还容易碰到诸多问题”就放弃学习C语言，我想是很遗憾的。

然而，推广的道路是曲折的。作为五大学科竞赛（数学、物理、化学、生物、信息学）中唯一一门高考中没有的“特殊竞赛”，学生、教师、家长所走的道路要比其他竞赛要艰辛得多。

第一，数理化竞赛中所学的知识，多是大学本科时期要学习的，只不过是提前灌输给高中生而已，但信息学竞赛中涉及的很多知识甚至连本科学生都不会学到，即使学到了，也只是“简单了解即可”，和“满足竞赛的要求”有着天壤之别，这极大地削减了中学生学习算法和编程的积极性。

第二，学科发展速度快。辅导信息学竞赛的教师常常有这样的感觉：必须不停地学习学习再学习，否则很容易跟不上“潮流”。事实上，学术上的研究成果常常在短短几年之内就体现在竞赛中。

第三，质量要求高。想法再伟大，如果无法在比赛时间之内把它变成实际可运行的程序，那么所有的心血都将白费。数学竞赛中有可能在比赛结束前15分钟找到突破口并在交卷前一瞬间把解法写完——就算有漏洞，还有部分分数呢；但在信息学竞赛中，想到正确解法却5个小时都写不完程序的现象并不罕见。连程序都写不完当然就是0分，即使程序写完了，如果存在关键漏洞，往往还是0分。这不难理解——如果用这个程序控制人造卫星发射，难道当卫星爆炸之后你还可以向人炫耀说：“除了有一个加号被我粗心写成减号从而引起爆炸之外，这个卫星的发射程序几乎是完美的。”

在这样的情况下，让学生和教师放弃自己熟悉的Pascal语言，转向既难学又容易出错的C语言确实是难为他们了，尤其是在C语言资料如此缺乏的情况下。等一下！C语言资料缺乏？难道市面上不是遍地都是C语言教材吗？对，C语言教材很多，但和算法竞赛相结合的书却几乎没有。不要以为语言入门以后就能轻易地写出算法程序（这甚至是很多IT工程师的误区），多数初学者都需要详细的代码才能透彻地理解算法，只了解算法原理和步骤是远远不够的。

大家都知道，编程需要大量的练习，只看和听是不够的。反过来，如果只是盲目练习，不看不听也是不明智的。本书的目标很明确——提供算法竞赛入门所必需的一切“看”的蓝本。有效的“听”要靠教师的辛勤劳动，而有效的“练”则要靠学生自己。当然，就算是最简单的“看”，也是大有学问的。不同的读者，往往能看到不同的深度。请把本书理解为“蓝本”。没有一本教材能不加修改就适用于各种年龄层次、不同学习习惯和悟性的学生，本书也不例外。我喜欢以人为本，因材施教，不推荐按照本书的内容和顺序填鸭式地教给学生。内容安排

前面花了大量篇幅讨论了语言，但语言毕竟只是算法竞赛的工具——尽管这个工具非常重要，却不是核心。正如前面所讲，算法竞赛的核心是算法。我曾考虑过把C语言和算法分开讲解，一本书讲语言，另一本书讲基础算法。但后来我发现，其实二者难以分开。

首先，语言部分的内容选择很难。如果把C语言的方方面面全部讲到，篇幅肯定不短，而且和市面上已有的C语言教材基本上不存在区别；如果只是提纲挈领地讲解核心语法，并只举一些最为初级的例子，看完后读者将会处于我当初3天看完《C语言三日通》后的状态——以为自己都懂了，慢慢才发现自己学的都是“玩具”，真正关键、实用的东西全都不懂。

其次，算法的实现常常要求程序员对语言熟练掌握，而算法书往往对程序实现避而不谈。即使少数书籍给出了详细代码，但代码往往十分冗长，不适合用在算法竞赛中。更重要的是，这些书籍对算法实现中的小技巧和常见错误少有涉及，所有的经验教训都需要读者自己从头积累。换句话说，传统的语言书和算法之间存在不小的鸿沟。

基于上述问题，本书采取一种语言和算法相结合的方法，把内容分为如下3部分：● 第1部分是语言篇（第1～4章），纯粹介绍语言，几乎不涉及算法，但逐步引入一些工程性的东西，如测试、断言、伪代码和迭代开发等。● 第2部分是算法篇（第5～8章），在介绍算法的同时继续强化语言，补充了第1部分没有涉及的语言特性，如位运算、动态内存管理等，并延续第一部分的风格，在需要时引入更多的思想和技巧。学习完前两部分的读者应当可以完成相当数量的练习题。● 第3部分是竞赛篇（第9～11章），涉及竞赛中常用的其他知识点和技巧。和前两部分相比，第3部分涉及的内容更加广泛，其中还包括一些难以理解的“学术内容”，但其实这些才是算法的精髓。

本书最后有一个附录，介绍开发环境和开发方法，虽然它们和语言、算法的关系都不大，却往往能极大地影响选手的成绩。另外，本书讲解过程中所涉及的程序源代码可登录网站http://www.tup.tsinghua.edu.cn/进行下载。致谢

在真正动笔之前，我邀请了一些对本书有兴趣的朋友一起探讨本书的框架和内容，并请他们撰写了一定数量的文字，他们是赖笠源（语言技巧、字符串）、曹正（数学）、邓凯宁（递归、状态空间搜索）、汪堃（数据结构基础）、王文一（算法设计）、胡昊（动态规划）。尽管这些文字本身并没有在最终的书稿中出现，但我从他们的努力中获得了很多启发。北京大学的杨斐瞳完成了本书中大部分插图的绘制，清华大学的杨锐和林芝恒对本书进行了文字校对、题目整理等工作，在此一并表示感谢。

在本书构思和初稿写作阶段，很多在一线教学的老师给我提出了有益的意见和建议，他们是绵阳南山中学的叶诗富老师、绵阳中学的曾贵胜老师、成都七中的张君亮老师、成都石室中学的文仲友老师、成都大弯中学的李植武老师、温州中学的舒春平老师，以及我的母校——重庆外国语学校的官兵老师等。

本书的习题主要来自UVa在线评测系统，感谢Miguel Revilla教授和Carlos M. Casas Cuadrado的大力支持。

最后，要特别感谢清华大学出版社的朱英彪编辑，与他的合作非常轻松、愉快。没有他的建议和鼓励，或许我无法鼓起勇气把“算法艺术与信息学竞赛”以丛书的全新面貌展现给读者。刘汝佳  第1部分语言篇第1章　程序设计入门

学习目标● 熟悉C语言程序的编译和运行● 学会编程计算并输出常见的算术表达式的结果● 掌握整数和浮点数的含义和输出方法● 掌握数学函数的使用方法● 初步了解变量的含义● 掌握整数和浮点数变量的声明方法● 掌握整数和浮点数变量的读入方法● 掌握变量交换的三变量法● 理解算法竞赛中的程序三步曲：输入、计算、输出● 记住算法竞赛的目标及其对程序的要求

计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字——步骤之间是有先后顺序的。这部分的重点在于计算。

接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。

注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。1.1　算术表达式

计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。程序1-1　计算并输出1+2的值#includeint main(){ printf("%d\n", 1+2); return 0;}

这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。如果不知道如何编译并运行这段程序，可阅读附录A或向指导教师求助。

即使读者不明白上述程序除了“1+2”之外的其他代码，仍然可以进行以下探索：试着把“1+2”改成其他内容，而不要修改那些并不明白的代码——它们看上去工作情况良好。

下面做4个实验。

实验1：修改程序1-1，输出3-4的结果。

实验2：修改程序1-1，输出5×6的结果。

实验3：修改程序1-1，输出8÷4的结果。

实验4：修改程序1-1，输出8÷5的结果。

直接把“1+2”替换成“3-4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。这样，4个实验都顺利完成了。

等一下！实验4的输出结果居然是1，而不是正确答案1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。

在C语言中，8/5的确切含义是8除以5所得商值的整数部分。同样地，（-8）/5的值是-1。那么，如果非要得到8÷5=1.6的结果怎么办？下面是完整的程序。程序1-2　计算并输出8/5的值，保留小数点后1位#includeint main(){ printf("%.1f\n", 8.0/5.0); return 0;}

注意：百分号后面是一个小数点，然后是数字1，最后是小写字母f，千万不能输入错，包括大小写——在C语言中，大写和小写字母代表的含义是不同的。

再来做3个实验。

实验5：把%.1f中的数字1改成2，结果如何？能猜想出“1”的确切意思吗？如果把小数点和1都删除，%f的含义是什么？

实验6：字符串%.1f不变，把8.0/5.0改成原来的8/5，结果如何？

实验7：字符串%.1f改成原来的%d，8.0/5.0不变，结果如何？

实验5并不难解决，但实验6和实验7的答案就很难简单解释了——真正原因涉及整数和浮点数编码，相信多数初学者对此都不感兴趣。原因并不重要，重要的是规范：根据规范做事情，则一切尽在掌握中。

提示1-1：整数值用%d输出，实数用%f输出。

这里的“整数值”指的是1+2、8/5这样“整数之间的运算”。只要运算符的两边都是整数，则运算结果也会是整数。正因为这样，8/5的值才是1，而不是1.6。

8.0和5.0被看作是“实数”，或者说得更专业一点，叫“浮点数”。浮点数之间的运算结果是浮点数，因此8.0/5.0=1.6也是浮点数。注意，这里的运算符“/”其实是“多面手”，它既可以做整数除(1)法，又可以做浮点数除法。

提示1-2：整数/整数=整数，浮点数/浮点数=浮点数。

这条规则同样适用于加法、减法和乘法，不过没有除法这么容易出错——毕竟整数乘以整数的结果本来就是整数。

算术表达式可以和数学表达式一样复杂，例如：程序1-3　复杂的表达式计算#include#includeint main(){ printf("%.8f\n", 1+2*sqrt(3)/(5-0.1)); return 0;}

相信读者不难把它翻译成数学表达式。尽管如此，读者可能还是有一些疑惑：5-0.1的值是什么？“整数-浮点数”是整数还是浮点数？另外，多出来的#include有什么作用？

第1个问题相信读者能够“猜到”结果：整数-浮点数=浮点数。但其实这个说法并不准确。确切的说法是：整数先“变”成浮点数，然后浮点数-浮点数=浮点数。

第2个问题的答案是：因为程序1-3中用到了数学函数sqrt。数学函数sqrt(x)的作用是计算x的算术平方根（若不信，可输出sqrt(9.0)的值试试）。一般来说，只要在程序中用到了数学函数，就需要在程序最开始处包含头文件math.h，并在编译时连接数学库。如果不知道如何编译并运行这段程序，可阅读本章末尾的内容。1.2　变量及其输入

1.1节的程序虽好，但有一个遗憾：计算的数据是事先确定的。为了计算1+2和2+3，下面不得不编写两个程序。可不可以让程序读取键盘输入，并根据输入内容计算结果呢？答案是肯定的。程序如下：程序1-4　a+b问题#includeint main(){ int a, b; scanf("%d%d", &a, &b); printf("%d\n", a+b); return 0;}

该程序比1.1节的复杂了许多。简单地说，第一条语句“int a, b”声明了两个整型（即整数类型）变量a和b，然后读取键盘输入，并放到a和b中。注意a和b前面的“&”符号——千万不要漏掉，不信可(2)以试试。

现在，你的程序已经读入了两个整数，可以在表达式中自由使用它们，就好比使用12、597这样的常数。这样，表达式a+b就不难理解了。

提示1-3：scanf中的占位符和变量的数据类型应一一对应，且每个变量前需要加“&”符号。

可以暂时把变量理解成“存放值的场所”，或者形象地认为每个变量都是一个盒子、瓶子或箱子。在C语言中，变量有自己的数据类型，例如，int型变量存放整数值，而double型变量存放浮点数值（专业的说法是“双精度”浮点数）。如果一定要把浮点数值存放在一个int型变量中，将会丢失部分信息——我们不推荐这样做。

下面来看一个复杂一点的例子。

例题1-1　圆柱体的表面积

输入底面半径r和高h，输出圆柱体的表面积，保留3位小数，格式见样例。

样例输入：

3.5 9

样例输出：

Area = 274.889【分析】

圆柱体的表面积由3部分组成：上底面积、下底面积和侧面积。由于上下底面积相等，完整的公式可以写成：表面积=底面积×2+侧面积。根据几何知识，底面积=πr2，侧面积=2πrh。不难写出完整程序：程序1-5　圆柱体的表面积#include#includeint main(){ const double pi = acos(-1.0); double r, h, s1, s2, s; scanf("%lf%lf", &r, &h); s1 = pi*r*r; s2 = 2*pi*r*h; s = s1*2.0 + s2; printf("Area = %.3f\n", s) return 0;}

这是本书中第一个完整的“竞赛题目”，因为和正规比赛一样，题目中包含着输入输出格式规定，还有样例数据。大多数的算法竞赛包含如下一些相同的“游戏规则”。

首先，选手程序的执行是自动完成的，没有人工干预。不要在用户输入之前打印提示信息（例如“Please input n:”），这不仅不会为程序赢得更高的“界面友好分”，反而会让程序丢掉大量的（甚至所有的）分数——这些提示信息会被当作输出数据的一部分。例如，刚才的程序如果加上了“友好提示”，输出信息将变成：Please input n:Area = 274.889

比标准答案多了整整一行！

其次，不要让程序“按任意键退出”（例如，调用system("pause")，或者添加一个多余的getchar()），因为不会有人来“按任意键”的。不少早期的C语言教材会建议在程序的最后添加这样一条语句来“观察输出结果”，但注意千万不要在算法竞赛中这样做。

提示1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。

在一般情况下，你的程序不能直接读取键盘和控制屏幕：不要在算法竞赛中使用getch()、getche()、gotoxy()和clrscr()函数（早期的教材中可能会介绍这些函数）。

提示1-5：在算法竞赛中不要使用头文件conio.h，包括getch()、clrscr()等函数。

最后，最容易忽略的是输出的格式：在很多情况下，输出格式是非常严格的，多一个或者少一个字符都是不可以的！

提示1-6：在算法竞赛中，每行输出均应以回车符结束，包括最后一行。除非特别说明，每行的行首不应有空格，但行末通常可以有多余空格。另外，输出的每两个数或者字符串之间应以单个空格隔开。

总结一下，算法竞赛的程序应当只做3件事情：读入数据、计算结果、打印输出。不要打印提示信息，不要在打印输出后“暂停程序”，更不要尝试画图、访问网络等与算法无关的任务。

回到刚才的程序，它多了几个新内容。首先是“const double pi = acos(-1.0);”。这里也声明了一个叫pi的“符号”，但是const关键字(3)表明它的值是不可以改变的——pi是一个真正的数学常数。

提示1-7：尽量用const关键字声明常数。

接下来是s1 = pi * r * r。这条语句应该如何理解呢？“s1等于pi*r*r”吗？并不是这样的。若把它换成“pi * r * r = s1”，编译器会给出错误信息：invalid value in assignment。如果这条语句真的是“二者相等”的意思，为何不允许反着写呢？

事实上，这条语句的学术说法是赋值（assignment），它不是一个描述，而是一个动作。其确切含义是：先把“等号”右边的值算出来，然后赋于左边的变量中。注意，变量是“喜新厌旧”的，即新的值将覆盖原来的值，一旦被赋了新的值，变量中原来的值就丢失了。

提示1-8：赋值是个动作，先计算右边的值，再赋给左边的变量，覆盖它原来的值。

最后是“Area = %.3f\n”，该语句的用法很容易被猜到：只有以“%”开头的部分才会被后面的值替换掉，其他部分原样输出。

提示1-9：printf的格式字符串中可以包含其他可打印符号，打印时原样输出。

这里还有一个非常容易忽略的细节：输入采用的是"%lf"而不是"%f"。关于这一点，本章的末尾会继续讨论，现在先跳过。1.3　顺序结构程序设计

例题1-2　三位数反转

输入一个三位数，分离出它的百位、十位和个位，反转后输出。

样例输入：

127

样例输出：

721【分析】

首先将三位数读入变量n，然后进行分离。百位等于n/100（注意这里取的是商的整数部分），十位等于n/10%10（这里的%是取余数操作），个位等于n%10。程序如下：程序1-6　三位数反转（1）#includeint main(){ int n; scanf("%d", &n); printf("%d%d%d\n", n%10, n/10%10, n/100); return 0;}

此题有一个没有说清楚的细节，即：如果个位是0，反转后应该输出吗？例如，输入是520，输出是025还是25？如果在算法竞赛中(4)遇到这样的问题，可向监考人员询问。但是在这里，两种情况的处理方法都应学会。

提示1-10：算法竞赛的题目应当是严密的，各种情况下的输出均应有严格规定。如果在比赛中发现题目有漏洞，应向相关人员询问，尽量不要自己随意假定。

上面的程序输出025，但要改成输出25似乎会比较麻烦——必须判断n%10是不是0，但目前还没有学到“根据不同情况执行不同指令”（分支结构程序设计是1.4节的主题）。

一个解决方法是在输出前把结果存储在变量m中。这样，直接用%d格式输出m，将输出25。要输出025也很容易，把输出格式变为%03d即可。程序1-7　三位数反转（2）#includeint main(){ int n, m; scanf("%d", &n); m = (n%10)*100 + (n/10%10)*10 + (n/100); printf("%03d\n", m); return 0;}

例题1-3　交换变量

输入两个整数a和b，交换二者的值，然后输出。

样例输入：

824 16

样例输出：

16 824【分析】

按照题目所说，先把输入存入变量a和b，然后交换。如何交换两个变量呢？最经典的方法是三变量法：程序1-8　变量交换（1）#includeint main(){ int a, b, t; scanf("%d%d", &a, &b); t = a; a = b; b = t; printf("%d %d\n", a, b); return 0;}

可以将这种方法形象地比喻成将一瓶酱油和一瓶醋借助一个空瓶子进行交换：先把酱油倒入空瓶，然后将醋倒进原来的酱油瓶中，最后把酱油从辅助的瓶子中倒入原来的醋瓶子里。这样的比喻虽然形象，但是初学者应当注意它和真正的变量交换的区别。

借助一个空瓶子的目的是：避免把醋直接倒入酱油瓶子——直接倒进去，二者混合以后，将很难分开。在C语言中，如果直接进行赋值a=b，则原来a的值（酱油）将会被新值（醋）覆盖，而不是混合在一起。

当酱油被倒入空瓶以后，原来的酱油瓶就变空了，这样才能装醋。但在C语言中，进行赋值t=a后，a的值不变，只是把值复制给了变量t而已，自身并不会变化。尽管a的值马上就会被改写，但是从原理上看，t=a的过程和"倒酱油"的过程有着本质区别。

提示1-11：赋值a=b之后，变量a原来的值被覆盖，而b的值不变。

另一个方法没有借助任何变量，但是较难理解：程序1-9　变量交换（2）#includeint main(){ int a, b; scanf("%d%d", &a, &b); a = a + b; b = a - b; a = a - b; printf("%d %d\n", a, b); return 0;}

这次就不太方便用倒酱油做比喻了：硬着头皮把醋倒在酱油瓶子里，然后分离出酱油倒回醋瓶子？比较理性的方法是手工模拟这段程序，看看每条语句执行后的情况。

在顺序结构程序中，程序一条一条依次执行。为了避免值和变量名混淆，假定用户输入的是a0和b0，因此scanf语句执行完后a=a0，b=b0。

执行完a=a+b后：a=a0+b0，b=b0。

执行完b=a-b后：a=a0+b0，b=a0。

执行完a=a-b后：a=b0，b=a0。

这样，就不难理解两个变量是如何交换的了。

提示1-12：可以通过手工模拟的方法理解程序的执行方式，重点在于记录每条语句执行之后各个变量的值。

这个方法看起来很好（少用一个变量），但实际上很少使用，因为它的适用范围很窄：只有定义了加减法的数据类型才能采用此方法(5)。事实上，笔者并不推荐读者采用这样的技巧实现变量交换：三变量法已经足够好，这个例子只是帮助读者提高程序阅读能力。

提示1-13：交换两个变量的三变量法适用范围广，推荐使用。

那么是不是说，三变量法是解决本题的最佳途径呢？答案是否定的。多数算法竞赛采用黑盒测试，即只考查程序解决问题的能力，而不关心采用了什么方法。对于本题而言，最合适的程序如下：程序1-10　变量交换（3）#includeint main(){ int a, b; scanf("%d%d", &a, &b); printf("%d %d\n", b, a); return 0;}

换句话说，我们的目标是解决问题，而不是为了写程序而写程序，同时应保持简单（Keep It Simple and Stupid，KISS），而不是自己创造条件去展示编程技巧。

提示1-14：算法竞赛是在比谁能更好地解决问题，而不是在比谁写的程序看上去更高级。1.4　分支结构程序设计

例题1-4　鸡兔同笼

已知鸡和兔的总数量为n，总腿数为m。输入n和m，依次输出鸡的数目和兔的数目。如果无解，则输出No answer。

样例输入：

14 32

样例输出：

12 2

样例输入：

10 16

样例输出：

No answer【分析】

设鸡有a只，兔有b只，则a＋b＝n，2a＋4b＝m，联立解得a＝（4n－m）/2，b＝n－a。在什么情况下此解“不算数”呢？首先，a和b都是整数；其次，a和b必须是非负的。可以通过下面的程序判断：程序1-11　鸡兔同笼#includeint main(){ int a, b, n, m; scanf("%d%d", &n, &m); a = (4*n-m)/2; b = n-a; if(m % 2 == 1 || a < 0 || b < 0) printf("No answer\n"); else printf("%d %d\n", a, b); return 0;}

上面的程序用到了if语句，其一般格式是：if(条件) 语句1;else 语句2;

注意语句1和语句2后面的分号，以及if后面的括号。“条件”是一个表达式，当该表达式的值为“真”时执行语句1，否则执行语句2。另外，“else语句2”是可以省略的。语句1和语句2前面的空行是为了让程序更加美观，并不是必需的，但强烈推荐读者使用。

提示1-15：if语句的基本格式为：if（条件）语句1；else语句2。

换句话说，“”是一个表达式，其字面意思是“m是奇数，或者a小于0，或者b小于0”。这句话可能正确，也可能错误。因此这个表达式的值可能为真，也可能为假，取决于m、a和b的具体数值。

这样的表达式称为逻辑表达式。和算术表达式类似，逻辑表达式也由运算符和值构成，例如“||”运算符称为“逻辑或”，a||b表示a为真，或者b为真。换句话说，a和b只要有一个为真，a||b就为真；如果a和b都为真，则a||b也为真。和其他语言不同的是，在C语言中单个整数也可以表示真假，其中0为假，其他值为真。

提示1-16：if语句的条件是一个逻辑表达式，它的值可能为真，也可能为假。单个整数值也可以表示真假，其中0为假，其他值为真。

细心的读者也许发现了，如果a为真，则无论b的值如何，a||b均为真。换句话说，一旦发现a为真，就不必计算b的值。C语言正是采取了这样的策略，称为短路（short-circuit）。也许读者会觉得，用短路的方法计算逻辑表达式的唯一优点是速度更快，但其实并不是这样，稍后将通过几个例子予以证实。

提示1-17：C语言中的逻辑运算符都是短路运算符。一旦能够确定整个表达式的值，就不再继续计算。

例题1-5　三整数排序

输入3个整数，从小到大排序后输出。

样例输入：

20 7 33

样例输出：

7 20 33【分析】

a、b、c这3个数一共只有6种可能的顺序：abc、acb、bac、bca、cab、cba，所以最简单的思路是使用6条if语句。程序1-12　三整数排序（1）（错误）#includeint main(){ int a, b, c; scanf("%d%d%d", &a, &b, &c); if(a < b && b < c)printf("%d %d %d\n", a, b, c); if(a < c && c < b)printf("%d %d %d\n", a, c, b); if(b < a && a < c)printf("%d %d %d\n", b, a, c); if(b < c && c < a)printf("%d %d %d\n", b, c, a); if(c < a && a < b)printf("%d %d %d\n", c, a, b); if(c < b && b < a)printf("%d %d %d\n", c, b, a); return 0;}

上述程序看上去没有错误，而且能通过题目中给出的样例，但可惜有缺陷：输入“111”将得不到任何输出！这个例子说明：即使通过了题目中给出的样例，程序仍然可能存在问题。

提示1-18：算法竞赛的目标是编程对任意输入均得到正确的结果，而不仅是样例数据。

将程序稍作修改：把所有的小于符号“＜”改成小于等于符号“＜＝”（在一个小于号后添加一个等号）。这下总可以了吧？很遗憾，还是不行。对于“111”，6种情况全部符合，程序一共输出了6次“111”。

一种解决方案是人为地让6种情况没有交叉：把所有的if改成else if。程序1-13　三整数排序（2）#includeint main(){ int a, b, c; scanf("%d%d%d", &a, &b, &c); if(a <= b && b <= c) printf("%d %d %d\n", a, b, c); else if(a <= c && c <= b) printf("%d %d %d\n", a, c, b); else if(b <= a && a <= c) printf("%d %d %d\n", b, a, c); else if(b <= c && c <= a) printf("%d %d %d\n", b, c, a); else if(c <= a && a <= b) printf("%d %d %d\n", c, a, b); else if(c <= b && b <= a) printf("%d %d %d\n", c, b, a); return 0;}

最后一条语句还可以简化成单独的else（想一想，为什么），不过，幸好程序正确了。

提示1-19：如果有多个并列、情况不交叉的条件需要一一处理，可以用else if语句。

另一种思路是把a、b、c这3个变量本身改成a≤b≤c的形式。首先检查a和b的值，如果a＞b，则交换a和b（利用前面讲过的三变量交换法）；接下来检查a和c，最后检查b和c，程序如下：程序1-14　三整数排序（3）

试读结束[说明：试读内容隐藏了图片]

下载完整电子书