CCF 信息学奥赛基础篇中国计算机学会_中国计算机学会_9787111782339

本书是“CCF全国青少年信息学奥林匹克竞赛教程”丛书的第二册，旨在普及计算机科学与程序设计知识。书中遵循由浅入深、逻辑严密的编写思路，辅以丰富的实例解析，引领读者逐步提升计算思维能力。全书共四章，涉及C++程序设计进阶、数据结构及其应用、算法设计、数学运用等内容，全面覆盖NOI竞赛大纲所要求的基础知识。根据竞赛的特点，书中还对一些常见的难点和易错点进行了深入的解析。本书可作为信息学奥林匹克竞赛的教学用书，也可作为青少年学习计算机科学知识、了解信息学奥赛的参考资料。

在信息学的广阔天地中，编程不仅是一种技术，更是一门艺术。自1984年中国计算机学会举办青少年信息学奥林匹克竞赛以来，编程逐渐成为青少年科技教育的重要组成部分。这种教育不仅培养了无数青少年的编程能力，也激发了他们对计算机科学的热情和探索欲望。近年来，CCF组织编撰了《全国青少年信息学奥林匹克系列竞赛大纲》（以下简称“NOI竞赛大纲”）、《信息学奥林匹克辞典》，本书正是在此基础之上编写而成的，旨在为广大青少年提供一本深入浅出、实用高效的编程教材。我们发现，尽管已经出版了不少相关书籍，但真正能够契合青少年学习特点、兼顾理论深度与实践应用、精准覆盖NOI竞赛大纲的教材仍然稀缺。因此，我们希望通过这本“不一样”的书，为读者搭建一座从概念理解到实际运用的桥梁，让中小学编程爱好者能够迅速成长。本书具有以下几个突出特点：1循序渐进，深入浅出我们精心设计了一条由浅入深的学习路径。通过“情境导航”环节，从生活常识出发，引入问题。通过丰富的图示和通俗易懂的语言讲解核心概念，再逐步过渡到更复杂的算法实现。这种渐进式的学习方法旨在激发读者的学习兴趣，建立直观的算法和数据结构认识，并避免因概念陡增引起的畏难情绪。2问题导向，实践驱动通过“问题抽象”环节，从分析问题入手，抽象出知识或概念。每节都从一个实际问题（有些是经典竞赛题）出发，引导读者分析问题、思考解决方案，然后学习相关算法原理，找出解决问题的基本方法，最后通过程序代码来巩固所学知识。这种问题导向的方法不仅能激发读者的学习兴趣，更能培养他们解决实际问题的能力。3强调思维训练除了传授具体的算法知识之外，我们十分注重培养读者的算法思维。每节都设有“知识探究”“实践应用”“总结提升”等环节，引导并鼓励读者独立思考、大胆假设、认真求证。通过这种方式，我们希望读者不仅学会“是什么”，更能理解“为什么”。通过给出注意事项和拓展方向，引导读者进一步钻研，最终达到举一反三、触类旁通的目的。4紧扣竞赛实战作为一本面向信息学竞赛的教材，我们特别关注了竞赛中的重点和难点。本书围绕着信息学竞赛的核心需求编写，精选了很多经典的竞赛题目，通过详尽的解析和丰富的实例，向读者展示从问题分析到解决方案的全过程。此外，根据竞赛的特点，对一些常见的竞赛难点和易错点进行了深入的剖析和讲解。我们希望这些内容能够帮助读者更快地适应竞赛节奏，提高解题速度和准确率。5注重知识体系构建在信息学领域，编程和算法是两项不可或缺的核心技能。本书作为系列教材的基础篇，涵盖了NOI竞赛大纲中入门级的算法与数据结构知识，这些知识是构建信息学竞赛完整知识体系的重要环节。本书适合参加信息学奥林匹克竞赛的学生使用，同时也适合对信息学算法感兴趣的读者阅读。我们希望本书能够帮助读者在竞赛中取得更好的成绩，同时也为他们未来的学习和发展打下坚实的基础。本书是一把开启智慧之门的钥匙，是一本培养学习方法和思维习惯的教科书。我们希望每一位读者在学习本书的过程中，不仅能学会编程，更能学会如何思考和探索。作为编者，我们深知编写一本好的教材何等艰难。尽管我们倾注了大量心血，仍难免存在疏漏和不足。我们真诚地希望能得到广大读者、教育工作者和业内专家的批评指正，以便在后续版本中不断完善。最后，感谢所有为本书付出努力的人。感谢朱全民、宋新波等专家的指导和帮助，感谢所有读者对本书的关注和支持。希望本书能够成为你备战信息学奥林匹克竞赛的良师益友，陪伴你一起迎接挑战，创造辉煌。让我们共同在信息学的世界中探索未知，享受解决问题的乐趣，不断前行！江　涛2024年7月

丛书序前言第一章　C++程序设计进阶第一节　二维数组3一、情境导航3二、问题抽象3三、知识探究4（一）二维数组的定义4（二）二维数组的输入、输出4（三）贪吃蛇问题5四、实践应用6五、总结提升9第二节　多维数组11一、情境导航11二、问题抽象12三、知识探究12（一）三维数组的定义12（二）三维数组的输入、输出13（三）统计石头问题13四、实践应用15五、总结提升19第三节　常用数学函数23一、情境导航23二、问题抽象23三、知识探究24（一）绝对值函数24（二）四舍五入函数24（三）取下整函数（地板函数）25（四）取上整函数（天花板函数）26（五）平方根函数26（六）常用三角函数27（七）对数函数27（八）幂函数28四、实践应用29五、总结提升31第四节　自定义函数的参数33一、情境导航33二、问题抽象33三、知识探究34（一）形参和实参34（二）参数的传递方式34四、实践应用36五、总结提升38第五节　结构体与联合体42一、情境导航42二、问题抽象43三、知识探究44（一）结构体的引入44（二）结构体的定义44（三）创建结构体变量45（四）访问结构体变量的成员45（五）初始化结构体变量的成员45（六）结构体数组46（七）结构体作为函数参数46（八）图书馆里的寻书游戏46四、实践应用48五、总结提升51第六节　指针类型60一、情境导航60二、问题抽象60三、知识探究61（一）什么是指针61（二）如何声明指针61（三）指针的初始化62（四）使用指针62（五）指针和函数63（六）指针的算术运算63（七）指针与数组63（八）动态分配内存64四、实践应用66五、总结提升68第七节　STL（标准模板库）——算法函数72一、情境导航72二、问题抽象72三、知识探究73（一）什么是STL73（二）算法函数max、min、swap73（三）算法函数sort75四、实践应用77五、总结提升80第八节　STL（标准模板库）——线性容器85一、情境导航85二、问题抽象86三、知识探究87（一） STL的线性容器87（二） STL的向量(vector)87（三）向量的成员函数89（四） STL的链表（list）90（五） STL的队列（queue）92（六） STL的栈（stack）93（七）线性容器相关函数总结95四、实践应用96五、总结提升98第二章　数据结构及其运用第一节　线性结构——链表103一、情境导航103二、问题抽象103三、知识探究104（一）链表的基本概念104（二）链表的分类104（三）链表的操作105（四）链表操作的STL list实现105（五）链表操作的数组模拟实现106（六）双向链表操作的数组模拟实现109（七）循环链表操作的数组模拟实现111（八）为什么学习链表操作的数组模拟实现112四、实践应用112五、总结提升116第二节　线性结构——队列和栈116一、情境导航116二、问题抽象117三、知识探究117（一）什么是队列117（二）队列的基本操作117（三）队列操作的STL queue实现118（四）队列操作的数组实现119（五）与队列类似的栈121（六）栈的基本操作121（七）栈操作的STL stack实现121（八）栈操作的数组实现122四、实践应用124五、总结提升130第三节　树的引入133一、情境导航133二、问题抽象134三、知识探究134（一）什么是树134（二）树的表示与存储135（三）树的基本操作136四、实践应用137五、总结提升139第四节　二叉树141一、情境导航141二、问题抽象142三、知识探究142（一）什么是二叉树142（二）二叉树的性质143（三）二叉树的表示与存储143（四）二叉树的基本操作144四、实践应用144五、总结提升146第五节　二叉搜索树150一、情境导航150二、问题抽象151三、知识探究151（一）什么是二叉搜索树151（二）二叉搜索树的插入操作152（三）二叉搜索树的查找操作153（四）二叉搜索树的遍历操作154四、实践应用155五、总结提升157第六节　哈夫曼树160一、情境导航160二、问题抽象160三、知识探究161（一）什么是哈夫曼树161（二）构建哈夫曼树161（三）哈夫曼树的性质162（四）哈夫曼编码162（五）哈夫曼编码的实现163四、实践应用166五、总结提升169第七节　完全二叉树170一、情境导航170二、问题抽象170三、知识探究171（一）什么是完全二叉树171（二）完全二叉树的平衡性质171（三）完全二叉树的数组实现171（四）什么是堆173（五）堆的操作173四、实践应用175五、总结提升177第八节　图的定义和存储181一、情境导航181二、问题抽象182三、知识探究183（一）什么是图183（二）图的性质183（三）什么是图的邻接矩阵184（四）图的邻接矩阵的实现185（五）图的邻接矩阵的优缺点186（六）图的邻接链表186（七）图的邻接链表的实现187（八）图的邻接链表的优缺点188四、实践应用188五、总结提升190第三章　算法设计第一节　算法基础195一、算法概述195（一）算法的定义195（二）算法的特性195二、算法的描述195（一）自然语言描述195（二）流程图描述196（三）伪代码描述197（四）三种描述方式的比较197第二节　基础算法1——贪心法198一、情境导航198二、问题抽象198三、知识探究199（一）贪心法的定义与原理199（二）贪心法的适用场景199（三）分发饼干问题199四、实践应用201五、总结提升206第三节　基础算法2——递推法208一、情境导航208二、问题抽象209三、知识探究209（一）递推法的基本步骤209（二）递推法的适用场景210四、实践应用210五、总结提升213第四节　基础算法3——递归法214一、情境导航214二、问题抽象215三、知识探究216（一）什么是递归法216（二）斐波那契数列的递归法描述216（三）递归法的优点216四、实践应用217五、总结提升221第五节　基础算法4——二分法222一、情境导航222二、问题抽象223三、知识探究223（一）二分法原理223（二）二分法的基本步骤223四、实践应用225五、总结提升229第六节　基础算法5——倍增法233一、情境导航233二、问题抽象233三、知识探究234四、实践应用236五、总结提升238第七节　基础算法6——前缀和245一、情境导航245二、问题抽象245三、知识探究245（一）前缀和的定义与优势245（二）前缀和的适用场景246（三）用前缀和解决仓库统计问题246四、实践应用248五、总结提升250（一）注意事项250（二）算法复杂度250（三）前缀和的优缺点250第八节　数值处理算法256一、情境导航256二、问题抽象257三、知识探究257（一）高精度加法257（二）高精度减法259（三）高精度乘法262四、实践应用264五、总结提升265第九节　排序算法269一、情境导航269二、问题抽象270三、知识探究271（一）冒泡排序271（二）选择排序273（三）插入排序275四、实践应用276五、总结提升278第十节　搜索算法281一、情境导航281二、问题抽象282三、知识探究282（一）深度优先搜索282（二）广度优先搜索287四、实践应用290五、总结提升292第十一节　图论算法298一、情境导航298二、问题抽象299三、知识探究299（一）图的深度优先搜索299（二）图的广度优先搜索303四、实践应用305五、总结提升308第十二节　动态规划1——简单一维动态规划312一、情境导航312二、问题抽象312三、知识探究313（一）动态规划概述315（二）动态规划的原理315四、实践应用317五、总结提升320第十三节　动态规划2——简单背包类型动态规划321一、情境导航321二、问题抽象322三、知识探究329四、实践应用331五、总结提升334ⅩⅦⅩⅧ第十四节　动态规划3——简单区间类型动态规划335一、情境导航335二、问题抽象336三、知识探究337四、实践应用340五、总结提升344第四章　数学运用第一节　初等数论351一、情境导航351二、问题抽象351三、知识探究352（一）整除352（二）因数（因子）352（三）倍数352（四）指数352（五）质数与合数352（六）整数唯一分解定理352四、实践应用357五、总结提升363第二节　组合数学368一、情境导航368二、问题抽象369三、知识探究369（一）加法原理与乘法原理369（二）排列与组合370四、实践应用371五、总结提升374附录　本书内容与NOI竞赛大纲的对应关系379

你还可能感兴趣

我要评论