资源描述：
《感受数学思维与算法艺术之美》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、感受数学思维与算法艺术之美ACM/ICPC是国际计算机协会(AssociationforComputingMachinery)组织的国际大学生程序设计竞赛(InternationalCollegiateProgrammingContest),这项每年一届的计算机学科竞赛始于1976年,是大学生智力与计算机解题能力的竞赛,是世界公认的、目前全球高校之间规模最大且最具影响力的国际顶级赛事。
由清华大学吴文虎、王建德编著的《世界大学生程序设计竞赛(ACM/ICPC)高级教程第一册程序设计中常用的计算思维方式》(以下简称《计算思
2、维方式》)就是针对世界大学生程序设计竞赛(ACM/ICPC)而编写的参考书,该书面向参加ACM/ICPC的高等院校学生,也可作为程序设计爱好者的参考用书。同时,也向讲授程序设计及相关课程的教师推荐此书,建议认真一读。
1ACM/ICPC
ACM/ICPC是高等院校计算机教育成果的直接体现,是大学生展示水平与才华的大舞台,也是IT企业与世界顶尖计算机人才对话的最佳机会。因而,ACM/ICPC吸引了越来越多的高校参赛,使得参赛队伍的水平上升很快,赛题的难度也在不断提高。
每年度的ACM/ICPC赛事从当年
3、9月份开始,先进行各大洲各地区的预选赛,从上千所高校的几千支队伍中挑选出几十支优胜队伍。让这些百里挑一的队伍在下一年春天参加总决赛,争夺金银铜奖和世界冠军的奖杯。参赛选手由三人组成,一队共用一台计算机。这项赛事与中学生的信息学奥林匹克竞赛既有联系又有较大区别,被称为大学生的信息学奥林匹克。以2008～2009年度的ACM/ICPC为例,这是第33届赛事,有1838所大学的7109支队伍参加分区赛。经过第一阶段的预选赛,共有100支队伍取得决赛资格,于2009年4月18日—22日在瑞典斯德哥尔摩举行全球总决赛。
参加ACM
4、/ICPC的选手需要具备很强的数学建模功底、广博的算法知识、超强的编程能力以及团队的合作与协同能力。ACM/ICPC的胜负规则是:答对题目数量多者占优;在两个队解题数量相同的情况下,总用时最少者占优,因此解题速度非常关键。如果比赛一开始就能迅速找出竞赛中相对简单的题目并尽快加以解决,队伍的成绩排名就会占有优势,心理上的压力也会小些。相反,一开始就没有选好题,或者所写的程序总有这样或那样的错误,要花很多时间去调试排错,就会浪费宝贵的时间,处于下风。
在这种你追我赶的激烈赛场上,比的是谁做得又快又好。竞赛过程中第一个重要的环
5、节是看题、审题和选题。一开始就选对题,一下子就切入主题是十分重要的。有时第一个环节遇到陷阱,“马失前蹄”,就会导致一筹莫展而步步落后。能否在第一环节占上优势取决于实践能力和洞察力,而实践能力与洞察力的提升需要实战,需要经验,需要学懂计算思维方式和解题策略。
参加ACM/ICPC活动,在与编程高手过招的过程中,可以把知识运用的综合性、灵活性和探索性发挥到极致,体验和感受数学思维与算法艺术之美,提升科学思维能力。
2“观察—联想—变换”思维方式
计算机解题的核心是算法设计,而算法设计需要具备良好的数学素养
6、。数学具有运用抽象思维去把握实际的能力,应用数学知识去解决实际问题时的建模过程是一个突出主要因素的科学抽象过程。进行抽象和形式化需要学习和掌握常用的计算思维方式。
科学思维能力的提高是成就事业最重要的因素之一,本书作者希望能在这方面对读者起到帮助作用。
编程解题的一般思维方法或过程,可以概述为“观察—联想—变换”,即通过对问题的观察,认识和理解该问题;然后通过联想,寻找该问题同已有知识和经验之间的联系;最后通过变换,把该问题转化为另一个或几个易于解决的新问题,最终达到解决原问题的目的。
“观察”是人类
7、认识客观事物的基本途径,就编程解题而言,“观察”是“联想”和“变换”的基础。一般地说,通过观察应当明确:求解的对象是什么;是枚举方案还是回答哪个存在性问题;已知的条件(包括隐含条件)是什么;能否用递推公式、递归公式、约束规则或状态转移方程把问题的条件、结论和求解途径表示出来;问题所涉及的这些计算式子各有什么特点等。
“联想”是由某种对象而引出其他相关对象的思维形式。就编程解题而言,“联想”的目的在于为“变换”提供可能的方向或线索。一般地说,在“观察”的基础上,通过联想应当明确:以前是否解过这类试题;是否解答过与其类似而又
8、稍有不同的试题;是否解答过与其有关的问题;能否利用解答这些问题时所使用的解题方法或所得到的结果;能否回忆出某个可能用得上的定理、公式或解题思路;为了能利用它,是否应当改变条件或结论的表现形式等。
“变换”是编程解题的基本手段。在“观察”和
