🎲

GESP 八级 C++ 教案

14 课,从数数的道理讲到算法优化——每课拆子任务、带手推演算和答案

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

  1. 计数原理:加法原理、乘法原理
  2. 排列与组合:排列、组合的基本概念,基础排列组合编程问题
  3. 杨辉三角:定义、实现、与组合的关系
  4. 倍增法:概念、时间复杂度(O(log n))
  5. 代数与平面几何(初中数学):一元一次方程、二元一次方程;三角形、圆形、长方形面积
  6. 图论算法及综合应用:最小生成树(概念、Kruskal、Prim);最短路径(概念、Dijkstra、Floyd);综合应用与问题求解技巧
  7. 算法的时间和空间效率分析:一般分析方法;各类算法(排序、查找、树图遍历、搜索、分治、DP)的复杂度
  8. 算法优化:不同方法的时空差异;数学知识辅助优化(如等差数列和用公式);一般优化技巧
怎么学:每课 = 比方 → 大图 → 4 个子任务(每个有小目标、手推演算、带答案的小检查)→ 完整代码 → 你来试试。模块 A(组合数学)依赖循环与双重 for;模块 B(倍增法与初中数学)依赖七级 C01 数学库,方程/几何用 double;模块 C(图论算法)依赖七级模块 C(图 + DFS/BFS)与五级排序(Kruskal 要排序);模块 D(复杂度与优化)依赖五级 C16 复杂度估算与七级 C07 滚动数组。
考试形式(八级):单选 15 道(2 分/道)+ 判断 10 道(2 分/道)+ 编程 2 道(25 分/道),共 180 分钟,C++11 标准。八级是 GESP 的最高级:组合数学 + 初中代数几何 + 四大图论算法(Kruskal / Prim / Dijkstra / Floyd)+ 复杂度分析,都是综合运用的重头戏。

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

🎲 模块 A · 组合数学(4 课)
01🎲 计数原理:加法与乘法→ 02🏃 排列:顺序有关系的计数→ 03📸 组合:顺序没关系的计数→ 04🔺 杨辉三角:数字金字塔→
⚡ 模块 B · 倍增法与初中数学(3 课)
05🚀 倍增法:快速幂→ 06⚖️ 一元一次与二元一次方程→ 07🏠 平面几何:面积计算→
🌉 模块 C · 图论算法(5 课)
08🌉 最小生成树:Kruskal 算法→ 09🌱 Prim 算法:从一点长成一棵树→ 10💧 Dijkstra:单源最短路→ 11🗺️ Floyd:任意两点最短路→ 12🧰 图论工具箱:选对工具→
⏱️ 模块 D · 复杂度分析与优化(2 课)
13⏱️ 时间和空间复杂度分析→ 14🚄 算法优化:同样的事做得更快→

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

📑 章节名(14 课)
01 计数原理:加法与乘法Counting Principles: Addition & Multiplication
02 排列:顺序有关系的计数Permutations (Order Matters)
03 组合:顺序没关系的计数Combinations (Order Does Not Matter)
04 杨辉三角:数字金字塔Pascal's Triangle
05 倍增法:快速幂Doubling Method: Fast Power (Exponentiation by Squaring)
06 一元一次与二元一次方程Linear Equations (One / Two Variables)
07 平面几何:面积计算Plane Geometry: Areas (Rectangle, Triangle, Circle)
08 最小生成树:Kruskal 算法Minimum Spanning Tree: Kruskal's Algorithm
09 Prim 算法:从一点长成一棵树Prim's Algorithm (Grow a Tree from One Vertex)
10 Dijkstra:单源最短路Dijkstra's Algorithm (Single-Source Shortest Path)
11 Floyd:任意两点最短路Floyd-Warshall Algorithm (All-Pairs Shortest Paths)
12 图论工具箱:选对工具Graph Algorithm Toolbox (Choosing the Right Tool)
13 时间和空间复杂度分析Time and Space Complexity Analysis
14 算法优化:同样的事做得更快Algorithm Optimization (Doing the Same Job Faster)
🔑 关键词 · 组合数学
加法原理(分类做,相加)Addition Principle (Categories → Add)
乘法原理(分步做,相乘)Multiplication Principle (Steps → Multiply)
排列 / 顺序有关系Permutation (Order Matters)
A(n,k) 排列数Arrangement Number A(n, k)
全排列 / 阶乘 n!Permutations of All n Elements / Factorial n!
组合 / 顺序没关系Combination (Order Does Not Matter)
C(n,k) 组合数Combination Number C(n, k)
握手问题Handshake Problem
杨辉三角Pascal's Triangle
🔑 关键词 · 倍增法与初中数学
倍增法Doubling / Exponentiation by Squaring
快速幂Fast Power (a^b in O(log b))
二进制拆分指数Binary Expansion of the Exponent
一元一次方程Linear Equation in One Variable
二元一次方程 / 方程组Linear Equation in Two Variables / System of Equations
消元法Elimination
面积 / 周长Area / Perimeter
圆面积 πr² / 周长 2πrCircle Area πr² / Circumference 2πr
🔑 关键词 · 图论与复杂度
生成树Spanning Tree
最小生成树(MST)Minimum Spanning Tree (MST)
环 / 成环判断Cycle / Cycle Detection
并查集 / 同组表Union-Find (Disjoint Set)
Kruskal 算法Kruskal's Algorithm
Prim 算法Prim's Algorithm
单源最短路Single-Source Shortest Path
Dijkstra 算法Dijkstra's Algorithm
松弛操作Edge Relaxation
全源最短路All-Pairs Shortest Paths
Floyd-Warshall 算法Floyd-Warshall Algorithm
时间复杂度Time Complexity
空间复杂度Space Complexity
大 O 记号Big O Notation
前缀和Prefix Sum
等差数列求和公式Sum of an Arithmetic Series
滚动数组Rolling Array
空间换时间Space for Time