gesp-c-五级 · 相关章节

初等数论是研究整数性质的数学分支，其内容在程序设计中有着广泛应用，如密码学、算法优化、数据校验等。本章对应 GESP C++ 五级知识块 1：初等数论，覆盖大纲要求的全部考点：素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性，以及欧几里得算法、唯一分解定理、埃氏筛法与线性筛法。

在 C 和 C++ 语言中，基本数据类型（如 int、long long）能表示的整数范围有限，例如 int 通常最大为 2147483647，当需要处理超出此范围的大整数（如几百位甚至几千位的整数）时，就需要借助数组来模拟高精度计算。数组模拟高精度计算的核心思想是用数组的每个元素存储大整数的一位数字，通过模拟人工计算的方式实现加、减、乘、除等运算。

动态数组（Dynamic Array）是一种在程序运行时可以灵活调整大小的数组结构，它克服了静态数组编译时确定大小的限制，能够根据实际需求动态分配和释放内存。动态数组是处理不确定规模数据的重要工具，也是后续链表（第44章）、高精度（第42章）等五级考点的内存基础。

线性表是计算机科学中最基础、最常用的数据结构之一，它是由 $n$ 个具有相同特性的数据元素组成的有限序列。本章对应 GESP C++ 五级知识块 4：链表，要求掌握单链表、双链表、循环链表的创建、插入、删除、遍历、查找、反转等基本操作，并理解三者的区别。

递归（Recursion）指在函数的定义中直接或间接调用函数自身的过程。它通过将复杂大问题拆解为结构相同、规模更小的子问题，先求解小规模基础情况，再反向推导原问题答案。本章对应 GESP C++ 五级知识块 6：递归算法，要求掌握递归基本原理、能分析其时间与空间复杂度，并了解递归的优化策略。

二分查找（Binary Search）又称折半搜索，是一种高效的查找算法，仅适用于有序序列，核心思路不断折半缩小搜索区间，将线性 $O(n)$ 查找优化为对数 $O(\log n)$ 级别。本章对应 GESP C++ 五级知识块 5：二分算法，要求掌握二分查找与二分答案（二分枚举法）。

贪心算法（Greedy Algorithm）是一种通过在每一步选择中采取局部最优策略，逐步构造完整解，期望最终得到全局最优解的算法思想。贪心只依据当前状态做最优决策，不考虑后续长远影响。本章对应 GESP C++ 五级知识块 8：贪心算法，要求理解最优子结构，能使用贪心算法解决相关问题。

分治算法（Divide and Conquer）核心思想为分而治之：将一个规模大、难以直接求解的原问题，拆分为若干结构相同、规模更小的独立子问题；递归求解所有子问题后，再将子问题的解合并，得到原问题的最终答案。本章对应 GESP C++ 五级知识块 7：分治算法，要求能用归并排序和快速排序对数组排序。

本章是五级备考的"速通手册"。我们统计了 2023 年 9 月至 2026 年 6 月 共 12 场真实认证（来源：CCF GESP 官方真题、洛谷题单、各机构真题解析）的编程题，归纳出出现频率最高的 6 大类核心程序。把它们背熟、写熟，编程题就稳了。

复杂度估算是 GESP C++ 五级知识块 2 的独立考点：要求掌握算法复杂度估算方法，尤其含多项式（如 $O(n)$、$O(n^2)$）与对数（如 $O(\log n)$、$O(n\log n)$）的复杂度。本章补充分章，因为五级大纲把它与大整数、链表、二分、递归、分治、贪心并列为核心知识块，而前 8 章（41–48）未设专门章节。掌握复杂度，才能在选择算法时判断"会不会超时"。