自1996年中国首次举办ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest,ACMICPC或ICPC,网址https://icpc.baylor.edu)亚洲区预选赛以来,国内高校越来越重视大学生程序设计竞赛。中国大学生程序设计竞赛(China Collegiate Programming Contest,CCPC,网址https://ccpc.io)旨在“激励当代大学生运用计算机编程技术和技能来解决实际问题,激发其学习算法和程序设计的兴趣,培养其团队合作意识、创新能力和挑战精神”。目前,ICPC、CCPC及团体程序设计天梯赛(Group Programming Ladder Tournament,GPLT,网址https://gplt.patest.cn/)等是国内大学生主要参加的大规模赛事。
对于零基础学习程序设计课程且希望在程序设计竞赛方面具有较好基础的学生而言,程序设计竞赛与课程教学相结合的教材比较难寻。而本书主要以C++语言描述过程化程序设计,同时兼顾C语言,着重引入大学生程序设计竞赛的基础知识,能满足这类学生的需求。本书重点讨论过程化程序设计的基础知识、程序控制结构、数组、函数、结构体、指针、链表等方面的内容,希望能为零基础学习C/C++程序设计的同学打下较好的基础。另外,本书还引入大学生程序设计竞赛的基础知识,主要包括在线做题结构、空间换时间思想与方法、C++标准模板库(Standard Template Library,STL)常用容器、递推与动态规划、深度优先搜索与广度优先搜索、查找与排序、贪心法与回溯法、大整数运算及简单数学问题等,希望对拟参加大学生程序设计竞赛的同学有所帮助。
本书立足于在线测评系统(Online Judge,OJ),以OJ上的问题为载体和核心,把对问题的分析和求解作为主线,简化了语法和理论知识的讲解,注重运用知识求解具体问题。本书以问题为导向,适合学生针对OJ问题进行探究式学习,注重培养学生的计算思维及编程求解具体问题的能力。
书中带“*”的章节,主要是程序设计竞赛相关的内容,可根据实际需要,作为学生自主学习的内容,或由教师酌情选讲。因本书编程方面的例题与习题较多,故教师可以酌情选讲,学生也可以酌情选学。
本书中的编程例题、习题主要来自OJ。书中大部分例题和编程习题来自绍兴文理学院OJ(简称HLOJ,网址http://acm.usx.edu.cn),这离不开绍兴文理学院程序设计类课程组教师历年来的辛勤工作,在此对他们表示由衷的感谢!书中部分编程例题和习题参考改编自浙江大学OJ(ZOJ,网址https://zoj.pintia.cn/)、杭州电子科技大学OJ(HDOJ,网址http://acm.hdu.edu.cn)、浙江工业大学OJ(ZJUTOJ,网址http://cpp.zjut.edu.cn)等OJ上的题目,在此对出题者及相关的老师、同学表示由衷的感谢!为便于读者在OJ上练习,每章的OJ题解及OJ编程题都标注了一个出处(标题、描述等方面可能有所改编)。
在编写本书的过程中,作者参阅了国内外一些C/C++程序设计语言、数据结构与算法方面的著作,从中吸收了新的思想、新的内容,书中部分内容和习题参考了这些著作及其网络资源,在这里对所参考著作的作者及相关人员表示衷心感谢!
本书受浙江省首批高等学校省级精品在线开放课程“高级语言”、浙江省一流课程“高级语言”、教育部产学合作协同育人项目(项目编号: 201902047018)支持,在此表示衷心感谢!
在编写本书的过程中,编者力图在问题驱动、竞赛引导、能力导向及强化实践等方面有所突破、有所创新,然而受限于能力和水平,书中难免存在疏漏和不足之处,恳请阅读本书的读者批评指正。
编者
2020年8月