Algorithm Essentials for CIE A-Level Mathematics | CIE A-Level 数学：算法考点精讲

📚 Algorithm Essentials for CIE A-Level Mathematics | CIE A-Level 数学：算法考点精讲

An algorithm is a finite sequence of well-defined, computer-implementable instructions, typically used to solve a class of problems or to perform a computation. In CIE A-Level Mathematics, ‘algorithm’ spans both numerical methods for solving equations and the step‑by‑step procedures found in Decision Mathematics, such as sorting, graph searching, and network optimisation. This revision guide distils the core algorithmic concepts you will encounter in your syllabus, complete with worked insights and exam‑ready strategies.

算法是一组有限且明确、可由计算机执行的指令序列，通常用于解决某一类问题或完成计算。在 CIE A-Level 数学中，“算法”既包含用于解方程的数值方法，也涵盖决策数学中的逐步操作流程，例如排序、图搜索和网络优化。本考点精讲提炼了你在考纲中将要接触的核心算法概念，并配有详细的解析和应试策略。

1. What Is an Algorithm and Why Does It Matter? | 什么是算法，它为何重要？

In mathematics, an algorithm is a precise set of rules that guarantees a solution when followed correctly. For the A-Level exam, you need to be able to trace, apply, and sometimes modify algorithms presented as flowcharts, pseudocode, or written instructions. Understanding algorithms enhances logical reasoning and is essential for topics like numerical solutions, critical path analysis, and sorting networks.

在数学中，算法是一套精确的规则，只要正确遵循就能得出确定解。备考A-Level时，你需要能追踪、应用甚至修改以流程图、伪代码或文字说明给出的算法。理解算法能提升逻辑推理能力，对数值求解、关键路径分析和排序网络等专题至关重要。

2. Bisection Method | 二分法

The bisection method is a root‑finding algorithm that repeatedly halves an interval to locate a solution to f(x)=0, provided f(x) is continuous and changes sign over [a, b]. At each step, compute the midpoint c = (a+b)/2; if f(c) has the same sign as f(a), replace a with c, otherwise replace b with c. The process continues until the interval width is less than the required tolerance.

二分法是一种求根算法，通过不断将区间对半分，来定位 f(x)=0 的解，前提是函数在 [a, b] 上连续且异号。每一步计算中点 c = (a+b)/2；若 f(c) 与 f(a) 同号，则用 c 替换 a，否则用 c 替换 b。重复此过程，直至区间宽度小于要求的容差。

Enables systematic bracketing of a root even when the function is not differentiable.
即使函数不可导，也能系统地将根括在区间里。
Linear convergence; simple to implement but slower than Newton‑Raphson.
线性收敛；实现简单，但比牛顿-拉夫森法慢。
Always works for a continuous sign change: robust and predictable.
只要连续函数变号就总能工作：稳健且可预测。

cₙ = (aₙ + bₙ)/2, stop when bₙ – aₙ < tolerance

cₙ = (aₙ + bₙ)/2，当 bₙ – aₙ < 容差时停止

3. Newton‑Raphson Method | 牛顿-拉夫森法

The Newton‑Raphson method uses the derivative to approximate a root iteratively: xₙ₊₁ = xₙ – f(xₙ)/f'(xₙ). Begin with an initial guess x₀, then generate successively better approximations. The method converges quadratically near a simple root, making it extremely efficient when a suitable starting point is chosen.

牛顿-拉夫森法利用导数迭代地逼近根：xₙ₊₁ = xₙ – f(xₙ)/f'(xₙ)。从初始猜测 x₀ 开始，逐步产生更好的近似值。该法在单根附近具有二次收敛性，只要选取了合适的起点，效率极高。

Requires the derivative f'(x) to exist and be non‑zero near the root.
要求导数 f'(x) 存在且在根附近非零。
Quadratic convergence means the number of correct digits roughly doubles each step.
二次收敛意味着每一步正确数字位数大致翻倍。
Can fail if f'(x) is very small or the guess is far from the root; always check convergence.
若 f'(x) 非常小或猜测值远离根，则可能失败；答题时务必检查收敛性。

xₙ₊₁ = xₙ − f(xₙ)/f'(xₙ)

4. Fixed‑Point Iteration | 不动点迭代

Rewrite f(x)=0 as x = g(x). Starting from x₀, compute xₙ₊₁ = g(xₙ). The iteration converges to a root if |g'(x)| < 1 near the fixed point. This algorithm is often examined by asking you to rearrange an equation into a suitable iterative form and to demonstrate whether a given iteration will converge.

将 f(x)=0 改写为 x = g(x)。从 x₀ 出发，计算 xₙ₊₁ = g(xₙ)。如果不动点附近有 |g'(x)| < 1，则迭代收敛到根。考题常要求把方程变形为合适的迭代形式，并说明所给迭代是否会收敛。

Different rearrangements lead to different convergence behaviour; choose g(x) wisely.
不同的变形导致不同的收敛行为；应明智选择 g(x)。
Use a cobweb or staircase diagram to visualise convergence or divergence.
可用蛛网图或阶梯图直观显示收敛或发散。
If |g'(α)| ≥ 1, the iteration generally diverges from the root α.
若 |g'(α)| ≥ 1，迭代通常会离开根 α 发散。

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

Bubble sort repeatedly steps through a list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating the list is sorted. In Decision Mathematics you may be asked to track the number of comparisons and swaps or to state the list after each pass.

冒泡排序反复遍历列表，比较相邻元素并在顺序错误时交换它们。持续进行遍历，直到某次遍历无需任何交换，表明列表已排序。在决策数学中，你可能需要记录比较和交换的次数，或者写出每次遍历后的列表。

Original: 5, 3, 8, 1

Pass 1: (3,5,8,1) → (3,5,8,1) → (3,5,1,8)

Pass 2: (3,5,1,8) → (3,1,5,8)

Pass 3: (3,1,5,8) → (1,3,5,8) – sorted

Original: 5, 3, 8, 1 → after passes becomes sorted: 1, 3, 5, 8. Bubble sort has O(n²) average and worst‑case time complexity but is easy to implement.

原列表 5, 3, 8, 1 → 多次遍历后变为已排序：1, 3, 5, 8。冒泡排序平均和最坏时间复杂度均为 O(n²)，但实现简单。

6. Quick Sort Algorithm | 快速排序算法

Quick sort selects a pivot element and partitions the list into two sub‑lists: elements less than the pivot and elements greater than the pivot. It recursively sorts the sub‑lists. CIE exam questions often provide the pivot choice rule (e.g. first element or median of three) and require you to show each stage of partitioning.

快速排序选择一个基准元素，将列表分为两个子列表：小于基准的元素和大于基准的元素。然后递归地对子列表排序。CIE 试题通常会给出基准选择规则（例如第一个元素或三数取中值），并要求展示每次分区的过程。

Efficient on average: O(n log n) comparisons; worst case O(n²) with poor pivot selection.
平均效率高：O(n log n) 次比较；基准选择不当则最坏情况 O(n²)。
In‑place quick sort uses indices; show sub‑lists clearly in workings.
原地快速排序使用下标；演算时需清楚标出子列表。

Example: sort [9, 4, 7, 2, 8] with pivot first element 9 → left sub‑list [4,7,2,8], right empty → continue recursively.

示例：排序 [9, 4, 7, 2, 8]，基准取第一个元素 9 → 左子列表 [4,7,2,8]，右子空 → 继续递归。

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

Kruskal’s algorithm builds a minimum spanning tree by selecting edges in order of increasing weight, rejecting any edge that would form a cycle. List all edges sorted by weight, then add the next smallest edge that does not create a cycle until n–1 edges are selected (for a network with n vertices).

克鲁斯卡尔算法通过按权重递增的顺序选择边来构建最小生成树，拒绝任何会形成环的边。列出所有边并按权重排序，然后挑选下一条不产生环的最短边，直到选出 n–1 条边（对于有 n 个顶点的网络）。

Edge	Weight
A-B	3
B-C	4
C-D	5

Apply Kruskal: choose A‑B (3), then B‑C (4), then C‑D (5) — all added without cycle. Total weight = 12. Always draw the resulting tree in your answer.

应用克鲁斯卡尔：选 A‑B (3)，再选 B‑C (4)，接着 C‑D (5) — 均无环加入。总权重 = 12。作答时务必画出生成的树。

8. Prim’s Algorithm | 普里姆算法

Prim’s algorithm grows a minimum spanning tree from a starting vertex by repeatedly adding the cheapest available edge that connects a visited vertex to an unvisited one. You can use a matrix or graphical approach; exam questions often provide a distance matrix and require ordered edge selection.

普里姆算法从起始顶点出发逐步构建最小生成树，反复添加连接已访问顶点和未访问顶点的最便宜可用边。既可用矩阵法也可用图形法；试题常提供距离矩阵，并要求按顺序选择边。

Start at any vertex, mark it as visited. In each stage, scan all edges from visited vertices to unvisited vertices and choose the one with least weight.
从任意顶点开始，标记为已访问。每一阶段扫描所有从已访问顶点到未访问顶点的边，并选择权重最小的一条。
Continue until all vertices are visited; the chosen edges form the minimum spanning tree.
继续直至所有顶点均被访问；选出的边构成最小生成树。

Always state the order of edge selection and the cumulative weight clearly.

务必清晰陈述边的选择顺序和累计权重。

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

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non‑negative weights. Each node gets a temporary label giving the distance from the start; once the minimum temporary label is finalised, update the distances of its neighbours. The process repeats until the destination is reached.

迪杰斯特拉算法在所有权重非负的图中找出从源节点到其他所有节点的最短路径。每个节点获得一个表示距离起点的临时标号；一旦最小的临时标号被固定，便更新其邻居的距离。重复此过程，直到到达目标。

Use a table showing node, shortest distance (working value), and previous node; cross out values as they become permanent.
使用表格，列出节点、最短距离（工作值）和前驱节点；值一旦固定便划去原有临时值。
For exam, you must present the full working table and then trace the shortest path backward using previous node entries.
考试中必须展示完整的工作表，然后利用前驱节点反向追踪最短路径。
Ensure all permanent labels are clearly indicated; final answer: path and its length.
确保所有固定标号标注清楚；最终答案：路径及其长度。

10. Critical Path Analysis (Forward and Backward Pass) | 关键路径分析（前推与后推法）

Critical path analysis determines the minimum project completion time and identifies activities that cannot be delayed without affecting the overall duration. The forward pass calculates the earliest start time (EST) and earliest finish time (EFT) for each activity; the backward pass yields the latest finish time (LFT) and latest start time (LST). Activities with zero total float lie on the critical path.

关键路径分析确定最小项目完工时间，并找出不会影响总工期而无法延迟的活动。前推法计算每个活动的最早开始时间和最早结束时间；后推法则给出最晚结束时间和最晚开始时间。总时差为零的活动位于关键路径上。

Construct an activity‑on‑node or activity‑on‑arc diagram following precedence constraints.
根据紧前关系构建节点图或箭线图。
Forward pass: EST of start node = 0; EFT = EST + duration; for merge nodes, EST = max(EFT of predecessors).
前推法：开始节点的 EST = 0；EFT = EST + 工期；汇合节点的 EST 取各前驱 EFT 的最大值。
Backward pass: from end node, LFT = project duration; LST = LFT − duration; for burst nodes, LFT = min(LST of successors).
后推法：从终点开始，LFT = 项目工期；LST = LFT − 工期；分支节点的 LFT 取各后继 LST 的最小值。
Float = LST − EST; critical activities have float = 0.
时差 = LST − EST；关键活动时差为 0。

11. First‑Fit and First‑Fit Decreasing Bin Packing | 首次适应与降序首次适应装箱算法

Bin‑packing algorithms deal with packing objects of given sizes into bins of fixed capacity. First‑fit places each object into the first bin where it fits. First‑fit decreasing sorts objects in descending order before applying first‑fit, often yielding a better (but not necessarily optimal) packing. These are heuristic algorithms; questions typically ask you to apply them to a list and to comment on the number of bins used.

装箱算法处理将给定大小的物品装入固定容量箱中的问题。首次适应法将每件物品放入第一个能够容纳的箱子。降序首次适应法先将物品降序排列再使用首次适应，通常能得到较好（但不一定最优）的装箱方案。两者皆为启发式算法；考题通常要求对列表应用算法并评论所用箱子数。

Clearly show bins as they fill; label each bin with its contents and remaining capacity.
随着箱子被填满，清晰地展示；标注每个箱子的内含物和剩余容量。
First‑fit decreasing can waste less space; understand why ordering matters.
降序首次适应可减少空间浪费；理解顺序为何有影响。
Be prepared to compare results with an optimal pack or comment on the heuristic’s performance.
准备与最优装箱结果作比较，或评论启发式算法的表现。

12. Algorithmic Thinking and Exam Tips | 算法思维与应试技巧

When faced with an unfamiliar algorithm in the exam, trace it carefully using a table or a systematic listing. Always show your steps: examiners allocate marks for process, not just final answers. For numerical methods, check convergence criteria; for graph algorithms, draw clear diagrams; for sorting, record intermediate passes. Time management is crucial — if you get stuck, move on and return later.

在考场上遇到不熟悉的算法时，借助表格或系统的列表仔细追踪其过程。务必展示步骤：考官给分看重过程，而非仅仅是最终答案。数值方法要检查收敛条件；图论算法要画出清晰图示；排序要记录中间遍历结果。时间管理至关重要——若卡住就先跳过，稍后回来继续。

Memorise key pseudo‑codes, like the bisection interval update rule or the Dijkstra label setting procedure.
记住关键伪代码，例如二分法区间更新规则或迪杰斯特拉标号设定程序。
Practice by writing out each algorithm on paper without a calculator; this builds speed and accuracy.
在不使用计算器的情况下纸上写出各算法进行练习；这能提升速度和准确度。
Use bullet points or small tables for clarity; label everything explicitly.
为清晰起见使用要点或小表格；对所有内容明确标注。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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

Algorithm Essentials for CIE A-Level Mathematics | CIE A-Level 数学：算法考点精讲