Algorithms Key Points Review | IB CIE 数学：算法考点精讲

📚 Algorithms Key Points Review | IB CIE 数学：算法考点精讲

Algorithms form the backbone of decision mathematics, appearing in both IB Mathematics: Applications and Interpretation and CIE Further Mathematics. Mastering algorithmic thinking – the ability to follow, modify and apply step-by-step procedures – is essential for tackling problems on graphs, networks, linear programming and numerical methods. This article breaks down the most frequently examined algorithms, presenting each one with clear steps, worked examples and exam tips that help you secure high marks.

算法是决策数学的核心，在 IB 数学：应用与解释以及 CIE 进阶数学中均有出现。掌握算法思维——即遵循、修改和应用逐步过程的能力——对于解决图、网络、线性规划和数值方法等问题至关重要。本文详细解析了最常考查的算法，通过清晰的步骤、示例和应试技巧，帮助你稳拿高分。

1. Algorithm Basics and Flowcharts | 算法基础与流程图

An algorithm is a finite sequence of well-defined instructions designed to solve a specific problem. In exams, you may be asked to trace an algorithm, complete a trace table, or identify its purpose. Flowcharts use standard symbols: oval for start/end, parallelogram for input/output, rectangle for process, diamond for decision. Always track variable values carefully and note that algorithms must terminate after a finite number of steps.

算法是为解决特定问题而设计的一组明确定义的有限指令序列。在考试中，你可能需要追踪算法、完成追踪表或识别其目的。流程图使用标准符号：椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理，菱形表示判断。务必仔细记录变量值，并注意算法必须在有限步骤后终止。

Terminator (oval): Start / End
Input/Output (parallelogram): READ, PRINT
Process (rectangle): x ← x + 1
Decision (diamond): IF condition THEN … ELSE …

终止符（椭圆）：开始 / 结束
输入/输出（平行四边形）：读取、打印
处理框（矩形）：x ← x + 1
判断框（菱形）：若条件成立则……否则……

Term	Meaning
Trace table	A table showing step-by-step changes in variable values.
Efficiency	How many steps an algorithm takes relative to input size.

术语	含义
追踪表	展示变量值逐步变化的表格。
效率	算法相对于输入大小所花费的步骤数。

2. Euclidean Algorithm for GCD | 求最大公因数的欧几里得算法

To find the greatest common divisor (GCD) of two integers a and b (a > b), repeatedly apply the division algorithm: a = bq + r, then replace a with b and b with r until r = 0. The last non-zero remainder is the GCD. This algorithm is also used to solve linear Diophantine equations and to find modular inverses, so it is highly examinable in both IB and CIE.

为求两个整数 a 与 b（a > b）的最大公因数（GCD），反复应用带余除法：a = bq + r，然后将 a 替换为 b，b 替换为 r，直至 r = 0。最后一个非零余数即为 GCD。该算法亦用于求解一次不定方程和模逆元，因此在 IB 与 CIE 考试中极为常见。

Example: Find GCD(252, 105).

示例：求 GCD(252, 105)。

252 = 105 × 2 + 42
105 = 42 × 2 + 21
42 = 21 × 2 + 0

The GCD is 21. The algorithm can be extended backwards to express gcd as a linear combination: 21 = 105 − 42×2 = 105 − (252 − 105×2)×2 = 5×105 − 2×252.

求得的 GCD 为 21。该算法可反向扩展，将最大公因数表示为线性组合：21 = 105 − 42×2 = 105 − (252 − 105×2)×2 = 5×105 − 2×252。

3. Bubble Sort Algorithm | 冒泡排序算法

Bubble sort compares adjacent pairs of items in a list and swaps them if they are in the wrong order. After each pass, the largest unsorted element “bubbles” to its correct position at the end. The algorithm stops when a complete pass is made without any swaps. Exam questions often ask for the state of the list after each pass and the total number of comparisons/swaps.

冒泡排序逐个比较列表中相邻的两个元素，如果顺序错误则交换。每完成一趟，最大的未排序元素便会“冒泡”至末尾的正确位置。当某一趟未发生任何交换时，算法停止。考题常要求写出每趟后列表的状态，以及比较和交换的总次数。

Initial list: 5, 3, 8, 1, 6

初始列表：5, 3, 8, 1, 6

Pass	List after pass	Swaps
1	3, 5, 1, 6, 8	3
2	3, 1, 5, 6, 8	1
3	1, 3, 5, 6, 8	1
4	1, 3, 5, 6, 8	0 (stop)

For n items, the worst-case number of comparisons is ½n(n−1). Bubble sort is O(n²) and is often contrasted with more efficient algorithms.

对于 n 个元素，最坏情况下的比较次数为 ½n(n−1)。冒泡排序的时间复杂度为 O(n²)，常与更高效的算法进行比较。

4. Dijkstra’s Shortest Path Algorithm | 迪杰斯特拉最短路径算法

Dijkstra’s algorithm finds the shortest path from a start node to all other nodes in a weighted graph with non-negative edge weights. It uses a labeling system: temporary labels (boxed) that are updated, and permanent labels (filled circle) that are fixed. The algorithm selects the unvisited node with the smallest temporary label, makes it permanent, and updates its neighbours.

迪杰斯特拉算法可在边权非负的加权图中，找出从起始节点到所有其他节点的最短路径。它使用标签系统：临时标签（方框）可被更新，永久标签（实心圆）一旦确定就不再改变。算法选取未访问节点中临时标签最小者，将其设为永久，并更新相邻节点的标签。

Worked steps:

解题步骤：

Set start node permanent label 0, all others ∞.
From current permanent node, update neighbours: if (label at current + weight) < neighbour's label, replace neighbour's temp label.
Choose smallest temp label in whole graph, make it permanent.
Repeat until all nodes are permanent.

将起始节点永久标签设为 0，其余节点临时标签设为 ∞。
从当前永久节点出发，更新相邻节点：若（当前节点标签 + 边权重）< 邻居标签，则替换邻居的临时标签。
选取全图中最小的临时标签，将其永久化。
重复直至所有节点均永久化。

Be careful to record the order of permanent labeling and to backtrack to find the actual path. Exam questions may also ask for the shortest distance and the route.

注意记录永久标签的顺序，并回溯以找出实际路径。考题可能还要求写出最短距离和路线。

5. Kruskal’s Algorithm for Minimum Spanning Tree | 最小生成树的克鲁斯卡尔算法

Kruskal’s algorithm builds a minimum spanning tree (MST) by selecting edges in order of increasing weight, provided they do not form a cycle. You must list all edges with weights, sort them, and then add each edge if it connects two previously unconnected components. Use a disjoint set or visual checking to detect cycles.

克鲁斯卡尔算法通过按权重递增的顺序选择边来构建最小生成树（MST），前提是加入的边不构成环。需列出所有边及其权重，排序后依次添加：若该边连接两个之前未连通的组件，则将其加入。可使用不相交集合或直观检查来检测环。

Edge	Weight
AB	2
CD	3
AC	4
BD	5

Sorted edges: AB(2), CD(3), AC(4), BD(5). Start with empty set. Add AB, CD. AC connects component {A,B} with {C,D}, add it. BD connects B and D, but they are already in the same component, so reject. MST total weight = 2+3+4 = 9.

排序后的边：AB(2), CD(3), AC(4), BD(5)。从空集开始。加入 AB，加入 CD。AC 连接了包含 A、B 的组件与包含 C、D 的组件，加入。BD 连接 B 和 D，但它们已在同一组件中，故拒绝。MST 总权重 = 2+3+4 = 9。

6. Prim’s Algorithm on a Table / Matrix | 表格/矩阵上的普里姆算法

Prim’s algorithm also finds an MST but grows it from an initial node. When the graph is given as a distance table or matrix, the method is: start at any vertex, delete its row, and number that column. Scan the numbered columns for the smallest available entry, circle it, add that edge, delete the row of the new vertex, and number its column. Repeat until all columns are numbered.

普里姆算法同样可求最小生成树，但从一个初始节点逐步生长。当图以距离表或矩阵形式给出时，方法为：从任意顶点开始，删除其所在行，并给该列编号；在已编号的列中寻找最小可用值，将其圈出，加入该边，删除新顶点的行，并给其列编号；重复直至所有列均已编号。

	A	B	C	D
A	–	5	4	3
B	5	–	2	6
C	4	2	–	7
D	3	6	7	–

Start at A: delete row A, number column A (1). Smallest in column A is 3 (AD). Circle AD, delete row D, number column D (2). Now numbered columns A and D; scan for smallest remaining: 4 (AC). Circle AC, delete row C, number column C (3). Next smallest from numbered columns A,C,D is 2 (CB). Circle CB, delete row B, number column B (4). MST: AD(3), AC(4), CB(2) total = 9.

从 A 开始：删除行 A，编号列 A (1)。在列 A 中最小值为 3 (AD)。圈出 AD，删除行 D，编号列 D (2)。现在已编号列 A 和 D；扫描剩余最小值：4 (AC)。圈出 AC，删除行 C，编号列 C (3)。在已编号列 A、C、D 中扫描：最小为 2 (CB)。圈出 CB，删除行 B，编号列 B (4)。MST：AD(3)、AC(4)、CB(2)，总权重 = 9。

7. Route Inspection (Chinese Postman) Algorithm | 路径检查（中国邮差）算法

The route inspection problem aims to find the shortest route that traverses every edge at least once and returns to the start. If the graph is Eulerian (all vertices even degree), any Eulerian circuit is optimal. If odd-degree vertices exist, the algorithm pairs them to minimise the total added distance, enabling a semi-Eulerian traversal. This appears in IB AI HL and CIE Decision Maths.

中国邮差问题旨在寻找至少遍历每条边一次并返回起点的最短路径。若图为欧拉图（所有顶点度数为偶数），则任意欧拉回路最优。若存在奇度顶点，算法将奇度顶点配对以最小化总重复距离，从而形成半欧拉遍历。该内容在 IB AI HL 和 CIE 决策数学中均有出现。

Steps:

步骤：

Identify all odd-degree vertices. There must be an even number of them.
List all possible pairings and find the shortest path distances between each pair (using Dijkstra if needed).
Choose the pairing that gives the smallest total extra distance.
Add those shortest paths as duplicated edges to the original graph. An Eulerian circuit can now be found on the enlarged graph.

找出所有奇度顶点，其个数必为偶数。
列出所有可能的配对方式，并找出每对顶点间的最短路径距离（必要时使用迪杰斯特拉算法）。
选择使总额外距离最小的配对。
将这些最短路径作为重复边加入原图。现在可在扩大的图上找到欧拉回路。

Total route length = sum of all original edge weights + extra distance from pairing.

路线总长度 = 所有原始边权重之和 + 配对产生的额外距离。

8. Linear Programming: Graphical Method | 线性规划的图解法

For two-variable linear programming problems, the graphical method is required. Plot the constraint inequalities, shade the feasible region, then use the objective function line to find the optimal vertex. Move the objective line parallel to itself until it last touches the feasible region. Integer solutions require checking points near the boundary when the optimum is not integer.

对于双变量线性规划问题，须使用图解法。绘制约束不等式，标出可行域，再利用目标函数直线寻找最优顶点。将目标直线平行移动，直至其最后一次接触可行域。当最优解非整数时，需检查边界附近的整数点以求得整数解。

Example: Maximise P = 3x + 2y subject to x + y ≤ 8, 2x + y ≤ 10, x, y ≥ 0.

示例：最大化 P = 3x + 2y，约束条件为 x + y ≤ 8, 2x + y ≤ 10, x, y ≥ 0。

Vertices of feasible region: (0,0), (0,8), (5,0) and intersection of x+y=8 and 2x+y=10 → (2,6). Evaluate P: (0,0)=0, (0,8)=16, (5,0)=15, (2,6)=18. Max P=18 at x=2, y=6.

可行域顶点：(0,0), (0,8), (5,0) 以及 x+y=8 与 2x+y=10 的交点 (2,6)。计算 P 值：(0,0)=0, (0,8)=16, (5,0)=15, (2,6)=18。最大 P=18 在 x=2, y=6 处取得。

9. Simplex Algorithm (Introduction for IB/CIE) | 单纯形法（IB/CIE 入门）

The simplex method solves linear programmes with more than two variables. The problem is converted to standard form using slack variables, and a simplex table is iterated. Starting from the initial basic feasible solution, the pivot column is chosen from the most negative entry in the objective row (for maximisation), and the pivot row is the one with the smallest non-negative ratio. Row operations are used to obtain the next tableau until all objective row entries are non-negative.

单纯形法求解变量多于两个的线性规划。问题通过松弛变量转化为标准形，并使用单纯形表迭代。从初始基本可行解开始，在目标行（最大化问题）中选择最负的项作为主元列，主元行则为具有最小非负比值的行。通过行运算得到下一表格，直至目标行所有项均非负。

A typical simplex tableau:

典型单纯形表：

Basic	x	y	s1	s2	RHS
s1	1	2	1	0	12
s2	2	1	0	1	16
P	-3	-5	0	0	0

Select the most negative in P-row (-5) as pivot column (y). Ratios: 12÷2=6, 16÷1=16. Pivot row is s1. After row operations, the next tableau will have y as basic variable, and the process repeats.

选择 P 行中最负的 -5 作为主元列 (y)。比值：12÷2=6，16÷1=16。主元行为 s1。行运算后，下一表格将以 y 为基变量，过程重复进行。

10. Numerical Methods: Bisection and Newton-Raphson | 数值方法：二分法与牛顿-拉弗森法

CIE P3 and IB AI HL both cover numerical solutions of equations. The bisection method repeatedly halves an interval [a, b] where f(a) and f(b) have opposite signs, narrowing to a root. Newton-Raphson uses iteration xₙ₊₁ = xₙ − f(xₙ)/f ‘(xₙ), requiring an initial guess. Ensure convergence and show iterations to required accuracy.

CIE P3 与 IB AI HL 均涵盖方程的数值解法。二分法通过不断对分区间 [a, b] 来逼近根，其中 f(a) 与 f(b) 异号。牛顿-拉弗森法使用迭代公式 xₙ₊₁ = xₙ − f(xₙ)/f ‘(xₙ)，需提供初始猜测值。务必确保收敛，并按所需精度展示迭代过程。

Bisection: root of f(x) = x³ − 2x − 5
f(2)=−1, f(3)=16 → sign change. Midpoint 2.5: f(2.5)=5.625 → positive, so new interval [2, 2.5]. Continue until |a−b| < tolerance.

二分法：求 f(x) = x³ − 2x − 5 的根
f(2)=−1, f(3)=16 → 异号。中点 2.5：f(2.5)=5.625 → 正，新区间 [2, 2.5]。继续直至 |a−b| 小于容许误差。

Newton-Raphson: xₙ₊₁ = xₙ − (xₙ³ − 2xₙ − 5)/(3xₙ² − 2)
Start x₀ = 2: x₁ = 2 − (−1)/(10) = 2.1. x₂ = 2.1 − (0.061/11.23) ≈ 2.0946. The root is ≈ 2.095 to 3 d.p.

Newton-Raphson is faster but may fail if the derivative is zero or the guess is poor. Always check the method’s validity before applying.

牛顿-拉弗森法速度更快，但若导数为零或初始猜测不佳则可能失效。应用前，务必验证方法的有效性。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Algorithms Key Points Review | IB CIE 数学：算法 考点精讲