Edexcel Maths: Algorithms Revision Guide | Edexcel 数学：算法考点精讲

📚 Edexcel Maths: Algorithms Revision Guide | Edexcel 数学：算法考点精讲

Algorithms are the backbone of the Edexcel Decision Mathematics module. From sorting lists to finding the shortest path, mastering these step-by-step procedures is essential for achieving top marks. This guide breaks down every key algorithm in the syllabus, offering clear explanations, worked steps, and exam-ready tips to help you trace, apply, and analyse algorithms with confidence.

算法是 Edexcel 决策数学模块的核心。从排序列表到寻找最短路径，掌握这些逐步操作过程对于取得高分至关重要。本文拆解考纲中的每一个关键算法，提供清晰的解释、操作步骤和应试技巧，帮助你自信地追踪、应用和分析算法。

1. What is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of well-defined instructions used to solve a problem. In Edexcel Decision Maths, algorithms are often presented as a list of steps or as a flowchart. You will be expected to trace an algorithm’s execution using trace tables, understand its purpose, and identify the order of operations.

算法是用于解决问题的有限序列的明确定义的指令。在 Edexcel 决策数学中，算法通常以步骤列表或流程图的形式呈现。你需要使用追踪表来追踪算法的执行过程，理解其目的，并识别操作的顺序。

A trace table records the values of variables after each step. It is crucial for showing how an algorithm transforms input data into output. Common operations include assignment (e.g., A ← B), comparison, and conditional branching.

追踪表记录每一步后变量的值。它对于展示算法如何将输入数据转化为输出至关重要。常见操作包括赋值（如 A ← B）、比较和条件分支。

2. Sorting Algorithms: Bubble Sort | 排序算法：冒泡排序

Bubble sort repeatedly passes through a list, compares adjacent items, and swaps them if they are in the wrong order. The largest unsorted element ‘bubbles’ to its correct position at the end of each pass, so the number of comparisons can be reduced in later passes.

冒泡排序反复遍历列表，比较相邻项，如果顺序错误就交换它们。每一趟后，最大的未排序元素“冒泡”到其正确位置，因此后续趟的比较次数可以减少。

To trace bubble sort on paper, show each pass clearly. After a complete pass with no swaps, the list is sorted, and you may stop early. The worst-case number of comparisons is n(n-1)/2 for a list of size n.

在纸上追踪冒泡排序时，要清晰地展示每一趟。如果一趟中没有发生交换，则列表已排好序，可以提前停止。对于规模为 n 的列表，最坏情况比较次数为 n(n-1)/2。

Step 1: Start from the first element; compare with the next. If out of order, swap.

步骤 1：从第一个元素开始；与下一个比较。如果顺序错误，交换。
Step 2: Move right one position and repeat comparisons. Continue until the end of the list.

步骤 2：向右移一个位置，重复比较。一直进行到列表末尾。
Step 3: After completing a pass, ignore the last sorted elements and start a new pass from the beginning.

步骤 3：一趟完成后，忽略最后已排序的元素，从开头进行新的一趟。

3. Sorting Algorithms: Quick Sort | 排序算法：快速排序

Quick sort chooses a pivot element from the list, partitions the remaining items into two sublists (those less than the pivot and those greater than the pivot), then recursively sorts the sublists. In Edexcel, the pivot is typically the middle item of the current list.

快速排序从列表中选择一个枢轴元素，将剩余项划分为两个子列表（小于枢轴的和大于枢轴的），然后递归地对子列表排序。在 Edexcel 中，枢轴通常取当前列表的中间项。

When tracing quick sort, write the pivot above the list, then write the two new sublists on separate lines below, maintaining the original relative order of items within each sublist. Reapply the process until all sublists contain one element, then reassemble the list.

追踪快速排序时，将枢轴写在列表上方，然后在下方用单独的行写出两个新的子列表，保持每个子列表中各项在原来列表中的相对顺序。重复此过程直到所有子列表只含一个元素，然后重新组合列表。

Pick the middle element as pivot. Underline or circle it.

选取中间元素作为枢轴。在其下方划线或画圈。
For each other element, if it is less than the pivot, place it in the left sublist; if greater, place it in the right sublist.

对于每个其他元素，如果小于枢轴就放入左子列表，如果大于则放入右子列表。
If an element equals the pivot, Edexcel convention places it in the left sublist (or follow your question’s instructions).

如果某元素等于枢轴，Edexcel 惯例将其放入左子列表（或遵照题目说明）。
Repeat the process on each sublist. Stop when all sublists have length 1.

对每个子列表重复此过程。当所有子列表长度为1时停止。

4. Bin Packing Algorithms | 装箱算法

Bin packing problems require packing a set of items of given sizes into bins of a fixed capacity, aiming to use as few bins as possible. Edexcel expects you to apply the first-fit, first-fit decreasing, and full-bin packing algorithms and to compare their efficiency.

装箱问题要求将给定大小的一组物品装入固定容量的箱子，目标是使用尽可能少的箱子。Edexcel 要求你应用首次适应、首次适应递减和整箱装箱算法，并比较它们的效率。

First-fit works online: take items in the order given; place each item into the first bin that has enough remaining space. If no bin can accommodate it, open a new bin. First-fit decreasing sorts the items into descending order first, then applies first-fit; it usually produces a better packing but requires the full list in advance.

首次适应算法在线工作：按给定顺序取物品；将每个物品放入第一个有足够剩余空间的箱子。如果没有箱子能容纳，就打开一个新箱子。首次适应递减算法先将物品按从大到小排序，然后应用首次适应；它通常能得到更好的装箱方案，但需要提前拿到完整列表。

Full-bin packing is an offline heuristic: you look for combinations of items that exactly fill a bin, pack those first, then use first-fit for the remaining items. This often leads to a near-optimal solution.

整箱装箱是一种离线启发式算法：寻找恰好装满满箱的物品组合，先装这些，然后用首次适应处理剩余物品。这通常能得到接近最优的解。

5. Graph Terminology | 图论术语

Before applying graph algorithms, you must be comfortable with key terms. A graph consists of vertices (nodes) connected by edges (arcs). A weighted graph has a number (weight) associated with each edge, representing distance, cost, or time. A directed graph (digraph) has edges with a direction.

在应用图算法之前，你必须熟悉关键术语。图由顶点（节点）通过边（弧）连接而成。加权图的每条边有一个数字（权值），表示距离、成本或时间。有向图（digraph）的边具有方向。

A path is a sequence of edges connecting one vertex to another without repeating vertices. A cycle is a closed path. A tree is a connected graph with no cycles, and a spanning tree of a graph connects all vertices with exactly n-1 edges. A minimum spanning tree (MST) has the smallest total weight.

路径是不重复顶点、连接两个顶点的边的序列。回路是闭合的路径。树是没有回路的连通图，图的生成树用恰好 n-1 条边连接所有顶点。最小生成树（MST）的总权值最小。

6. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal算法

Kruskal’s algorithm builds a minimum spanning tree by considering edges in ascending order of weight. You sort all edges by weight, then add the next smallest edge to the tree unless it would create a cycle. Continue until all vertices are connected (n-1 edges for n vertices).

Kruskal 算法按权值升序考虑边，从而构建最小生成树。将所有边按权值排序，然后加入下一条最小的边，除非加入后会形成回路。一直进行到所有顶点都被连通（n 个顶点需要 n-1 条边）。

In the exam, list the sorted edges in a table. Show which edges are added and which are rejected (because they form a cycle). Draw the resulting tree or state its total weight. Kruskal is particularly effective when the graph is sparse.

考试时，在一个表格中列出排序好的边。显示哪些边被添加、哪些边被拒绝（因为形成回路）。画出最终的树或写出其总权值。当图稀疏时，Kruskal 算法特别有效。

Sort all edges by increasing weight. If two edges have the same weight, either may be chosen first unless the question specifies a rule.

按权值递增顺序将所有边排序。如果两条边权值相同，可任选其一，除非题目规定规则。
Select the edge with the least weight. Add it to the tree.

选择权值最小的边。将其加入树中。
Select the next edge. If adding it connects two vertices that are already in the same component (cycle), reject it. Otherwise, add it.

选择下一条边。如果加入它会使两个已经在同一连通分量中的顶点相连（形成回路），拒绝它。否则，加入它。
Repeat until you have included exactly n-1 edges.

重复直到恰好包含 n-1 条边。

7. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim算法

Prim’s algorithm builds an MST by starting at any vertex and growing the tree one edge at a time. At each step, choose the edge of minimum weight that connects a vertex already in the tree to a vertex not yet in the tree. The choice of starting vertex is arbitrary but can affect early selections.

Prim 算法通过从任意顶点开始并一次增长一条边来构建 MST。每一步，选择连接已在树中的顶点与尚未在树中的顶点的权值最小的边。起始顶点可任意选择，但可能影响早期选择。

Edexcel questions often present the graph as a distance matrix and require you to apply Prim’s algorithm on the matrix. Here you start from a chosen row, find the smallest entry in that row (ignoring zeros/used columns), join the corresponding vertex, then consider all edges from the current tree to new vertices.

Edexcel 的考题常以距离矩阵形式给出图，并要求在矩阵上应用 Prim 算法。你从所选的行开始，在该行中找到最小值（忽略零/已用列），连接对应的顶点，然后考虑从当前树到新顶点的所有边。

On a network: start at any vertex. List the edges incident to the start vertex and choose the smallest weight to join a new vertex.

在网络图上：从任意顶点开始。列出与起始顶点相连的边，选择最小权值以连接一个新顶点。
Update the list of candidate edges: now include all edges from any vertex already in the tree to vertices not yet in the tree.

更新候选边列表：现在包括所有从已在树中的顶点到尚未在树中的顶点的边。
Choose the smallest candidate edge without creating a cycle. Add the new vertex to the tree.

选择不形成回路的最小候选边。将新顶点加入树中。
On a matrix: delete the row of the chosen vertex; label its column. At each step, look at the labelled columns to find the smallest entry among the remaining rows.

在矩阵上：删除已选顶点的行；标记其列。每一步，查看已标记列，在剩余行中找到最小项。

8. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra算法

Dijkstra’s algorithm finds the shortest path from a designated start vertex to all other vertices in a non-negative weighted graph. It works by assigning temporary labels (working distances) to vertices, permanently fixing the smallest label, and updating its neighbours.

Dijkstra 算法寻找从一个指定起始顶点到非负加权图中所有其他顶点的最短路径。它通过给顶点分配临时标号（工作距离）、永久固定最小的标号并更新其邻居来工作。

You must box the permanent label and write the order of permanence. When updating a neighbour, if a shorter distance is found through the newly fixed vertex, change the temporary label and record the new predecessor vertex. At the end, you can trace back from the destination to find the route.

你必须给永久标号画上方框，并写出永久化的顺序。更新邻居时，如果通过新固定的顶点找到了更短的距离，就更改临时标号并记录新的前驱顶点。最后，你可以从终点回溯找到路径。

Step 0: Give the start vertex a permanent label 0. All other vertices get a temporary label ∞ (infinity).

第 0 步：给起始顶点永久标号 0。所有其他顶点获得临时标号 ∞（无穷大）。
Step 1: From the most recently fixed vertex, consider all directly connected unlabelled vertices. Calculate (weight from fixed vertex + its permanent label). If smaller than current temporary label, update it and note the predecessor.

第 1 步：从最近固定的顶点出发，考虑所有直接相连且未标号的顶点。计算（来自固定顶点的权值 + 其永久标号）。若比当前临时标号小，则更新并记录前驱。
Step 2: Among all temporary labels, choose the smallest and make it permanent. This vertex is now fixed. Repeat from Step 1 until the destination vertex is permanently labelled.

第 2 步：在所有临时标号中，选择最小的并将其永久化。该顶点现已固定。从第 1 步重复，直至目标顶点获得永久标号。

9. Route Inspection Problem | 路线检查问题

The route inspection (or Chinese postman) problem seeks the shortest closed walk that traverses every edge at least once. If the graph is Eulerian (all vertices even), an Eulerian circuit exists and all edges need be traversed exactly once. If not, you must pair up odd vertices by adding repeats of shortest paths between them to minimise total weight.

路线检查（中国邮递员）问题寻求至少遍历每条边一次的最短闭合路径。如果图是欧拉图（所有顶点为偶度），则存在欧拉回路，每条边恰好遍历一次。如果不是，则必须通过添加奇度顶点之间的最短路径的重复边来两两配对奇顶点，以最小化总权值。

The algorithm: (1) Identify all odd-degree vertices. (2) List all possible pairings of these vertices and find the shortest path distance for each pair. (3) For each complete pairing, sum the shortest path distances; choose the pairing that gives the smallest total. (4) Duplicate these paths on the network to make all vertices even, then find an Eulerian trail.

算法步骤：(1) 找出所有奇度顶点。(2) 列出这些顶点的所有可能配对，并找出每对的最短路径距离。(3) 对于每种完整配对，将最短路径距离求和；选择总和最小的配对。(4) 在网络中重复这些路径，使所有顶点变为偶度，然后寻找欧拉路径。

10. Critical Path Analysis Basics | 关键路径分析基础

Critical path analysis helps schedule complex projects. An activity-on-arc (AoA) network represents activities as directed edges with durations, and events (nodes) mark the start/finish of activities. Dependencies must be respected. The critical path is the longest path through the network; any delay here delays the whole project.

关键路径分析有助于调度复杂项目。活动在弧上（AoA）网络将活动表示为带持续时间的有向边，事件（节点）表示活动的开始/完成。必须遵守依赖关系。关键路径是穿过网络的最长路径；任何此处的延迟都会拖慢整个项目。

Forward pass calculates the earliest start time (EST) for each event; backward pass gives the latest start time (LST). Float is LST – EST; critical activities have zero float. For an activity, you also find earliest finish time (EFT) and latest finish time (LFT).

前推法计算每个事件的最早开始时间（EST）；后推法给出最晚开始时间（LST）。浮动时间为 LST – EST；关键活动具有零浮动时间。对于一项活动，还要找最早完成时间（EFT）和最晚完成时间（LFT）。

11. Linear Programming: Graphical Method | 线性规划：图解法

Decision 1 includes formulating and solving linear programming problems with two decision variables using graphs. Define variables, write the objective function and constraints as inequalities, plot them to form the feasible region, and determine the optimal solution by sliding the objective line or checking vertices.

决策数学 1 包含使用图形法表述并求解具有两个决策变量的线性规划问题。定义变量，将目标函数和约束条件写成不等式，通过绘制它们形成可行域，并通过滑动目标函数直线或检查顶点来确定最优解。

Use a ruler to draw straight lines corresponding to each constraint. Shade or clearly indicate the unwanted region (Edexcel often uses shading out). The feasible region is the unshaded area allowing integer or continuous solutions. Integer solutions require testing all lattice points near the vertex that gives the optimal continuous solution.

使用直尺画出每条约束对应的直线。对不可行区域进行阴影或明确指示（Edexcel 常使用对外阴影）。可行域是允许整数或连续解的无阴影区域。整数解需要测试最优连续解顶点附近的所有格点。

12. Algorithmic Complexity and Tracing | 算法复杂度与追踪表

Exam questions often ask you to trace an algorithm presented as a structured text, processing an input and producing output. You must complete a trace table showing the step-by-step change of variables, evaluate loops, and follow conditional statements precisely. Efficiency is measured by the number of comparisons or operations.

考题常要求你追踪以结构化文本形式给出的算法，处理输入并生成输出。你必须完成追踪表，显示变量的逐步变化，评估循环，并精确遵循条件语句。效率通过比较次数或操作次数来衡量。

Understanding the order of an algorithm (e.g., bubble sort’s O(n²)) is not always tested numerically, but you should recognise that, for example, quick sort generally performs fewer comparisons than bubble sort on large, unordered lists. Tracing ensures deep understanding of algorithmic logic.

理解算法的数量级（例如冒泡排序的 O(n²)）虽不总以数值方式考查，但你应认识到，例如快速排序在大型无序列表上通常比冒泡排序执行更少的比较。追踪确保对算法逻辑的深度理解。

When tracing, write values cleanly in columns. If an algorithm contains a WHILE loop, check the condition carefully at each iteration. For recursive algorithms like quick sort, use indentation to show recursive depth and keep track of subproblems.

追踪时，要在各列中清晰地记录值。如果算法包含 WHILE 循环，每次迭代仔细检查条件。对于快速排序等递归算法，使用缩进显示递归深度，并跟踪子问题。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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

Edexcel Maths: Algorithms Revision Guide | Edexcel 数学：算法 考点精讲