📚 Mastering Algorithms in IB & OCR Mathematics: Key Concepts | IB & OCR 数学：算法考点精讲
Algorithms lie at the heart of mathematical problem-solving, linking discrete reasoning with computational thinking. In both the IB Diploma (particularly Applications & Interpretation HL) and OCR AS/A Level Mathematics and Further Mathematics, you will encounter a range of algorithms—from classic numerical methods to graph theory and sorting routines. This revision guide breaks down the essential algorithmic concepts, step-by-step processes, and typical exam-style applications you need to master.
算法是数学问题解决的核心，它将离散推理与计算思维联系起来。在IB文凭（尤其是应用与解释高水平）和OCR AS/A Level数学及进阶数学中，你会遇到一系列算法——从经典的数值方法到图论和排序程序。本复习指南将分解你需要掌握的基本算法概念、逐步流程以及典型的考试式应用。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite, ordered set of unambiguous instructions designed to perform a task or solve a problem. In mathematics, algorithms guarantee a result after a finite number of steps, provided initial conditions are met. Their representations include pseudo-code, flowcharts, and written step-by-step descriptions.
算法是一组有限、有序且明确的指令，旨在执行任务或解决问题。在数学中，算法在满足初始条件的情况下，经有限步骤后保证得到一个结果。其表示形式包括伪代码、流程图和书面的逐步描述。
Both IB and OCR specifications emphasise algorithmic thinking: tracing an algorithm by hand, modifying existing algorithms, and understanding efficiency. Common categories include numerical methods (root-finding), sorting and searching, and graph algorithms for networks.
IB和OCR大纲都强调算法思维：手工追踪算法、修改现有算法以及理解效率。常见的类别包括数值方法（求根）、排序和搜索，以及用于网络的图论算法。
2. Tracing and Designing Algorithms | 算法的追踪与设计
Before diving into specific algorithms, you should be able to trace the values of variables through each step. A trace table is used to record variable states after every instruction. This helps identify logical errors and predict output without executing code.
在深入具体算法之前，你应该能够追踪每一步的变量取值。追踪表用于记录每条指令执行后的变量状态。这有助于识别逻辑错误，并无需执行代码即可预测输出。
Design skills involve breaking a problem into smaller parts, using loops, conditional statements and assignments. OCR often presents pseudo-code with keywords like WHILE, IF...THEN...ELSE, and INPUT. IB may use informal language; however, clear structuring is equally rewarded.
设计技能包括将问题分解为更小的部分，使用循环、条件语句和赋值。OCR通常出现带有关键词的伪代码，如WHILE、IF...THEN...ELSE和INPUT。IB可能使用非正式语言；然而，清晰的结构同样会得奖分。
3. Euclidean Algorithm for GCD | 求最大公因数的欧几里得算法
A fundamental algorithm for finding the greatest common divisor (GCD) of two integers. Repeatedly apply the division algorithm: replace the larger number by the remainder when dividing the smaller number into it, until the remainder becomes zero. The last non-zero remainder is the GCD.
求两个整数最大公因数（GCD）的基本算法。重复应用带余除法：用较小数除较大数，将较大数替换为余数，直到余数为零。最后一个非零余数就是最大公因数。
Example: Find gcd(252, 105).
105 = 2 remainder 42; 105 ÷ 42 = 2 remainder 21; 42 ÷ 21 = 2 remainder 0. Hence gcd = 21.
示例：求 gcd(252, 105)。
252 ÷ 105 = 2 余 42；105 ÷ 42 = 2 余 21；42 ÷ 21 = 2 余 0。因此 gcd = 21。
This algorithm appears in IB and can be applied to solve Diophantine equations, while OCR further mathematics may use it in modular arithmetic contexts. Ensure you can present the steps in a clear table.
该算法出现在IB考试中，并可用于求解丢番图方程，而OCR进阶数学可能在模运算情境中使用它。确保你能够用清晰的表格呈现步骤。
4. Bisection Method (Interval Halving) | 二分法（区间半分法）
f f(c) has the same sign as f(a), replace a with c; otherwise, replace b with c. Repeat until the interval width is less than a desired tolerance.
用于寻找连续函数 f(x) 在区间 [a, b] 上的根，其中 f(a) 和 f(b) 异号。计算中点 c = (a+b)/2。如果 f(c) 与 f(a) 同号，则用 c 代替 a；否则用 c 代替 b。重复直至区间宽度小于所需容差。
Midpoint c = (a + b) / 2
误差范围 ≤ (b - a) / 2ⁿ (经过 n 次迭代)
Both IB AI and OCR (A Level Mathematics, numerical methods) test the bisection method. You must be able to complete a table of signs, decide the next interval, and calculate the maximum error after n iterations. A typical OCR question will ask for the root to a specified number of decimal places.
IB AI和OCR（A Level数学，数值方法）都会考查二分法。你必须能够完成符号表、决定下一个区间，并计算n次迭代后的最大误差。典型的OCR题目会要求将根算到指定小数位数。
5. Newton-Raphson Method | 牛顿-拉夫逊方法
finding successively better approximations to the roots of a function: xₙ₊₁ = xₙ - f(xₙ)/f' s quadratically when the initial guess is close enough to the true root, but may fail if f'(x) is near zero.
一种迭代公式，用于逐步逼近函数的根：xₙ₊₁ = xₙ - f(xₙ)/f'(xₙ)。当初值猜测足够靠近真根时，该方法具有二次收敛性，但如果 f'(x) 接近于零，可能会失败。
xₙ₊₁ = xₙ - f(xₙ) / f'(xₙ)
This method is examined in OCR A Level Maths (pure) and in IB mathematics when calculus is applied to approximation problems. You are expected to derive the iteration from a given function, perform successive iterations, and comment on convergence.
该方法在OCR A Level数学（纯数）以及将微积分应用于逼近问题的IB数学中考查。你需要从给定函数推导出迭代式，执行连续迭代，并评论收敛性。
6. Bubble Sort Algorithm | 冒泡排序算法
A simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. Each pass 'bubbles' the next largest element to its correct position. The algorithm terminates when a complete pass requires no swaps.
一种简单的排序算法，它反复遍历列表，比较相邻元素，若顺序错误则交换它们。每一轮将下一个最大元素“冒泡”到正确位置。当某次完整遍历无需交换时，算法终止。
Trace example for [6, 3, 8, 5]:
1: compare 6,3 → swap → [3,6,8,5]; compare 6,8 → no swap; compare 8,5 → swap → [3,6,5,8].
compare 3,6 no swap; 6,5 swap → [3,5,6,8]; compare 6,8 no swap. Pass 3: no swaps → sorted.
追踪示例：[6, 3, 8, 5]：
第一轮：比较6,3 → 交换 → [3,6,8,5]；比较6,8 → 不交换；比较8,5 → 交换 → [3,6,5,8]。
第二轮：[3,6,5,8] → 比较3,6不交换；6,5交换 → [3,5,6,8]；比较6,8不交换。第三轮：无交换 → 已排序。
Both IB AI and OCR Further Mathematics (Discrete) feature bubble sort as an introductory sorting algorithm. You may be asked to count comparisons and swaps, or identify the state of the list after a given number of passes.
IB AI和OCR进阶数学（离散）都将冒泡排序作为入门排序算法。你可能需要统计比较和交换的次数，或在指定轮数后给出列表的状态。
7. Quick Sort Algorithm | 快速排序算法
Quick sort uses a divide-and-conquer strategy. A pivot element is selected (often the first or last item). The list is then partitioned into two sublists: elements smaller than the pivot and elements larger than (or equal to) the pivot. The sublists are recursively sorted. Concatenating the sorted sublists and the pivot yields the fully sorted list.
快速排序采用分治策略。选择一个枢轴元素（常为第一个或最后一个），然后将列表划分为两个子列表：小于枢轴的元素和大于（或等于）枢轴的元素。对这些子列表递归排序。最后将排序好的子列表和枢轴连接起来，得到完全排序的列表。
This algorithm appears in discrete mathematics units for both IB and OCR. You must be able to illustrate partitioning steps and correctly reassemble the list. The choice of pivot can affect performance; in the worst case, quick sort can degenerate to O(n²).
该算法出现在IB和OCR的离散数学单元中。你必须能够展示划分步骤并正确重组列表。枢轴的选择会影响性能；最坏情况下，快速排序可能变坏为 O(n²)。
8. Minimum Spanning Tree: Prim's Algorithm | 最小生成树：普里姆算法
For a connected, weighted, undirected graph, a minimum spanning tree (MST) connects all vertices with the minimal total edge weight. Prim's algorithm starts at an arbitrary vertex and grows the tree by repeatedly adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree, until all vertices are included.
对于一个连通加权无向图，最小生成树（MST）用边权重总和最小的方式连接所有顶点。普里姆算法从一个任意顶点开始，通过反复添加连接树内顶点和树外顶点的最便宜边来生长树，直到所有顶点都被包含。
步骤：1. 选择起点；2. 在所有连接已选顶点和未选顶点的边中，选择权重最小的边；3. 重复直到覆盖所有顶点。
Both IB AI HL and OCR Discrete Maths require Prim's algorithm, often presented in tabular or matrix form. You need to record the order in which edges are added and calculate the total weight. Common mistake: forgetting to consider only edges connecting the growing tree to unvisited vertices.
IB AI HL和OCR离散数学都要求掌握普里姆算法，常以表格或矩阵形式给出。你需要记录边被添加的顺序并计算总权重。常见错误：忘记只考虑连接生长中的树与未访问顶点的边。
9. Minimum Spanning Tree: Kruskal's Algorithm | 最小生成树：克鲁斯卡尔算法
Kruskal's algorithm builds the MST by sorting all edges by weight and adding them one by one, provided they do not create a cycle. A cycle is formed if both vertices of the edge are already in the same connected component. The process stops when (n−1) edges have been added for a graph with n vertices.
克鲁斯卡尔算法通过将所有边按权重排序，并逐一添加边来构建最小生成树，前提是不会形成回路。如果边的两个顶点已经在同一连通分量中，则会形成回路。对于有 n 个顶点的图，当已经添加了 n−1 条边时停止。
In exams you may be given a list of edges sorted by weight. You then list each edge and either accept or reject it, giving a reason. The algorithm is particularly exam-friendly for sparse graphs.
在考试中，你可能得到按权重排序的边列表。然后你需要列出每条边，并说明接受或拒绝，给出理由。该算法对于稀疏图特别适合考试。
10. Dijkstra's Shortest Path Algorithm | 迪杰斯特拉最短路径算法
Finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative edge weights. Working iteratively, it assigns temporary distance labels, sets final labels for the vertex with the smallest temporary label, and updates adjacent vertices. Box values or a table are used.
在具有非负边权的加权图中，找出从起始顶点到所有其他顶点的最短路径。它以迭代方式工作：分配临时距离标签，为具有最小临时标签的顶点设置最终标签，并更新相邻顶点。通常使用方框值或表格。
Key steps: ick the unvisited vertex with smallest distance; make it permanent. 3. For each neighbour, if new distance < current, update. 4. Repeat until all vertices are permanent.
关键步骤：1. 将起始顶点标为0，其他标为∞。2. 选取距离最小且未访问的顶点，将其设为永久。3. 对于每个邻居，如果新距离 < 当前距离，则更新。4. 重复直到所有顶点都是永久的。
This is a core network algorithm in IB AI (HL) and OCR Further Mathematics. You must be able to find the shortest path to a specific terminal and write the route by tracing back. The algorithm fails if any edge weight is negative.
这是IB AI（HL）和OCR进阶数学中的核心网络算法。你必须能够找到到特定终点的最短路径，并通过回溯写出路线。如果任何边权为负，算法将失败。
11. Critical Path Analysis (CPA) | 关键路径分析
CPA is used to schedule activities in a project. An activity network is drawn with vertices representing events and edges as activities. Forward scanning computes earliest start times (EST), and backward scanning gives latest start times (LST). The float is LST − EST. Activities with zero float form the critical path(s), which determine the minimum project completion time.
CPA用于调度项目中的活动。绘制活动网络，顶点代表事件，边代表活动。正向扫描计算最早开始时间（EST），反向扫描给出最迟开始时间（LST）。浮动时间为 LST − EST。浮动时间为零的活动构成关键路径，它决定了最短项目完成时间。
Both IB AI (HL) and OCR Discrete include CPA. You should be able to construct a precedence table, draw the network, perform forward and backward passes, and identify all critical activities. Care is needed when handling dummies—activities of zero duration that maintain logical dependencies.
IB AI（HL）和OCR离散都包含CPA。你应该能够构建先后关系表，绘制网络图，执行正向和反向传递，并识别所有关键活动。处理虚活动（持续时间为零、用于维持逻辑依赖）时需要小心。
12. Binary Search Algorithm | 二分查找算法
An efficient algorithm for locating a target value within a sorted list. It repeatedly divides the search interval in half. Compare the target with the middle element; if they are not equal, discard the half that cannot contain the target and continue on the remaining half until the target is found or the interval is empty.
一种在有序列表中定位目标值的高效算法。它反复将搜索区间对半分。将目标值与中间元素比较；若不相等，则丢弃不可能包含目标值的那一半，在剩余的一半上继续，直到找到目标或区间为空。
Example on [2, 5, 8, 12, 16, 23, 38], target 16:
search upper half [16,23,38]; middle 23: 16<23, search lower half [16]; middle 16 → found.
在 [2, 5, 8, 12, 16, 23, 38] 上查找目标 16 的例子：
中间索引4（值12）：16>12，搜索上半部分 [16,23,38]；中间值23：16<23，搜索下半部分 [16]；中间值16 → 找到。
Binary search features in OCR discrete algorithms and as an example of efficient search in IB computational thinking. You may need to trace the indices (low, high, mid) and state the maximum number of comparisons, which is ⌈log₂ n⌉.
二分查找出现在OCR离散算法中，并作为IB计算思维中高效搜索的一个例子。你可能需要追踪索引（low, high, mid），并说明最大比较次数，即⌈log₂ n⌉。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图