算法艺术与信息学竞赛
点击看大图基本信息
编辑推荐
如果说信息科学与计算机技术为我们开辟了一片新的天地，程序设计是这片天地的灵魂居住的花园，那么程序设计竞赛则是点缀这个花园，使她充满灵气的塔宇。
计算机解题的核心是算法设计。算法设计涉及许多先修的基础知识，包括数据结构、高级语言程序设计、离散数学、图论、组合数学、人工智能、计算几何等。当然还包括除数学与信息学之外的其他学科知识，因为没有这些知识，往往连题目都会看不懂，这可能也是要求参加ACM大赛的选手应该具备全面科学素养的原因之一。 刘汝佳、黄亮两位作者都曾在高中时参加过信息学奥林匹克竞赛活动，他们在如何用计算机解难题方面投入过很大精力，有着比较丰富的经验。
推荐阅读
内容简介回到顶部↑
作译者回到顶部↑
本书提供作译者介绍
刘汝佳 1982年12月生。于2000年3月获得NOI2000全国青少年信息学奥林匹克竞赛一等奖第四名，进入国家集训队，并因此保送到清华大学计算机科学与技术系学习至今。2000年9月建立个人网站 "信息学初学者之家(OIBH)"，该网站现已成为国内最具影口向力的信息学竞赛网站之一。大一时参加ACH／ICPC国际大学生程序设计竞赛，获得2001年亚洲-上海赛区冠军和2002年世界总决赛银牌(世界第四)，并担任2002年和2003年北京赛区裁判。2003年12月为止共为全国青少年信息学竞赛(NOI)、IOI中国国家队.. << 查看详细
目录回到顶部↑
第1章 算法与数据结构
1.1 编程的灵魂--数据结构+算法=程序
1.2 基本算法
1.2.1 枚举
1.2.2 贪心法
1.2.3 递归与分治法
1.2.4 递推
1.3 数据结构（1）--入门
1.3.1 栈和队列
1.3.2 串
1.3.3 树和二叉树
1.3.4 力瘃其基本算法
1.3.5 排序与检索基本算法
1.4 数据结构（2）--拓宽和应用举例
1.4.1 并查集
1.4.2 堆及其变种
1.4.3 字典的两种实现方式：哈希表、二叉搜索树
1.4.4 两个特殊树结构：线段树和trie
1.5 动态规划
1.5.1 动态规划的两种动机
1.1 编程的灵魂--数据结构+算法=程序
1.2 基本算法
1.2.1 枚举
1.2.2 贪心法
1.2.3 递归与分治法
1.2.4 递推
1.3 数据结构（1）--入门
1.3.1 栈和队列
1.3.2 串
1.3.3 树和二叉树
1.3.4 力瘃其基本算法
1.3.5 排序与检索基本算法
1.4 数据结构（2）--拓宽和应用举例
1.4.1 并查集
1.4.2 堆及其变种
1.4.3 字典的两种实现方式：哈希表、二叉搜索树
1.4.4 两个特殊树结构：线段树和trie
1.5 动态规划
1.5.1 动态规划的两种动机
前言回到顶部↑
信息学(informatics)是一门新兴的学科，主要是指利用计算机及其程序设计来分析问题、解决问题的学问。随着计算机逐步深入生活，网络日趋普及，"信息革命"已经到来。信息学的地位逐步提高，青少年信息学竞赛也方兴未艾，在世界范围内受到了越来越多的重视。国际上，信息学竞赛主要分为两类：中学生的国际信息学奥林匹克和大学生的国际大学生程序设计竞赛。国际信息学奥林匹克(International Olympiad in Informatics，IOI)始于1989年，是联合国教科文组织倡导举行的五项国际学科奥林匹克之一。中国队每届都取得了名列前茅的佳绩，所有选手全部获奖，多次总分名列第一。国际大学生程序设计竞赛(ACM International Collegiate Programming Contest，ACM／ICPC)分为地区赛和国际总决赛，中国从1996年开始参加，现有3个地区赛赛点。清华大学、上海交通大学和中山大学等学校多次进入国际总决赛。上海交通大学队还获得了2002年的世界冠军的好成绩。从大局看，竞赛不是目的，而是推动普及的手段。虽然国内在培养信息学的优秀人才方面做了很大的努力，而且成绩斐然，但仍然存在一些遗憾之处：
第一，书籍资料的缺乏性。由于信息学竞赛的普及不如其他学科竞赛，辅导教师和研究人员相对匮乏，参与写作的人员也较少，致使国内此类书籍缺乏，而好书尤其缺乏。由此造成了不少信息学爱好者求书无门。另外，一些已出版的同类书籍或艰深难懂，或教条灌输，使不少爱好者望而却步，中途放弃，以至于信息学竟成了一种"曲高和寡"的学问。然而，社会信息化和信息学普及的大势已不可逆转，所以，信息学竞赛呼唤通俗易懂又有相当学术含量的好书。
第二，地区的不平衡性。由于信息学发展的时间毕竟不算长，很多地区在中学阶段刚刚开设或者还未开设信息学课程，师资力量相对比较薄弱。而且，信息学竞赛相对于其他学科，毕竟上手比较困难，这使得每年都有相当数目的信息学爱好者因为自学难度过大而中途放弃，从而导致国内信息学教学水平存在着很明显的地区不平衡性。很多地处信息学竞赛起步较晚地区的信息学爱好者们渴望能买到既实用又便于自学的书籍。
第三，国内视野的局限性。国内不少从事信息学竞赛研究的教育工作者把大部分精力放到了国内竞赛题目的研究中，而忽视了其他国家和地区的竞赛题目和研究成果。信息学竞赛题目的风格和内容往往受到本地传统文化等因素的影响，不同地区的题目往往有较大差异，因此熟悉各个国家的出题风格和特点，训练自己各方面的解题能力是很有必要的。所以，对于中高层选手和长期从事信息学竞赛辅导的老师来说，很需要紧跟国际动向、充分介绍国外成果的好书。
总之，从以上3点可以看出，国内信息学的普及度还远远不够。本书的出版，一方面是为了弥补国内信息学便于自学的普及读物方面的不足，拉近国内信息学竞赛起步较晚地区与发达地区的差距。另一方面是为了向国内读者介绍国外最新研究成果和竞赛试题，填补这方面的空白，拉近国内和国际最新发展的距离。
本书在理论方面参考了国外的最新研究成果的论文报告，在实际运用方面大量选用了在国内研究较少的外国竞赛的优秀题目，对信息学竞赛理论研究和实践都具有一定的参考价值，同时本书也是一本难得的资料集。
本书分为3章，第1章介绍算法与数据结构。算法与数据结构是信息学中最重要的部分之一，内容多而杂，不容易从整体上把握。本章的前三节介绍复杂度分析基本理论、基础算法和基础数据结构，重在给读者一定的感性认识，然后分三个专题介绍三个重要的问题：数据结构的应用、动态规划和搜索。第2章介绍信息学中用到的数学。数学是信息学的基础，因此本书专门用一章的篇幅加以详细论述。本章容量大，理论性比第1章强，涉及到基本代数方法、初等数论、组合数学和图论等问题。第3章介绍计算几何的基础知识、基本算法以及技巧。3．1节从最基本的位置和方向问题介绍叉积和点积；3．2节过渡到多边形、多面体及其容积、重心的求取以及形内形外的判断；3．3节讨论凸包这个最基本的几何模型及其应用；3．4节介绍了几个常用的特殊算法，包括分治法、离散化和扫描法，还介绍了增量和随机增量算法。
本书包含的内容非常多，各个层次、各种需求的读者都能在本书中找到适合自己的内容。本书丰富的内容能给读者以很大的选择余地，不同难度的例题和习题中既有引导读者兴趣的入门题目，又有极富挑战性的精彩题目，习题编号前的*越多，表示作者越推荐。
本书的第1章和第2章由刘汝佳编写，第3章由黄亮编写，在成书过程中还得到了很多老师和选手的大力支持。
在第3章的写作过程中，上海交通大学ACM代表队的不少队员和教练给了作者许多帮助。
要特别感谢陆靖；感谢远在美国的陈晓敏，他与作者进行了多次富有启发意义的讨论并提供了不少国内罕见的资料；感谢吕侣、陶云峰、杨寅、严琦琦、林晨曦、龚理、田斌、张羲等同学对本书写作的支持和与作者进行的讨论。
感谢世界著名计算几何学家Joseph O'Rourke博士对作者的启发。
在前两章的写作过程中，部分IOI2002和IOI2003中国国家集训队的成员提出了不少宝贵的意见，也提供了一些资料作为帮助，他们是王知昆、张一飞、李睿、何林、毛子青、骆骥、齐鑫、赵爽、金恺、李益明、符文杰、刘才良、张宁、黄芸。
感谢俞玮和林希德，他们与作者一起进行了大量的试题翻译工作，并讨论和撰写了题目分析。
感谢在讨论中启发作者思维并教会作者不少知识的外国朋友们：瑞典的Jimmy Mardell、加拿大的Derek Kisman、波兰的Tomasz Malesinski、乌克兰的Alexandar Gmshetsky、保加利亚的Petko Minkov。
感谢中国著名人像摄影家魏德运先生在本书的出版过程中所给予的帮助。
感谢北京师范大学ACM代表队的吴莹莹同学为本书的出版所给予的大力支持和帮助。
特别感谢在本书写作过程中对作者大力支持的各位老师!他们是：IOI中国队总教练吴文虎老师、ACM／ICPC清华大学代表队总教练王帆老师和邬晓钧老师、ACM／ICPC上海交通大学代表队总教练俞勇教授、ACM／ICPC德黑兰赛区总裁判Ramtin Khosravi先生、ACM／ICPC世界总决赛裁判Shahriar Manzoor先生和ACM／ICPC世界总决赛筹划指导委员会的Miguel Revilla先生。
作 者
2003年12月2日
第一，书籍资料的缺乏性。由于信息学竞赛的普及不如其他学科竞赛，辅导教师和研究人员相对匮乏，参与写作的人员也较少，致使国内此类书籍缺乏，而好书尤其缺乏。由此造成了不少信息学爱好者求书无门。另外，一些已出版的同类书籍或艰深难懂，或教条灌输，使不少爱好者望而却步，中途放弃，以至于信息学竟成了一种"曲高和寡"的学问。然而，社会信息化和信息学普及的大势已不可逆转，所以，信息学竞赛呼唤通俗易懂又有相当学术含量的好书。
第二，地区的不平衡性。由于信息学发展的时间毕竟不算长，很多地区在中学阶段刚刚开设或者还未开设信息学课程，师资力量相对比较薄弱。而且，信息学竞赛相对于其他学科，毕竟上手比较困难，这使得每年都有相当数目的信息学爱好者因为自学难度过大而中途放弃，从而导致国内信息学教学水平存在着很明显的地区不平衡性。很多地处信息学竞赛起步较晚地区的信息学爱好者们渴望能买到既实用又便于自学的书籍。
第三，国内视野的局限性。国内不少从事信息学竞赛研究的教育工作者把大部分精力放到了国内竞赛题目的研究中，而忽视了其他国家和地区的竞赛题目和研究成果。信息学竞赛题目的风格和内容往往受到本地传统文化等因素的影响，不同地区的题目往往有较大差异，因此熟悉各个国家的出题风格和特点，训练自己各方面的解题能力是很有必要的。所以，对于中高层选手和长期从事信息学竞赛辅导的老师来说，很需要紧跟国际动向、充分介绍国外成果的好书。
总之，从以上3点可以看出，国内信息学的普及度还远远不够。本书的出版，一方面是为了弥补国内信息学便于自学的普及读物方面的不足，拉近国内信息学竞赛起步较晚地区与发达地区的差距。另一方面是为了向国内读者介绍国外最新研究成果和竞赛试题，填补这方面的空白，拉近国内和国际最新发展的距离。
本书在理论方面参考了国外的最新研究成果的论文报告，在实际运用方面大量选用了在国内研究较少的外国竞赛的优秀题目，对信息学竞赛理论研究和实践都具有一定的参考价值，同时本书也是一本难得的资料集。
本书分为3章，第1章介绍算法与数据结构。算法与数据结构是信息学中最重要的部分之一，内容多而杂，不容易从整体上把握。本章的前三节介绍复杂度分析基本理论、基础算法和基础数据结构，重在给读者一定的感性认识，然后分三个专题介绍三个重要的问题：数据结构的应用、动态规划和搜索。第2章介绍信息学中用到的数学。数学是信息学的基础，因此本书专门用一章的篇幅加以详细论述。本章容量大，理论性比第1章强，涉及到基本代数方法、初等数论、组合数学和图论等问题。第3章介绍计算几何的基础知识、基本算法以及技巧。3．1节从最基本的位置和方向问题介绍叉积和点积；3．2节过渡到多边形、多面体及其容积、重心的求取以及形内形外的判断；3．3节讨论凸包这个最基本的几何模型及其应用；3．4节介绍了几个常用的特殊算法，包括分治法、离散化和扫描法，还介绍了增量和随机增量算法。
本书包含的内容非常多，各个层次、各种需求的读者都能在本书中找到适合自己的内容。本书丰富的内容能给读者以很大的选择余地，不同难度的例题和习题中既有引导读者兴趣的入门题目，又有极富挑战性的精彩题目，习题编号前的*越多，表示作者越推荐。
本书的第1章和第2章由刘汝佳编写，第3章由黄亮编写，在成书过程中还得到了很多老师和选手的大力支持。
在第3章的写作过程中，上海交通大学ACM代表队的不少队员和教练给了作者许多帮助。
要特别感谢陆靖；感谢远在美国的陈晓敏，他与作者进行了多次富有启发意义的讨论并提供了不少国内罕见的资料；感谢吕侣、陶云峰、杨寅、严琦琦、林晨曦、龚理、田斌、张羲等同学对本书写作的支持和与作者进行的讨论。
感谢世界著名计算几何学家Joseph O'Rourke博士对作者的启发。
在前两章的写作过程中，部分IOI2002和IOI2003中国国家集训队的成员提出了不少宝贵的意见，也提供了一些资料作为帮助，他们是王知昆、张一飞、李睿、何林、毛子青、骆骥、齐鑫、赵爽、金恺、李益明、符文杰、刘才良、张宁、黄芸。
感谢俞玮和林希德，他们与作者一起进行了大量的试题翻译工作，并讨论和撰写了题目分析。
感谢在讨论中启发作者思维并教会作者不少知识的外国朋友们：瑞典的Jimmy Mardell、加拿大的Derek Kisman、波兰的Tomasz Malesinski、乌克兰的Alexandar Gmshetsky、保加利亚的Petko Minkov。
感谢中国著名人像摄影家魏德运先生在本书的出版过程中所给予的帮助。
感谢北京师范大学ACM代表队的吴莹莹同学为本书的出版所给予的大力支持和帮助。
特别感谢在本书写作过程中对作者大力支持的各位老师!他们是：IOI中国队总教练吴文虎老师、ACM／ICPC清华大学代表队总教练王帆老师和邬晓钧老师、ACM／ICPC上海交通大学代表队总教练俞勇教授、ACM／ICPC德黑兰赛区总裁判Ramtin Khosravi先生、ACM／ICPC世界总决赛裁判Shahriar Manzoor先生和ACM／ICPC世界总决赛筹划指导委员会的Miguel Revilla先生。
作 者
2003年12月2日
序言回到顶部↑
计算机解题的核心是算法设计。算法设计涉及许多先修的基础知识，包括数据结构、高级语言程序设计、离散数学、图论、组合数学、人工智能、计算几何等。当然还包括除数学与信息学之外的其他学科知识，因为没有这些知识，往往连题目都会看不懂，这可能也是要求参加ACM大赛的选手应该具备全面科学素养的原因之一。
刘汝佳、黄亮两位作者都曾在高中时参加过信息学奥林匹克竞赛活动，他们在如何用计算机解难题方面投入过很大精力，有着比较丰富的经验。在上大学之后，又投入了大量精力帮助训练中国队的小选手和参加ACM世界大学生程序设计大赛。他们深感这些活动对提高学生的能力和全面素质所起的巨大作用。因此，他们利用课余时间，广泛收集各地各类试题，并着力研究、分析与归类，想出比较好的解法，特别是总结出若干的思路和经验写成书和大家共享。从他们开始动笔到成书期间又花了大量的心血，对一些难题的解法也有了独到的见解。这本书应该说是很难得的经验之谈。对一个编程高手来说，借鉴别人的经验是十分重要的。因此，我想将这本书推荐给参加IOI的中学生和参加ACM/ICPC的大学生阅读。
本书的命名也有独到之处。就我本人的教学经历来看，算法的确是艺术。艺术与科学本来就是孪生姊妹，不科学的东西谈不上艺术。艺术给人以美的感受，而算法属于数学文化范畴，数学的美在算法中得到了充分的体现，特别是当今数学已经进入新的机器时代，利用计算机求解问题，需要人充分开动脑筋，解决一系列难点，解题过程本身就是一个精益求精追求完美的过程。在这样一个过程中，编程者在付出艰辛的努力之后，会有一种获得成功的愉悦。正如一些数学大师所言：数学是理性的艺术，是创造性的艺术。在编程解题的过程中，通过理性的思维和理性的实践，你一定会感受到算法艺术的无穷魅力。一个颇具匠心的好算法会让你拍案叫绝，感受到它的思维艺术之美。我们许多参加过IOI和ACM／ICPC程序设计大赛的选手，当问起他们当年的拼搏是否艰苦时，他们都说苦中有乐，苦中有甜。这可能就是感受到了这种思维艺术的魅力。
科学思维能力的提高是成就事业最重要的一个因素，希望本书对你思维能力的提高能有很大的帮助。
清华大学计算机系教授，博士生导师
信息学奥林匹克中国队总教练
2003年12月
刘汝佳、黄亮两位作者都曾在高中时参加过信息学奥林匹克竞赛活动，他们在如何用计算机解难题方面投入过很大精力，有着比较丰富的经验。在上大学之后，又投入了大量精力帮助训练中国队的小选手和参加ACM世界大学生程序设计大赛。他们深感这些活动对提高学生的能力和全面素质所起的巨大作用。因此，他们利用课余时间，广泛收集各地各类试题，并着力研究、分析与归类，想出比较好的解法，特别是总结出若干的思路和经验写成书和大家共享。从他们开始动笔到成书期间又花了大量的心血，对一些难题的解法也有了独到的见解。这本书应该说是很难得的经验之谈。对一个编程高手来说，借鉴别人的经验是十分重要的。因此，我想将这本书推荐给参加IOI的中学生和参加ACM/ICPC的大学生阅读。
本书的命名也有独到之处。就我本人的教学经历来看，算法的确是艺术。艺术与科学本来就是孪生姊妹，不科学的东西谈不上艺术。艺术给人以美的感受，而算法属于数学文化范畴，数学的美在算法中得到了充分的体现，特别是当今数学已经进入新的机器时代，利用计算机求解问题，需要人充分开动脑筋，解决一系列难点，解题过程本身就是一个精益求精追求完美的过程。在这样一个过程中，编程者在付出艰辛的努力之后，会有一种获得成功的愉悦。正如一些数学大师所言：数学是理性的艺术，是创造性的艺术。在编程解题的过程中，通过理性的思维和理性的实践，你一定会感受到算法艺术的无穷魅力。一个颇具匠心的好算法会让你拍案叫绝，感受到它的思维艺术之美。我们许多参加过IOI和ACM／ICPC程序设计大赛的选手，当问起他们当年的拼搏是否艰苦时，他们都说苦中有乐，苦中有甜。这可能就是感受到了这种思维艺术的魅力。
科学思维能力的提高是成就事业最重要的一个因素，希望本书对你思维能力的提高能有很大的帮助。
清华大学计算机系教授，博士生导师
信息学奥林匹克中国队总教练
2003年12月
加载中...
