📚

GESP 5 级 C++ 教案

22 课,从素数讲到快排——给 12 岁同学的 eli5 学习包

📋 考试形式(GESP 五级)

单选题 15 道(2 分/道)· 判断题 10 道(2 分/道)· 编程题 2 道(25 分/道),考试时间 180 分钟。

考核目标:掌握初等数论知识点,能用辗转相除法、埃氏筛与线性筛、唯一分解定理解题;掌握单/双/循环链表基本操作;掌握复杂度估算(多项式、对数);熟悉二分、分治、贪心、递归思想并能按实际选题;C++ 会用数组模拟高精度加、减、乘、除。

📖 知识点大纲(官方原文整理)

  1. 初等数论:素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性。
  2. 高精度运算(C++ 特有):数组模拟高精度加、减、乘、除。
  3. 链表:创建、插入、删除、遍历、反转;单链表、双链表、循环链表的区别。
  4. 数论算法:辗转相除法(欧几里得算法)、埃氏筛法与线性筛法、唯一分解定理。
  5. 复杂度估算:算法复杂度估算方法(含多项式、对数)。
  6. 二分法:二分查找和二分答案(二分枚举法),在有序数组中快速定位目标值。
  7. 递归:递归基本原理与应用,分析时间/空间复杂度,了解递归优化策略。
  8. 贪心:贪心基本原理,理解最优子结构,用贪心解题。
  9. 分治:分治基本原理,用归并排序和快速排序排序。

来源:爱思创信息学奥赛《GESP 认证 5-6 级大纲上线通知》(2023-08-04),六级大纲见下方附录。

📖 附录:术语对照(章节名 + 关键词,中英文)

📑 章节名(22 课)
01 素数与合数Primes and Composite Numbers
02 最大公约数与最小公倍数GCD (Greatest Common Divisor) and LCM (Least Common Multiple)
03 同余与模运算Congruence and Modulo Arithmetic
04 约数与倍数Divisors and Multiples
05 质因数分解Prime Factorization
06 奇偶性Parity (Even and Odd)
07 高精度加法High-precision Addition
08 高精度减法High-precision Subtraction
09 高精度乘法High-precision Multiplication
10 高精度除法High-precision Division
11 链表基础Linked List Basics
12 链表的种类Kinds of Linked Lists: Singly / Doubly / Circular
13 辗转相除法Euclidean Algorithm
14 埃氏筛与线性筛Sieve of Eratosthenes and Linear (Euler) Sieve
15 唯一分解定理Fundamental Theorem of Arithmetic (Unique Factorization)
16 复杂度估算Estimating Complexity (Big-O Notation)
17 二分查找Binary Search
18 二分答案Binary Search on the Answer
19 递归Recursion
20 贪心算法Greedy Algorithm
21 分治与归并排序Divide and Conquer; Merge Sort
22 快速排序Quick Sort
🔑 关键词 · 数论
素数 / 质数Prime Number
合数Composite Number
最大公约数GCD — Greatest Common Divisor
最小公倍数LCM — Least Common Multiple
同余Congruence(a ≡ b (mod m))
模 / 取余Modulo (mod) / Remainder
约数(因数)Divisor / Factor
倍数Multiple
质因数Prime Factor
奇偶性Parity(even / odd)
🔑 关键词 · 高精度与数据结构
高精度(大数)Big Number / Arbitrary-precision
数组模拟Simulated with an Array
进位 / 借位Carry / Borrow
链表Linked List
节点Node
指针 / 下标Pointer / Index
头指针Head Pointer
单链表Singly Linked List
双链表Doubly Linked List
循环链表Circular Linked List
遍历Traversal
反转Reversal
🔑 关键词 · 算法与复杂度
辗转相除法Euclidean Algorithm
埃氏筛Sieve of Eratosthenes
线性筛 / 欧拉筛Linear Sieve / Euler Sieve
唯一分解定理Fundamental Theorem of Arithmetic
时间复杂度 / 空间复杂度Time Complexity / Space Complexity
大 O 记号Big-O Notation:O(n)、O(n log n)、O(n²)、O(2ⁿ)
对数Logarithm(log n)
二分查找Binary Search
二分答案 / 二分枚举Binary Search on the Answer
单调性(可行连成一片)Monotonicity(feasible region is contiguous)
递归 / 基本情况Recursion / Base Case
调用栈 / 栈溢出Call Stack / Stack Overflow
记忆化Memoization
贪心 / 局部最优Greedy / Locally Optimal
最优子结构Optimal Substructure
反例Counterexample
分治Divide and Conquer
哨兵(基准元素)Pivot
划分(分区)Partition
稳定排序Stable Sort
原地排序In-place Sort
最好情况 / 最坏情况Best Case / Worst Case

🗂️ 教案目录(22 课,按模块分组)

🔢 数论(6 课)
01⭐ 素数与合数→ 02🧩 最大公约数与最小公倍数→ 03🕐 同余与模运算→ 04🔗 约数与倍数→ 05🧱 质因数分解→ 06👫 奇偶性→
🧮 高精度(4 课,数组模拟)
07➕ 高精度加法→ 08➖ 高精度减法→ 09✖️ 高精度乘法→ 10➗ 高精度除法→
🔗 数据结构(2 课)
11🔗 链表基础:创建/插入/删除/遍历/反转→ 12🔀 链表的种类:单/双/循环→
⚙️ 算法(10 课)
13🔄 辗转相除法(欧几里得算法)→ 14🧹 埃氏筛与线性筛→ 15🧮 唯一分解定理→ 16⏱️ 复杂度估算(多项式、对数)→ 17🎯 二分查找→ 18📏 二分答案(二分枚举)→ 19🪆 递归→ 20🪙 贪心算法→ 21🌗 分治与归并排序→ 22🚀 快速排序→

📎 附录:GESP 六级大纲(本学习包已含六级教案)

  1. 树的基本概念、构造与遍历
  2. 哈夫曼树、完全二叉树、二叉排序树
  3. 哈夫曼编码、格雷编码
  4. DFS / BFS / 二叉树搜索
  5. 简单动态规划(一维 DP、简单背包)
  6. 面向对象:封装、继承、多态,类的创建与使用
  7. 栈、队列、循环队列
六级 15 课教案:树 7 课 → 图搜索 2 课 → 动态规划 2 课 → 栈与队列 2 课 → 面向对象 2 课,见 总目录 · 六级部分,或直接进入 01 树与二叉树的基本概念。