📚 Algorithms for A-Level OCR Mathematics | A-Level OCR 数学：算法 考点精讲
In the OCR A-Level Mathematics specification, the Decision Mathematics module places algorithms at the core of problem-solving. Algorithms are step-by-step procedures designed to perform a specific task, and you will be expected to understand, apply, and trace them through a variety of contexts. Mastering these systematic methods is key to success in the examination, where questions frequently require you to execute algorithms efficiently, calculate the number of comparisons or swaps, and interpret their output.
在OCR A-Level数学大纲中，决策数学模块将算法置于问题解决的核心地位。算法是为完成特定任务而设计的分步过程，你需要理解、应用并在各种情境下跟踪它们。掌握这些系统方法是成功通过考试的关键，考题经常要求你高效执行算法、计算比较或交换的次数，并解释输出结果。
1. Understanding Algorithms | 理解算法
An algorithm is a finite sequence of well-defined instructions that takes an input, processes it, and produces an output. All algorithms must possess five essential properties: finiteness, definiteness (unambiguous steps), input, output, and effectiveness. When designing or tracing an algorithm, you must ensure that each step is clearly defined and that the process always terminates after a finite number of operations.
算法是一个定义明确的有限指令序列，接收输入、处理并产生输出。所有算法必须具备五个基本性质：有限性、确定性（无歧义的步骤）、输入、输出和有效性。在设计或跟踪算法时，你必须确保每个步骤都被清晰定义，并且过程总是在有限次操作后终止。
In examinations, algorithms are often presented as flowcharts, structured English, or pseudocode. You may be asked to follow a given algorithm with sample data, identify the purpose of an unfamiliar algorithm, or modify an existing algorithm to handle a slightly different problem. A deep understanding of the underlying logic helps you to avoid common pitfalls and to trace the state of variables accurately at each iteration.
在考试中，算法通常以流程图、结构化英语或伪代码的形式呈现。你可能会被要求用样本数据执行一个给定的算法、识别一个陌生算法的目的，或者修改现有算法以处理稍有不同的问题。对底层逻辑的深刻理解有助于你避免常见陷阱，并在每次迭代中准确跟踪变量的状态。
2. Bubble Sort Algorithm | 冒泡排序算法
The bubble sort algorithm works by repeatedly making passes through a list, comparing adjacent pairs of items, and swapping them if they are in the wrong order. The largest unsorted element ‘bubbles’ to its correct position at the end of the list during each pass. This process continues until a complete pass is made without any swaps, indicating that the list is fully sorted.
冒泡排序算法通过反复遍历列表、比较相邻元素并在顺序错误时交换它们来工作。每一趟遍历中，最大的未排序元素会“冒泡”到列表末尾的正确位置。该过程持续进行，直到某趟遍历中没有发生任何交换，表明列表已完全排序。
Example: sort the list [6, 3, 8, 1, 4]. Pass 1: compare 6 and 3 → swap → [3,6,8,1,4]; compare 6 and 8 → no swap; compare 8 and 1 → swap → [3,6,1,8,4]; compare 8 and 4 → swap → [3,6,1,4,8]. Pass 2: compare 3 and 6 → no swap; compare 6 and 1 → swap → [3,1,6,4,8]; compare 6 and 4 → swap → [3,1,4,6,8]. Pass 3: compare 3 and 1 → swap → [1,3,4,6,8]; compare 3 and 4 → no swap; no swaps from here onward; the algorithm stops after Pass 4 confirming no swaps.
示例：对列表 [6,3,8,1,4] 排序。第一趟：比较6和3 → 交换 → [3,6,8,1,4]；比较6和8 → 不交换；比较8和1 → 交换 → [3,6,1,8,4]；比较8和4 → 交换 → [3,6,1,4,8]。第二趟：比较3和6 → 不交换；比较6和1 → 交换 → [3,1,6,4,8]；比较6和4 → 交换 → [3,1,4,6,8]。第三趟：比较3和1 → 交换 → [1,3,4,6,8]；比较3和4 → 不交换；此后无交换，算法在第四趟确认无交换后停止。
The maximum number of comparisons for a list of length n is ½ n(n−1). For n=5, this is 10 comparisons in the worst case. The number of swaps is at most ½ n(n−1) as well, occurring when the list is in reverse order. You should be able to count the exact number of comparisons and swaps performed on a given list, as this is a common exam requirement.
对于长度为n的列表，最大比较次数为½ n(n−1)。当n=5时，最坏情况为10次比较。交换次数最多也是½ n(n−1)，发生在列表完全逆序时。你应该能计算在给定列表上执行的确切比较次数和交换次数，这是常见的考试要求。
3. Shuttle Sort Algorithm | 穿梭排序算法
The shuttle sort algorithm, often likened to insertion sort, builds a sorted sublist at the left of the original list. Starting with the second item, it repeatedly shuttles it leftwards by swapping with the preceding item until it reaches its correct position among the already sorted elements. This is repeated for each subsequent item until the whole list is ordered.
穿梭排序算法通常被比作插入排序，它在原始列表左侧构建一个已排序的子列表。从第二项开始，它反复与前面的项交换，向左“穿梭”，直到在已排序元素中到达其正确位置。对每个后续项重复此过程，直到整个列表有序。
Using the same list [6,3,8,1,4]: start with 6 as the sorted sublist. Take 3: compare 3 and 6 → swap → [3,6,8,1,4]. Take 8: it is greater than 6, so no swaps → [3,6,8,1,4]. Take 1: compare with 8 → swap → [3,6,1,8,4]; compare with 6 → swap → [3,1,6,8,4]; compare with 3 → swap → [1,3,6,8,4]. Take 4: compare with 8 → swap → [1,3,6,4,8]; compare with 6 → swap → [1,3,4,6,8]; compare with 3 → no swap. The list is sorted.
使用同一列表 [6,3,8,1,4]：以6作为已排序子列表开始。取出3：比较3和6 → 交换 → [3,6,8,1,4]。取出8：它大于6，因此不交换 → [3,6,8,1,4]。取出1：与8比较 → 交换 → [3,6,1,8,4]；与6比较 → 交换 → [3,1,6,8,4]；与3比较 → 交换 → [1,3,6,8,4]。取出4：与8比较 → 交换 → [1,3,6,4,8]；与6比较 → 交换 → [1,3,4,6,8]；与3比较 → 不交换。列表排序完成。
In the worst case, shuttle sort also requires about ½ n(n−1) comparisons and swaps. However, it performs fewer comparisons on average on partially sorted data than bubble sort. In OCR exam questions, you must be careful to count each comparison and swap exactly as the algorithm would, following the shuttle back to the left until no swap is needed or the start is reached.
在最坏情况下，穿梭排序同样需要约½ n(n−1)次比较和交换。然而，在部分有序的数据上，它的平均比较次数比冒泡排序少。在OCR考题中，你必须严格按照算法的步骤，仔细计算每次比较和交换，跟随元素向左穿梭，直到无需交换或到达列表开头。
4. Binary Search Algorithm | 二分查找算法
Binary search is a highly efficient algorithm for finding the position of a target value within a sorted list. It repeatedly divides the search interval in half. If the target value equals the middle element, the search is successful. If the target is less than the middle element, the left half is searched; if greater, the right half is searched. This logarithmic time complexity makes it far superior to linear search for large lists.
二分查找是一种在有序列表中查找目标值位置的高效算法。它反复将搜索区间对半分。如果目标值等于中间元素，则搜索成功。如果目标值小于中间元素，则搜索左半部分；如果大于，则搜索右半部分。这种对数时间复杂度使其在大列表上远优于线性查找。
Example: find 17 in the sorted list [2, 5, 9, 13, 17, 21, 30]. The middle of indices 1 to 7 is 4 (value 13). Since 17 > 13, search right sublist [17,21,30]. The new middle is index 6 (value 21). Now 17 < 21, search left sublist [17]. Middle is index 5, value 17, so target found in 3 comparisons. If the target is not present, the algorithm terminates when the interval becomes empty.
示例：在有序列表 [2,5,9,13,17,21,30] 中查找17。索引1到7的中间是4（值13）。由于17 > 13，搜索右子列表 [17,21,30]。新中间是索引6（值21）。此时17 < 21，搜索左子列表 [17]。中间为索引5，值17，因此在3次比较后找到目标。如果目标不存在，算法会在区间变空时终止。
The maximum number of comparisons is ⌈log₂ n⌉ + 1 for a list of size n (depending on implementation), which is roughly the ceiling of the binary logarithm plus one comparison for the equality check. You must be able to carry out binary search and state the number of comparisons made. Occasionally you might need to list the probes in order, showing how the algorithm homes in on the target.
对于大小为n的列表，最大比较次数为⌈log₂ n⌉ + 1（取决于实现），约为以2为底的对数向上取整再加一次相等性比较。你必须能够执行二分查找并列出比较次数。有时你可能需要按顺序列出探测点，展示算法如何逐渐逼近目标。
5. Bin Packing Algorithms: First‑fit and First‑fit Decreasing | 装箱算法：首次适应与递减首次适应
Bin packing problems involve placing items of given sizes into bins of fixed capacity, aiming to minimise the number of bins used. The first-fit algorithm processes items in the order they are given, placing each item into the first bin that has enough remaining capacity. If no existing bin can accommodate the item, a new bin is started.
装箱问题涉及将给定大小的物品放入固定容量的箱子中，目标是使所用箱子数量最少。首次适应算法按给出的顺序处理物品，将每件物品放入第一个有足够剩余容量的箱子。如果没有现有箱子能容纳该物品，则开始一个新箱子。
Example: bin capacity = 10, items: 5, 7, 3, 4, 2. First-fit: item 5 goes to Bin1 (5); item 7 goes to Bin2 (7); item 3 fits into Bin1 (5+3=8); item 4 does not fit Bin1 (8+4>10), does not fit Bin2 (7+4>10), so new Bin3 (4); item 2 fits Bin1 (8+2=10). Bins used: 3.
示例：箱子容量=10，物品：5, 7, 3, 4, 2。首次适应：物品5放入箱1 (5)；物品7放入箱2 (7)；物品3可放入箱1 (5+3=8)；物品4不能放入箱1 (8+4>10)，也不能放入箱2 (7+4>10)，故新箱3 (4)；物品2放入箱1 (8+2=10)。使用箱子数：3。
The first-fit decreasing algorithm improves upon first-fit by first sorting items into non-increasing order of size. This often yields a better (i.e. fewer bins) solution because large items are placed early, leaving gaps that smaller items can fill efficiently. Using the same items sorted: 7,5,4,3,2. Bin1 gets 7, then 5 does not fit (7+5>10) so Bin2 gets 5; item 4 fits Bin1 (7+4>10? no, 11>10) and not Bin2 (5+4=9) so actually check: Bin1 7-> leftover 3, 4 does not fit → Bin2 5, leftover 5, fits 4 → Bin2 (5+4=9). Then item 3: Bin1 leftover 3 fits 3 → Bin1 (7+3=10). Item 2 fits Bin2 (9+2>10?) no, leftover is 1, so new Bin3 (2). Bins: 3. A different example might demonstrate superiority, but the key in exams is to trace both algorithms accurately.
递减首次适应算法通过先将物品按尺寸非增排序来改进首次适应。这通常能得到更好（即箱子数更少）的解，因为大物品先放置，留出的小间隙可由小物品有效填充。使用相同的物品排序：7,5,4,3,2。箱1放入7，剩余3；5不能放入箱1，开箱2放入5；4不能放入箱1 (3<4)，放入箱2 (5+4=9)；3放入箱1 (7+3=10)；2放入箱2 (9+2=11>10) 不能，开箱3放入2。箱子数：3。虽然此例未减少箱数，但考试中需准确跟踪两种算法，并比较所用箱数。
6. Kruskal’s Algorithm for Minimum Spanning Tree | 克鲁斯卡尔最小生成树算法
Kruskal’s algorithm finds a minimum spanning tree (MST) for a weighted connected graph by building the tree edge by edge. It first sorts all edges in non‑decreasing order of weight. Then, it considers edges in that order, adding an edge to the MST if it does not form a cycle with the edges already selected. The algorithm stops when n−1 edges have been added (where n is the number of vertices).
克鲁斯卡尔算法通过一条条添加边来寻找加权连通图的最小生成树。它首先将所有边按权重非减排序。然后，按该顺序考虑每条边，如果一条边不会与已选边形成环，则将其加入最小生成树。当已添加n−1条边时算法停止（n为顶点数）。
Consider a graph with vertices A,B,C,D and edges: AB(2), AC(5), AD(4), BC(3), BD(6), CD(1). Sorted edges: CD(1), AB(2), BC(3), AD(4), AC(5), BD(6). Add CD(1). Add AB(2). Add BC(3) – does not form a cycle. Next AD(4) would form cycle A-B-C-D-A? Actually edges selected so far: CD, AB, BC. Introducing AD would connect A to D via A-D and D-C-B-A a cycle, so reject. Add AC(5) – cycle formed, reject. Add BD(6) – tree already has 3 edges, stop. MST weight = 1+2+3 = 6.
考虑具有顶点A,B,C,D的图和边：AB(2), AC(5), AD(4), BC(3), BD(6), CD(1)。排好序的边：CD(1), AB(2), BC(3), AD(4), AC(5), BD(6)。添加CD(1)。添加AB(2)。添加
Published by TutorHao | A-Level Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导