ACM/ICPC是国际计算机协会(Association for Computing Machinery)组织的国际大学生程序设计竞赛(International Collegiate Programming Contest),这项每年一届的计算机学科竞赛始于1976年,是大学生智力与计算机解题能力的竞赛,是世界公认的、目前全球高校之间规模最大且最具影响力的国际顶级赛事。
由清华大学吴文虎、王建德编著的《世界大学生程序设计竞赛(ACM/ICPC)高级教程 第一册 程序设计中常用的计算思维方式》(以下简称《计算思维方式》)就是针对世界大学生程序设计竞赛(ACM/ICPC)而编写的参考书,该书面向参加ACM/ICPC的高等院校学生,也可作为程序设计爱好者的参考用书。同时,也向讲授程序设计及相关课程的教师推荐此书,建议认真一读。
1ACM/ICPC
ACM/ICPC是高等院校计算机教育成果的直接体现,是大学生展示水平与才华的大舞台,也是IT企业与世界顶尖计算机人才对话的最佳机会。因而,ACM/ICPC吸引了越来越多的高校参赛,使得参赛队伍的水平上升很快,赛题的难度也在不断提高。
每年度的ACM/ICPC赛事从当年9月份开始,先进行各大洲各地区的预选赛,从上千所高校的几千支队伍中挑选出几十支优胜队伍。让这些百里挑一的队伍在下一年春天参加总决赛,争夺金银铜奖和世界冠军的奖杯。参赛选手由三人组成,一队共用一台计算机。这项赛事与中学生的信息学奥林匹克竞赛既有联系又有较大区别,被称为大学生的信息学奥林匹克。以2008～2009年度的ACM/ICPC为例,这是第33届赛事,有1838所大学的7109支队伍参加分区赛。经过第一阶段的预选赛,共有100支队伍取得决赛资格,于2009年4月18日—22日在瑞典斯德哥尔摩举行全球总决赛。
参加ACM/ICPC的选手需要具备很强的数学建模功底、广博的算法知识、超强的编程能力以及团队的合作与协同能力。ACM/ICPC的胜负规则是:答对题目数量多者占优;在两个队解题数量相同的情况下,总用时最少者占优,因此解题速度非常关键。如果比赛一开始就能迅速找出竞赛中相对简单的题目并尽快加以解决,队伍的成绩排名就会占有优势,心理上的压力也会小些。相反,一开始就没有选好题,或者所写的程序总有这样或那样的错误,要花很多时间去调试排错,就会浪费宝贵的时间,处于下风。
在这种你追我赶的激烈赛场上,比的是谁做得又快又好。竞赛过程中第一个重要的环节是看题、审题和选题。一开始就选对题,一下子就切入主题是十分重要的。有时第一个环节遇到陷阱,“马失前蹄”,就会导致一筹莫展而步步落后。能否在第一环节占上优势取决于实践能力和洞察力,而实践能力与洞察力的提升需要实战,需要经验,需要学懂计算思维方式和解题策略。
参加ACM/ICPC活动,在与编程高手过招的过程中,可以把知识运用的综合性、灵活性和探索性发挥到极致,体验和感受数学思维与算法艺术之美,提升科学思维能力。
2“观察—联想—变换”思维方式
计算机解题的核心是算法设计,而算法设计需要具备良好的数学素养。数学具有运用抽象思维去把握实际的能力,应用数学知识去解决实际问题时的建模过程是一个突出主要因素的科学抽象过程。进行抽象和形式化需要学习和掌握常用的计算思维方式。
科学思维能力的提高是成就事业最重要的因素之一,本书作者希望能在这方面对读者起到帮助作用。
编程解题的一般思维方法或过程,可以概述为“观察—联想—变换”,即通过对问题的观察,认识和理解该问题;然后通过联想,寻找该问题同已有知识和经验之间的联系;最后通过变换,把该问题转化为另一个或几个易于解决的新问题,最终达到解决原问题的目的。
“观察”是人类认识客观事物的基本途径,就编程解题而言,“观察”是“联想”和“变换”的基础。一般地说,通过观察应当明确:求解的对象是什么;是枚举方案还是回答哪个存在性问题;已知的条件(包括隐含条件) 是什么;能否用递推公式、递归公式、约束规则或状态转移方程把问题的条件、结论和求解途径表示出来;问题所涉及的这些计算式子各有什么特点等。
“联想”是由某种对象而引出其他相关对象的思维形式。就编程解题而言,“联想”的目的在于为“变换”提供可能的方向或线索。一般地说,在“观察”的基础上,通过联想应当明确:以前是否解过这类试题;是否解答过与其类似而又稍有不同的试题;是否解答过与其有关的问题;能否利用解答这些问题时所使用的解题方法或所得到的结果;能否回忆出某个可能用得上的定理、公式或解题思路;为了能利用它,是否应当改变条件或结论的表现形式等。
“变换”是编程解题的基本手段。在“观察”和“联想”的基础上,有目的地对问题实施“变换”,把原问题转化为另一个或几个易于解决的新问题,这是编程解题成功的关键。为此,变换时,应当遵循如下三条基本的思考原则:熟悉化原则、简单化原则以及和谐化原则。
3程序设计的常用思维方式
为了使读者对“观察—联想—变换”的思维方法和过程有一个比较全面深入的了解,本书归纳了大赛程序设计中六种常用的思维方式,主要包括正确认识和处理整体与部分的关系、构造性思维、目标转化的思想、分类与分治思想、逆向思维、猜想与试验六个章节,旨在引导参赛学生学习并掌握编程解题的一般思维方法和过程,提高解题能力。
在“观察”上,提出了整体与部分的思想,包括:
(1) 整体实现的关键是准确地应用必要条件。
(2) 整体思考的一个重要角度是“守恒”,即寻找变化中的不变量。
(3) 提高整体实现效率的途径是“充分利用有效信息”和“压缩冗余信息”。
(4) 改善整体的性能状态的基础是处理好细节问题。
在“联想”上,提出了逆向思维和猜想与试验,分析了“执果索因型”的逆向思维和“由反及正型”的逆向思维;探讨了四种联想方式:相似联想、归纳联想、从数与形的结合上联想和“回到起点”重新联想。指出猜想是在深入分析问题的基础上,不懈探索、反复修正的过程。
在“变换”上,提出了构造性思维、目标转化思想、分类与分治思想。构造性思维包括建立模型的机理分析法和统计分析法;建模过程注意应用序关系;选择模型时必须权衡四个因素:“时间复杂度、空间复杂度、编程复杂度和思维复杂度”。目标转化思想包括缩小目标的“降维”思想和放大目标的“升维”思想;分类与分治思想包括应用于一般有序序列的“二分查找”;应用于退化了的有序序列的“二分枚举”;应用于无序序列的“二分搜索”;应用于多维情况的“多重二分”。
在实际编程解题时,“观察”、“联想”、“变换”等思想活动总是互相联系、互相影响、互相交织地进行着,形成了一个有机的整体。本书列举的六种思维方式是互相渗透的,章节划分主要是依据各种思维方式的主要特征进行分类,同时也是为了叙述的方便。当然这六种思维方式并没有、也不可能穷尽编程解题过程中的所有思维活动,它只不过是列举了常用的一些思维方式,为“观察—联想—变换”的思维活动勾勒出一个基本轮廓,为读者留下学习、探索和再创造的空间。
4本书的体例结构
本书介绍的内容丰富而深入,所采用的叙述结构大致如下:
思维方法1 (1～6)
知识点1
经典例题1
思路点拨
解题思路分析
算法1
算法分析
程序实例
算法2
……
经典例题2
……
小结
知识点2
……
思维方法2
……
书中选择了大量的经典例题,这些题目对于丰富程序设计课程教师的教学案例也很有帮助。所选取案例大都具有一定的趣味性,有助于提高读者的阅读和实践练习的兴趣,提高实践效果。因此,可以说,虽然本书的编写主要针对ACM/ICPC,但对于高等院校程序设计教学水平的提高,促进程序设计教学质量和教学改革发展具有积极的意义。
本书各个知识点的“小结”内容是很值得推荐阅读的部分,作者以精准的语言扼要地概括了本部分的知识内容,仔细阅读和认真思考,将起到事半功倍的效果。
5图书相关信息
书名:《世界大学生程序设计竞赛(ACM/ICPC) 高级教程(第一册) 程序设计中常用的计算思维方式》
作者:吴文虎王建德编著
ISBN:978-7-113-10134-3/ TP3344
页数:278
定价:42.0元
出版社:中国铁道出版社(计算机图书批销部)
北京市宣武区右安门西街8号
邮编:100054
责编:秦绪好
装帧:精装
出版年:2009-7
6主要内容(目录)
第1章正确认识和处理整体与部分的关系
1.1整体实现的关键是准确地应用必要条件
1.1.1选择有助于简化问题、变难为易的必要条件
1.1.2合成必要条件,从整体结构上优化
1.1.3必要条件与原有模型比较,更新算法
1.2整体思考的一个重要角度是“守恒”
1.2.1从具体问题中抽象出守恒量
1.2.2根据问题的本质构造守恒量
1.2.3在交互问题中构造变化中的不变量
1.3提高整体实现效率的基本途径是“充分利用有效信息”和“压缩冗余信息”
1.3.1计算过程中充分利用有效信息
1.3.2通过“压缩法”消除冗余的图形和数据信息
1.4改善整体性能状态的基础是处理好细节问题
1.4.1必须解决导致错误结果的细节问题
1.4.2争取降低算法时间复杂度的阶
1.4.3注意降低算法时间复杂度的系数
第2章构造性思维
2.1模型的基本概念
2.1.1模型的一般特点与功能
2.1.2模型的一般分类
2.1.3模型与信息原型间的关系
2.2建模的一般方法
2.2.1建模的机理分析方法
2.2.2建模的统计分析法
2.3建模的一般思维方式
2.3.1直接构造法
2.3.2分类构造法
2.3.3归纳构造法
2.4在建模过程中注意应用序关系
2.4.1在交互式问题中应用序
2.4.2利用典型的“序”关系简化问题
2.4.3寻找蕴涵在题意中的序关系
2.5模型选择
第3章目标转化的思想
3.1“降维”——缩小目标
3.1.1引入“降维思想”
3.1.2高维降为低维
3.1.3一般降为特殊
3.1.4抽象降为具体
3.1.5整体降为局部
3.1.6简化数据关系
3.2“升维”——放大目标
3.2.1让步假设
3.2.2倍增思想
第4章分类与分治思想
4.1应用于一般有序序列的二分法
4.1.1在给定的序列中“二分查找”
4.1.2在交互式问题中应用“二分插入”
4.2应用于退化了的有序序列的“二分枚举”
4.2.1用二分枚举求可行方案
4.2.2用二分枚举求最优性问题
4.3应用于无序序列的“二分搜索”
4.3.1在“二分搜索”的基础上构造可行解
4.3.2在“二分搜索”的基础上构造最优解
4.4应用于多维情况的“多重二分”
第5章逆向思维
5.1执果索因型逆向思维
5.1.1设置结果参数,逆向搜索
5.1.2从目标状态出发逆向规划
5.2由反及正型逆向思维
5.2.1割补法
5.2.2在统计问题中应用补集转化
第6章猜想与试验
6.1相似联想
6.1.1与熟悉的问题类比
6.1.2与特殊的问题类比
6.2归纳联想
6.2.1归纳联想的理论基础
6.2.2归纳联想的实际应用
6.3从数与形的结合上联想
6.3.1在数值计算中联想“以形助数”
6.3.2在几何计算中联想“以数助形”
6.4 “回到起点”重新联想
7推荐指数
推荐同行阅读指数:★★★★★ (注:以★★★★★为最高。)
这是ACM/ICPC高级教程的第一册,我们期待着后续教程的尽早面世。
8作者简介
吴文虎,1955-1961年分别就读于清华大学电机工程系及自动控制系。清华大学计算机系教授、博士生导师,原国际信息学奥林匹克中国队总教练。主要研究方向包括语音识别及语言理解、语音合成、语音信号数字处理等。
吴教授学术水平精湛、教学水平高超、教学经验丰富。从1989年至今,吴教授作为总教练和领队,曾15次带领中国队参加国际信息学奥林匹克竞赛,中国队累计获金牌51块,届届名列前茅,2002年获信息学奥林匹克国际委员会颁发的“特别贡献奖”。1997年～2008年,吴教授连续13年指导清华大学的学生进入ACM世界大学生程序设计大赛总决赛,多次获金、银牌,并于2009年被大赛组委会授予“杰出教练奖”。
参考文献:
[1] 吴文虎,王建德. 世界大学生程序设计竞赛(ACM/ICPC)高级教程(第一册)程序设计中常用的计算思维方式[M]. 北京:中国铁道出版社,2009-7.