算法艺术与信息学竞赛（清晰版）

内容简介 本书较为系统和全面的介绍了算法学的最基本的知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容，也是国际青少年信息学奥林匹克（IOI）竞赛和ACM/ICPC国际大学生程序设计竞赛中所需要的。书中分析了相当数量的问题。 本书共3章。第1章介绍算法与数据结构，第2章介绍数学知识和方法，第3章介绍计算几何。全书内容丰富，分析透彻，启发性强，既适合读者自学，也适合于课堂讲授。 本书适合于各个层次的信息学爱好者、参赛选手、辅导老师和高等院校计算机专业师生。本书既是信息学入门和提高的好帮手，也是一本内容丰富，新颖的资料集。 本书序 计算机解题的核心是算法设计。算法设计涉及许多先修的基础知识，包括数据结构、高级语言程序设计、离散数学、图论、组合数学、 人工智能、计算几何等。当然还包括除数学与信息学之外的其他学科知识，因为没有这些知识，往往连题目都会看不懂，这可能也是要求参加ACM大赛选手应该具有全面科学素养的原因之一吧。 刘汝佳、黄亮两位作者都曾在高中时参加过信息学奥林匹克竞赛活动，他们在如何用计算机解难题方面投入过很大精力，有着比较丰富的经验。在上大学之后，又投入了精力帮助训练中国队的小选手和参加ACM世界大学生程序设计大赛。他们深感这些活动对提高学生的能力和全面素质所起的巨大作用。因此，他们利用课余时间，广泛收集各地各类试题，并着力研究、分析与归类，想出比较好的解法，特别是总结出若乾的思路和经验写成书和大家共享。从他们开始动笔到写成书中间又花了大量的心血，对一些难题的解法有独到的见解。这本书应该说是很难得的经验之谈，对一个编程高手来说借鉴别人的经验是十分重要的。因此，我想将这本书推荐给参加IOI的中学生和参加ACM/ICPC的大学生阅读。 本书的命名也有独到之处。就我本人的教学经历来看，算法的确是艺术。艺术与科学本来就是孪生姊妹。不科学的东西谈不上艺术。艺术给人以美的感受，算法属于数学文化范畴，数学的美在算法中得到充分体现，特别是当今数学已经进入了新的机器时代，利用计算机求解问题，需要人充分开动脑筋，解决一系列难点，解题过程本身就是一个精益求精追求完美的过程。在这样一个过程中编程者在付出艰辛的努力之后，会有一种获得成功的愉悦。正如一些数学大师所言：数学是理性的艺术，是创造性的艺术。在你编程解题的过程中，通过理性的思维和理性的实践，你一定会感受到算法艺术的无穷魅力。一个颇具匠心的好算法会让你拍案叫绝，感受到它的思维艺术之美。我们许多参加过IOI和ACM/ICPC程序设计大赛的选手，当问起他们当年的拼搏是否艰苦时，他们都说苦中有乐，苦中有甜，可能就是感受到了这种思维艺术的魅力。科学思维能力的提高是成就事业的最重要的一个因素。 清华大学计算机系教授、博士生导师 信息学奥林匹克中国队总教练 吴文虎 作者简介 刘汝佳 1982年12月生，毕业于重庆外国语学校。于2000年3月获NOI2000全国青少年信息学奥林匹克竞赛一等奖第4名，进入国家集训队，并因此保送到清华大学计算机科学与技术系学习至今。2000年9月建立个人网站“信息学初学者之家(OIBH)”，现已成为国内最具影响力的信息学竞赛网站之一。大一时参加ACM/ICPC国际大学生程序设计竞赛，获2001年亚洲—上海赛区冠军和2002年世界总决赛银牌（世界第四），并担任2002和2003年北京赛区裁判。2003年12月为止共为全国青少年信息学竞赛（NOI），IOI中国国家队选拔赛、冬令营、ACM/ICPC亚洲分区赛命题十余道，担任 IOI2002，2003和2004三届中国国家集训队教练，并在重庆、成都、长沙、北京、天津等地讲课多次，深受选手欢迎。于2002年底被中国计算机学会聘为全国青少年信息学竞赛科学委员会学生委员。 黄亮 自初中起跟随著名“金牌教练”王建德学习程序设计和算法。初三时代表上海代参加NOI’96全国青少年信息学奥林匹克竞赛，获三等奖（总第19名）。高三时取得信息学全国联赛一等奖和数学全国联赛三等奖。进入上海交大后，参加ACM/ICPC国际大学生程序设计竞赛，代表交大一队于2000年获上海赛区第四名。2002年获全国数学建模竞赛全国一等奖。本科期间在国际学术会议上发表论文3篇，参加了在台湾举行的计算语言学界最高会议COLING’02。其中在SIGHAN’02子会议上作的论文演讲获得了与会专家的一致好评和广泛关注。2003年本科毕业时被美国哥伦比亚大学、宾夕法尼亚大学和加拿大多伦多大学同时以全额奖学金录取。2003年秋起在宾夕法尼亚大学计算机与信息科学系攻读博士学位。 人工智能、计算几何等。当然还包括除数学与信息学之外的其他学科知识，因为没有这些知识，往往连题目都会看不懂，这可能也是要求参加ACM大赛选手应该具有全面科学素养的原因之一吧。 刘汝佳、黄亮两位作者都曾在高中时参加过信息学奥林匹克竞赛活动，他们在如何用计算机解难题方面投入过很大精力，有着比较丰富的经验。在上大学之后，又投入了精力帮助训练中国队的小选手和参加ACM世界大学生程序设计大赛。他们深感这些活动对提高学生的能力和全面素质所起的巨大作用。因此，他们利用课余时间，广泛收集各地各类试题，并着力研究、分析与归类，想出比较好的解法，特别是总结出若乾的思路和经验写成书和大家共享。从他们开始动笔到写成书中间又花了大量的心血，对一些难题的解法有独到的见解。这本书应该说是很难得的经验之谈，对一个编程高手来说借鉴别人的经验是十分重要的。因此，我想将这本书推荐给参加IOI的中学生和参加ACM/ICPC的大学生阅读。 本书的命名也有独到之处。就我本人的教学经历来看，算法的确是艺术。艺术与科学本来就是孪生姊妹。不科学的东西谈不上艺术。艺术给人以美的感受，算法属于数学文化范畴，数学的美在算法中得到充分体现，特别是当今数学已经进入了新的机器时代，利用计算机求解问题，需要人充分开动脑筋，解决一系列难点，解题过程本身就是一个精益求精追求完美的过程。在这样一个过程中编程者在付出艰辛的努力之后，会有一种获得成功的愉悦。正如一些数学大师所言：数学是理性的艺术，是创造性的艺术。在你编程解题的过程中，通过理性的思维和理性的实践，你一定会感受到算法艺术的无穷魅力。一个颇具匠心的好算法会让你拍案叫绝，感受到它的思维艺术之美。我们许多参加过IOI和ACM/ICPC程序设计大赛的选手，当问起他们当年的拼搏是否艰苦时，他们都说苦中有乐，苦中有甜，可能就是感受到了这种思维艺术的魅力。科学思维能力的提高是成就事业的最重要的一个因素。 清华大学计算机系教授、博士生导师 信息学奥林匹克中国队总教练 吴文虎 作者简介 刘汝佳 1982年12月生，毕业于重庆外国语学校。于2000年3月获NOI2000全国青少年信息学奥林匹克竞赛一等奖第4名，进入国家集训队，并因此保送到清华大学计算机科学与技术系学习至今。2000年9月建立个人网站“信息学初学者之家(OIBH)”，现已成为国内最具影响力的信息学竞赛网站之一。大一时参加ACM/ICPC国际大学生程序设计竞赛，获2001年亚洲—上海赛区冠军和2002年世界总决赛银牌（世界第四），并担任2002和2003年北京赛区裁判。2003年12月为止共为全国青少年信息学竞赛（NOI），IOI中国国家队选拔赛、冬令营、ACM/ICPC亚洲分区赛命题十余道，担任 IOI2002，2003和2004三届中国国家集训队教练，并在重庆、成都、长沙、北京、天津等地讲课多次，深受选手欢迎。于2002年底被中国计算机学会聘为全国青少年信息学竞赛科学委员会学生委员。 黄亮 自初中起跟随著名“金牌教练”王建德学习程序设计和算法。初三时代表上海代参加NOI’96全国青少年信息学奥林匹克竞赛，获三等奖（总第19名）。高三时取得信息学全国联赛一等奖和数学全国联赛三等奖。进入上海交大后，参加ACM/ICPC国际大学生程序设计竞赛，代表交大一队于2000年获上海赛区第四名。2002年获全国数学建模竞赛全国一等奖。本科期间在国际学术会议上发表论文3篇，参加了在台湾举行的计算语言学界最高会议COLING’02。其中在SIGHAN’02子会议上作的论文演讲获得了与会专家的一致好评和广泛关注。2003年本科毕业时被美国哥伦比亚大学、宾夕法尼亚大学和加拿大多伦多大学同时以全额奖学金录取。2003年秋起在宾夕法尼亚大学计算机与信息科学系攻读博士学位。