算法竞赛入门经典
点击看大图基本信息
- 作者： 刘汝佳
- 丛书名： 算法艺术与信息学竞赛
- 出版社：清华大学出版社
- ISBN：9787302206088
- 上架时间：2009-11-12
- 出版日期：2009 年11月
- 开本：16开
- 页码：225
- 版次：1-1
- 所属分类：
计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
编辑推荐
适合语言零基础的初学者.
涵盖算法竞赛的主要知识点
大量经验教训与比赛技巧..
简洁、清晰、高效的示例代码
丰富的辅助教学资源与配套习题...
推荐阅读
内容简介回到顶部↑
本书是一本算法竞赛的入门教材，把c/c++语言、算法和解题有机地结合在了一起，淡化理论，注重学习方法和实践技巧。全书内容分为11章，包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法，覆盖了算法竞赛入门所需的主要知识点，并附有大量习题。书中的代码规范、简洁、易懂，不仅能帮助读者理解算法原理，还能教会读者很多实用的编程技巧。另外，书中包含的各种开发、测试和调试技巧也是在传统的语言、算法类书籍中难以见到的。.
本书可作为全国青少年信息学奥林匹克联赛（noip）的复赛教材及acm国际大学生程序设计竞赛（acm/icpc）的入门参考，还可作为it工程师与科研人员的参考用书。...
本书可作为全国青少年信息学奥林匹克联赛（noip）的复赛教材及acm国际大学生程序设计竞赛（acm/icpc）的入门参考，还可作为it工程师与科研人员的参考用书。...
作译者回到顶部↑
目录回到顶部↑
第1部分 语 言 篇.
第1章 程序设计入门 1
1.1 算术表达式 1
1.2 变量及其输入 3
1.3 顺序结构程序设计 6
1.4 分支结构程序设计 9
1.5 小结与习题 13
1.5.1 数据类型实验 13
1.5.2 scanf输入格式实验 13
1.5.3 printf语句输出实验 13
1.5.4 测测你的实践能力 14
1.5.5 小结 14
1.5.6 上机练习 15
第2章 循环结构程序设计 16
2.1 for循环 16
2.2 循环结构程序设计 19
2.3 文件操作 23
2.4 小结与习题 27
2.4.1 输出技巧 28
2.4.2 浮点数陷阱 28
第1章 程序设计入门 1
1.1 算术表达式 1
1.2 变量及其输入 3
1.3 顺序结构程序设计 6
1.4 分支结构程序设计 9
1.5 小结与习题 13
1.5.1 数据类型实验 13
1.5.2 scanf输入格式实验 13
1.5.3 printf语句输出实验 13
1.5.4 测测你的实践能力 14
1.5.5 小结 14
1.5.6 上机练习 15
第2章 循环结构程序设计 16
2.1 for循环 16
2.2 循环结构程序设计 19
2.3 文件操作 23
2.4 小结与习题 27
2.4.1 输出技巧 28
2.4.2 浮点数陷阱 28
前言回到顶部↑
“听说你最近在写一本关于算法竞赛入门的书？”朋友问我。.
“是的。”我微笑道。
“这是怎样的一本书呢？”朋友很好奇。
“C语言、算法和题解。”我回答。
“什么？几样东西混着吗？”朋友很吃惊。
“对。”我笑了，“这是我思考许久后做出的决定。”
大学之前的我
12年前，当我翻开Sam A.Abolrous所著《C语言三日通》的第一页时，我不会想到自己会有机会编写一本讲解C语言的书籍。当时，我真的只花了3天就学完了这本书，并且自信满满：“我学会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语言、算法和题解。”我回答。
“什么？几样东西混着吗？”朋友很吃惊。
“对。”我笑了，“这是我思考许久后做出的决定。”
大学之前的我
12年前，当我翻开Sam A.Abolrous所著《C语言三日通》的第一页时，我不会想到自己会有机会编写一本讲解C语言的书籍。当时，我真的只花了3天就学完了这本书，并且自信满满：“我学会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工程师的误区），多数初学者都需要详细的代码才能透彻地理解算法，只了解算法原理和步骤是远远不够的。
)
加载中...
