Standard Solutions for Algorithms | 算法的标准解法

📚 Standard Solutions for Algorithms | 算法的标准解法

In the CIE IGCSE Computer Science syllabus, algorithms form the backbone of problem solving. A standard solution is a well-established, repeatable method for solving a class of problems. This article presents the core algorithmic techniques you need to master for the exam, including standard algorithms, control structures, and validation methods.

在 CIE IGCSE 计算机科学考纲中，算法是问题解决的基石。标准解法是指用于解决某一类问题的、成熟且可重复的方法。本文系统梳理考试中必须掌握的核心算法技巧，包括标准算法、控制结构以及验证方法。

1. Key Terminology | 关键术语

Before exploring standard solutions, you must understand the essential vocabulary. An algorithm is a finite sequence of precise steps that solves a problem. A program is an algorithm written in a programming language. A flowchart is a diagrammatic representation of an algorithm, while pseudocode is a text-based, language-independent description.

在探索标准解法之前，你必须理解基本术语。算法是解决问题的有限且精确的步骤序列。程序是用编程语言写成的算法。流程图是算法的图形化表示，而伪代码是基于文本、与具体语言无关的描述方式。

Another key concept is decomposition, which means breaking a large problem into smaller, manageable sub-problems. Abstraction removes unnecessary details so that only the relevant information remains. Both techniques support the design of clear, modular algorithms.

另一个关键概念是分解，即将一个大问题拆分为更小、更易于管理的子问题。抽象则是去除无关细节，只保留相关信息。这两种技术有助于设计清晰、模块化的算法。

Finally, efficiency measures how well an algorithm uses time and memory. In IGCSE, you are expected to compare the efficiency of linear search and binary search, and to select appropriate algorithms for given tasks.

最后，效率衡量算法在时间和空间上的使用情况。在 IGCSE 考试中，你需要比较线性搜索与二分搜索的效率，并根据任务选择适当的算法。

2. Problem-Solving Approach | 问题解决方法

A standard approach to algorithmic problem solving follows these stages: understand the problem, identify inputs and outputs, break it down into sub-tasks, design the steps, then test and refine. This methodology ensures that your solution is logical and complete.

算法问题解决的标准流程包括以下阶段：理解问题、明确输入与输出、将问题分解为子任务、设计步骤、然后进行测试与优化。这一方法确保你的解决方案逻辑清晰且完整。

For example, if the problem is “find the average of ten numbers”, you would first determine that the input is ten numbers, the output is the average, and the sub-tasks include summing the numbers and dividing by ten. This structured approach is exactly what examiners look for.

例如，若问题是”求十个数的平均值”，你首先确定输入是十个数，输出是平均值，子任务包括求和以及除以十。这种结构化的方法正是考官希望看到的。

Understand the problem | 理解问题
Define inputs and outputs | 定义输入与输出
Decompose into sub-problems | 分解为子问题
Design step-by-step solution | 设计逐步解决方案
Test with sample data | 使用样例数据测试

3. Representing Algorithms | 算法的表示方式

In CIE examinations, you must be able to read and write pseudocode, and to interpret or draw flowcharts. Pseudocode uses plain English-like statements, while flowcharts use standard symbols: rectangles for processes, diamonds for decisions, parallelograms for input/output, and arrows for flow of control.

在 CIE 考试中，你必须能够阅读和编写伪代码，并能够理解或绘制流程图。伪代码使用类似英语的自然语句，而流程图使用标准符号：矩形表示处理，菱形表示判断，平行四边形表示输入/输出，箭头表示控制流。

Consider a simple algorithm to input a number and print whether it is positive or negative.

考虑一个简单算法：输入一个数，并输出它是正数还是负数。

INPUT Number
IF Number > 0 THEN
OUTPUT “Positive”
ELSE
OUTPUT “Negative or Zero”
ENDIF

For flowcharts, you must be careful with the direction of arrows and ensure every path leads to a clear end. A common error is forgetting the terminal symbol, which represents the start or end of the algorithm.

对于流程图，你需要注意箭头的方向，并确保每条路径最终都到达明确的结束点。常见错误是忘记终端符号——它表示算法的开始或结束。

4. Sequence, Selection, and Iteration | 顺序、选择与循环

The three basic control structures are sequence, selection, and iteration. Every algorithm can be built from these structures alone. Sequence executes statements one after another; selection chooses between paths using IF or CASE; iteration repeats a block using FOR, WHILE, or REPEAT loops.

三种基本控制结构是顺序、选择和循环。每个算法都可以仅由这些结构构建。顺序结构逐条执行语句；选择结构通过 IF 或 CASE 在路径之间做出选择；循环结构通过 FOR、WHILE 或 REPEAT 重复执行某段代码。

For selection, the pseudocode may look like:

对于选择结构，伪代码如下：

IF score >= 50 THEN
OUTPUT “Pass”
ELSE
OUTPUT “Fail”
ENDIF

For iteration, consider a loop that outputs the numbers from 1 to 5:

对于循环，考虑输出 1 到 5 的循环：

FOR i = 1 TO 5
OUTPUT i
NEXT i

Remember that a WHILE loop checks the condition before executing, while a REPEAT loop executes at least once and checks after. Choosing the correct loop structure is a key skill in algorithm design.

请记住，WHILE 循环在执行前检查条件，而 REPEAT 循环至少执行一次后再检查条件。选择正确的循环结构是算法设计中的关键技能。

5. Standard Algorithms: Totalling and Counting | 标准算法：总计与计数

Standard algorithms are common solutions to frequently occurring problems. Totalling adds up a list of numbers; counting counts how many items satisfy a condition. These appear in almost every examination.

标准算法是针对常见问题的通用解法。总计是将一系列数字相加；计数是统计满足某个条件的项目数量。这两类算法几乎出现在每场考试中。

For totalling, set a variable total to 0, then loop through each value, adding it to total. For counting, initialise count to 0, then increment it whenever the condition is true.

对于总计，将变量 total 初始化为 0，然后遍历每个值并将其加到 total 中。对于计数，将 count 初始化为 0，并在条件为真时将其递增。

total = 0
FOR each number IN list
total = total + number
NEXT

The same pattern applies to finding the average: total divided by the number of items. In marking schemes, the initialisation step is often required, so never forget to set the starting value.

同样的模式也适用于求平均值：总数除以项数。在评分标准中，初始化步骤常常是得分点，因此切勿忘记设定初始值。

6. Standard Algorithms: Maximum and Minimum | 标准算法：最大值与最小值

Finding the largest or smallest value in a list is another standard algorithm. Set a variable max to the first value (or a very small number), then compare each subsequent value with the current maximum, updating if it is larger.

查找列表中的最大值或最小值是另一个标准算法。将变量 max 设为第一个值（或一个非常小的数），然后将后续每个值与当前最大值比较，如果更大则更新。

max = list[1]
FOR i = 2 TO length(list)
    IF list[i] > max THEN
        max = list[i]
    ENDIF
NEXT i

For the minimum, simply change the comparison operator from > to <. This algorithm works on arrays and also on single values read from a file, making it a versatile tool in practical programming.

对于最小值，只需将比较运算符从 > 改为 <。该算法适用于数组，也适用于从文件读取的单个值，在实际编程中非常灵活。

7. Linear Search | 线性搜索

Linear search checks each item in sequence until the target value is found or the end of the list is reached. It works on unsorted and sorted lists, but it is less efficient than binary search on large data sets.

线性搜索按顺序检查每个项目，直到找到目标值或到达列表末尾。它适用于未排序和已排序的列表，但在大数据集上效率低于二分搜索。

The pseudocode implementation is:

其伪代码实现如下：

found = FALSE
i = 1
WHILE found = FALSE AND i <= length(list)
    IF list[i] = target THEN
        found = TRUE
        OUTPUT i
    ENDIF
    i = i + 1
ENDWHILE
IF found = FALSE THEN
    OUTPUT “Not found”
ENDIF

Linear search is easy to implement and does not require the data to be sorted. The worst-case number of comparisons is n, where n is the number of elements, so it has linear time complexity.

线性搜索易于实现，并且不要求数据已排序。最坏情况下的比较次数为 n，其中 n 为元素个数，因此其时间复杂度为线性的。

8. Binary Search | 二分搜索

Binary search is a much faster algorithm, but it requires the list to be sorted. It works by repeatedly dividing the search interval in half, comparing the middle element with the target, and discarding the half that cannot contain the target.

二分搜索是一种快得多的算法，但要求列表已经排序。它通过反复将搜索区间一分为二，将中间元素与目标值比较，并丢弃不可能包含目标的一半，来缩小查找范围。

Steps of the algorithm:

算法步骤如下：

Set lower bound to first index and upper bound to last index | 设下界为首个索引，上界为末个索引
Find the middle index = (lower + upper) / 2 | 计算中间索引 = (下界 + 上界) / 2
If the middle value equals the target, stop | 若中间值等于目标值，则停止
If the target is smaller, set upper = middle – 1 | 若目标值更小，则设上界 = 中间 – 1
If the target is larger, set lower = middle + 1 | 若目标值更大，则设下界 = 中间 + 1

lower = 1
upper = length(list)
found = FALSE
WHILE lower <= upper AND found = FALSE
    mid = (lower + upper) DIV 2
    IF list[mid] = target THEN
        found = TRUE
    ELSE IF list[mid] < target THEN
        lower = mid + 1
    ELSE
        upper = mid – 1
    ENDIF
ENDWHILE

For a list of 1,000 elements, linear search may need 1,000 comparisons, but binary search needs only 10 comparisons in the worst case. This is because each step halves the search size.

对于包含 1,000 个元素的列表，线性搜索最多可能需要 1,000 次比较，而二分搜索在最坏情况下只需要 10 次。这是因为每一步都将搜索规模减半。

9. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. This process repeats until no swaps are needed, meaning the list is sorted.

冒泡排序反复遍历列表，比较相邻的项目，如果顺序错误就交换它们。该过程一直重复到不需要任何交换为止，此时列表已排序。

Take the list [5, 2, 9, 1]. The first pass compares 5 and 2 → swap; 5 and 9 → no swap; 9 and 1 → swap. At the end of the pass, the largest value 9 is in its correct position. The same process repeats on the remaining unsorted portion.

以列表 [5, 2, 9, 1] 为例。第一轮比较 5 和 2 → 交换；5 和 9 → 不交换；9 和 1 → 交换。这一轮结束时，最大值 9 已就位。然后对剩余未排序部分重复同样的过程。

FOR i = 1 TO n – 1
    FOR j = 1 TO n – i
        IF list[j] > list[j + 1] THEN
            swap list[j] and list[j + 1]
        ENDIF
    NEXT j
NEXT i

Bubble sort is simple but inefficient for large lists, as it has a worst-case time complexity of O(n²). You should be able to simulate this algorithm manually for a short list in the exam.

冒泡排序简单，但对大规模列表效率较低，其最坏时间复杂度为 O(n²)。在考试中，你需要能够手动模拟短列表的排序过程。

10. Insertion Sort | 插入排序

Insertion sort builds the sorted list one element at a time. It takes each element and inserts it into its correct position among the already-sorted elements, shifting larger elements to the right as needed.

插入排序逐个构建已排序列表。它取出每个元素，并将其插入已排序元素中的正确位置，必要时将较大的元素向右移动。

Consider [7, 3, 5, 1]. Start with 7 as sorted. Take 3, compare with 7, and insert before it: [3, 7]. Take 5, compare with 7 then 3, and insert between: [3, 5, 7]. Finally insert 1 at the front: [1, 3, 5, 7].

以 [7, 3, 5, 1] 为例。将 7 视为已排序序列。取出 3，与 7 比较并插入其前面：[3, 7]。取出 5，依次与 7、3 比较，插入中间：[3, 5, 7]。最后将 1 插入最前面：[1, 3, 5, 7]。

FOR i = 2 TO n
    key = list[i]
    j = i – 1
    WHILE j >= 1 AND list[j] > key
        list[j + 1] = list[j]
        j = j – 1
    ENDWHILE
    list[j + 1] = key
NEXT i

Insertion sort is also O(n²) in the worst case, but it performs well on small lists or nearly sorted lists.

插入排序的最坏时间复杂度同样为 O(n²)，但在小规模或近乎有序的列表上表现良好。

11. Validating and Testing Algorithms | 算法的验证与测试

Once an algorithm is written, you must validate it, meaning you check that it solves the original problem correctly. Dry running is a technique where you trace through the algorithm step by step using a trace table, recording the values of all variables at each stage.

算法编写完成后，你必须进行验证，即检查其是否正确解决了原始问题。干运行是一种使用跟踪表逐步追踪算法执行过程的技术，用于记录每个阶段所有变量的值。

Step \| 步骤	number \| 数值	count \| 计数	Output \| 输出
1	5	0	–
2	–	1	5

Boundary testing is also important: you should test extreme values such as 0, negative numbers, or an empty list to ensure the algorithm handles them gracefully. In the exam, you may be asked to identify errors in pseudocode or to complete a trace table.

边界测试同样重要：你应该测试极端值，如 0、负数或空列表，以确保算法能妥善处理它们。在考试中，你可能会被要求识别伪代码中的错误或完成跟踪表。

12. Choosing the Right Algorithm | 选择正确的算法

Selecting the appropriate standard algorithm depends on the data and the problem. If the data is unsorted and you need to find one item, use linear search. If the data is sorted, binary search is far more efficient. For sorting small datasets, insertion sort is often easier to code; for larger datasets, both bubble sort and insertion sort are slow, and you might consider merge sort.

选择正确的标准算法取决于数据特征和问题本身。如果数据未排序且需要查找一个项目，应使用线性搜索。如果数据已排序，二分搜索效率高得多。对于小规模数据集的排序，插入排序通常更易编写；对于较大数据集，冒泡排序和插入排序都较慢，这时可以考虑归并排序。

Unsorted data + search → linear search | 未排序数据 + 搜索 → 线性搜索
Sorted data + search → binary search | 已排序数据 + 搜索 → 二分搜索
Small list sorting → insertion sort | 小规模列表排序 → 插入排序
Large list sorting → merge sort | 大规模列表排序 → 归并排序

Always justify your choice in the exam by referring to time complexity, memory usage, and whether the data is already sorted. This analytical skill distinguishes top-scoring candidates.

在考试中，务必通过时间复杂性、内存使用情况以及数据是否已排序来论证你的选择。这种分析能力是区分高分考生的关键。

Published by TutorHao | Computer Science Revision Series | aleveler.com

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

Step \| 步骤	number \| 数值	count \| 计数	Output \| 输出
1	5	0	–
2	–	1	5

Standard Solutions for Algorithms | 算法的标准解法