A Guide to Standard Problem-Solving Methods in Algorithm Design | 算法设计中的标准解题方法指南

📚 A Guide to Standard Problem-Solving Methods in Algorithm Design | 算法设计中的标准解题方法指南

Algorithm design is a core skill in computer science, especially for students preparing for CIE examinations. This guide introduces the standard problem-solving methods you will need to master: decomposition, abstraction, pattern recognition, algorithms, and the key design approaches such as iteration, recursion, and divide-and-conquer.

算法设计是计算机科学的核心技能，尤其对于备考 CIE 的学生而言。本指南将介绍你需要掌握的标准解题方法：分解、抽象、模式识别、算法，以及迭代、递归、分治等关键设计方法。

1. Understanding the Problem | 理解问题

Before writing any code, you must fully understand the problem. This means identifying the inputs, the expected outputs, the constraints, and any special cases. Read the question carefully and underline keywords such as ‘maximum’, ‘minimum’, ‘sorted’, ‘unique’, or ‘efficient’.

在编写任何代码之前，你必须充分理解问题。这包括识别输入、预期输出、约束条件以及任何特殊情况。仔细阅读题目，并在“最大值”“最小值”“已排序”“唯一”或“高效”等关键词下划线。

A common mistake is to start coding immediately. Instead, restate the problem in your own words. Ask yourself: What data do I have? What transformation is required? What should the output look like?

一个常见错误是立即开始编码。相反，你应该用自己的话重述问题。问自己：我有什么数据？需要进行什么转换？输出应该是什么样子？

Identify inputs and outputs | 识别输入和输出

List every input variable and its data type. Determine whether the output is a single value, a set, a list, or a boolean.

列出每个输入变量及其数据类型，确定输出是单个值、集合、列表还是布尔值。
Identify constraints | 识别约束条件

Check for limits on time, memory, input size, or value ranges. For CIE questions, constraints often suggest which algorithm to use.

检查时间、内存、输入规模或数值范围的限制。对于 CIE 题目，约束条件往往暗示了应使用哪种算法。
Identify edge cases | 识别边界情况

Consider empty inputs, single elements, negative numbers, duplicates, and extreme values.

考虑空输入、单元素、负数、重复值以及极端数值。

2. Decomposition | 分解

Decomposition is the process of breaking a complex problem into smaller, more manageable sub-problems. Each sub-problem can be solved independently, and the solutions are combined to solve the original problem.

分解是将一个复杂问题拆分为更小、更易管理的子问题的过程。每个子问题可以独立求解，再将解合并以解决原始问题。

For example, writing a program to calculate student grades might be decomposed into: read data, calculate average, determine grade, and display results. Each part becomes a separate function or procedure.

例如，编写一个计算学生成绩的程序可以分解为：读取数据、计算平均分、确定等级和显示结果。每个部分成为一个独立的函数或过程。

Advantages of decomposition | 分解的优点

It makes problems easier to understand, allows team collaboration, and simplifies testing and debugging.

它使问题更易理解，允许团队协作，并简化测试和调试。
How to decompose | 如何进行分解

Start with the main task and ask ‘What steps are needed?’ Continue breaking each step down until each sub-task is simple enough to implement directly.

从主任务开始，问“需要哪些步骤？”继续将每个步骤拆分，直到每个子任务都足够简单，可以直接实现。

3. Abstraction | 抽象

Abstraction means removing unnecessary details and focusing only on the essential features of a problem. In algorithm design, abstraction allows you to create a general solution that can be applied to many different situations.

抽象意味着去除不必要的细节，只关注问题的本质特征。在算法设计中，抽象使你能够创建适用于许多不同情况的通用解决方案。

For instance, when designing a sorting algorithm, you do not need to know whether the items are names, numbers, or records. You only need to know that they can be compared using a ‘less than’ operation.

例如，在设计排序算法时，你不需要知道排序对象是姓名、数字还是记录。你只需要知道它们可以通过“小于”操作进行比较。

Levels of abstraction | 抽象的层次

High-level abstraction describes what a system does; low-level abstraction describes how it does it. Pseudocode is an example of medium-level abstraction.

高层抽象描述系统做什么；低层抽象描述系统如何做。伪代码是中层抽象的一个例子。
Using abstraction in exams | 在考试中使用抽象

When answering questions, describe the algorithm in terms of its logical steps without over-specifying the syntax of a particular programming language.

在回答问题时，用逻辑步骤来描述算法，而不要过度指定某种编程语言的语法。

4. Pattern Recognition | 模式识别

Pattern recognition is the ability to identify similarities and regularities in data or in problems. Recognising a pattern allows you to reuse a known solution instead of inventing a new one.

模式识别是识别数据或问题中相似性和规律性的能力。识别出模式可以让你复用已知的解决方案，而不是重新发明一个。

Common patterns in algorithm design include: searching, sorting, counting, aggregating, and transforming. If a problem asks for the largest value in a list, you immediately recognise the ‘find maximum’ pattern.

算法设计中常见的模式包括：搜索、排序、计数、聚合和转换。如果问题要求列表中的最大值，你可以立即识别出“查找最大值”模式。

Sequential search pattern | 顺序查找模式

Scan each item one by one until a condition is met. Used when data is unsorted or very small.

逐个扫描每个项目，直到满足条件。适用于数据未排序或规模很小的情况。
Binary search pattern | 二分查找模式

Repeatedly divide a sorted list in half to locate a target. Much faster than sequential search for large datasets.

反复将已排序列表分成两半以定位目标。对于大规模数据集，比顺序查找快得多。
Accumulator pattern | 累加器模式

Initialize a variable to zero, then update it inside a loop. Used for sums, products, counts, and averages.

将变量初始化为零，然后在循环中更新它。用于求和、乘积、计数和平均值。

5. Standard Algorithms: Searching | 标准算法：查找

Searching is the process of finding a specific element in a data structure. The two most common search algorithms are linear search and binary search.

查找是在数据结构中寻找特定元素的过程。两种最常见的查找算法是线性查找和二分查找。

Linear search works on any list and checks each element in order until the target is found or the list ends. Its time complexity is O(n) in the worst case.

线性查找适用于任何列表，按顺序检查每个元素，直到找到目标或列表结束。其最坏时间复杂度为 O(n)。

Binary search requires a sorted list. It repeatedly compares the target to the middle element and discards half of the remaining data. Its time complexity is O(log n).

二分查找要求列表已排序。它反复将目标与中间元素比较，并丢弃剩余数据的一半。其时间复杂度为 O(log n)。

Linear Search: O(n) | Binary Search: O(log n)

线性查找：O(n) | 二分查找：O(log n)

When to use linear search | 何时使用线性查找

When the list is unsorted, when the list is very small, or when you need to find all occurrences.

当列表未排序、列表非常小，或需要查找所有出现位置时。
When to use binary search | 何时使用二分查找

When the list is already sorted and you need fast repeated searches.

当列表已经排序且需要快速重复查找时。

6. Standard Algorithms: Sorting | 标准算法：排序

Sorting arranges data in a specific order, usually ascending or descending. CIE examinations often focus on bubble sort and insertion sort for understanding, and may mention merge sort or quick sort for more advanced contexts.

排序是按特定顺序（通常升序或降序）排列数据。CIE 考试通常侧重冒泡排序和插入排序的理解，并可能在更高级的情境中提及归并排序或快速排序。

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

冒泡排序重复遍历列表，比较相邻项目，如果顺序错误则交换。此过程重复进行，直到不再需要交换。

Insertion sort builds the sorted list one item at a time. Each new element is inserted into its correct position among the previously sorted elements.

插入排序一次一个地构建有序列表。每个新元素被插入到之前已排序元素中的正确位置。

Algorithm \| 算法	Best Case \| 最佳情况	Average Case \| 平均情况	Worst Case \| 最坏情况
Bubble Sort \| 冒泡排序	O(n)	O(n²)	O(n²)
Insertion Sort \| 插入排序	O(n)	O(n²)	O(n²)
Merge Sort \| 归并排序	O(n log n)	O(n log n)	O(n log n)

7. Algorithm Design Techniques: Iteration | 算法设计技术：迭代

Iteration is the repeated execution of a block of code using a loop. In pseudocode, this is often represented by FOR, WHILE, or REPEAT structures.

迭代是使用循环重复执行一段代码。在伪代码中，通常用 FOR、WHILE 或 REPEAT 结构表示。

Iteration is appropriate when the number of repetitions is known (FOR loop) or when the loop must continue until a condition changes (WHILE loop).

当重复次数已知时（FOR 循环）或当循环必须继续直到条件改变时（WHILE 循环），迭代是合适的。

FOR i ← 1 TO n DO … ENDFOR

Counting loop | 计数循环

A FOR loop is ideal when you know exactly how many times to repeat.

当你确切知道要重复多少次时，FOR 循环是理想选择。
Conditional loop | 条件循环

A WHILE loop is used when the number of repetitions depends on a runtime condition.

当重复次数取决于运行时条件时，使用 WHILE 循环。

8. Algorithm Design Techniques: Recursion | 算法设计技术：递归

Recursion is a technique in which a function calls itself to solve a smaller version of the original problem. Every recursive function must have a base case to stop the recursion and a recursive case to continue it.

递归是一种函数调用自身以解决原始问题更小版本的技术。每个递归函数必须有一个基础情形来停止递归，以及一个递归情形来继续递归。

A classic recursive example is calculating the factorial of a number:

一个经典的递归示例是计算数字的阶乘：

FUNCTION Factorial(n) IF n = 0 THEN RETURN 1 ELSE RETURN n × Factorial(n − 1) ENDIF ENDFUNCTION

函数 Factorial(n) 如果 n = 0 则返回 1 否则返回 n × Factorial(n − 1) 结束结束函数

Base case | 基础情形

The simplest instance of the problem that can be answered directly. In the factorial example, the base case is n = 0.

问题的最简单实例，可以直接回答。在阶乘示例中，基础情形是 n = 0。
Recursive case | 递归情形

The part that reduces the problem size and calls the function again with a smaller argument.

减小问题规模并用更小的参数再次调用函数的部分。
Tracing recursion | 追踪递归

In exams, you may be asked to trace recursive calls. Draw a call tree to show each call and its returned value.

在考试中，你可能会被要求追踪递归调用。画一棵调用树来展示每次调用及其返回值。

9. Divide and Conquer | 分治法

Divide and conquer is a powerful design strategy that splits a problem into smaller independent sub-problems, solves each recursively, and combines the solutions. Merge sort is a typical example.

分治是一种强大的设计策略，它将问题拆分为更小的独立子问题，递归地解决每个子问题，然后合并解决方案。归并排序是一个典型例子。

Steps of divide and conquer:

分治法的步骤：

Divide | 分解

Split the problem into two or more smaller sub-problems of the same type.

将问题拆分为两个或更多同类型的更小子问题。
Conquer | 解决

Solve each sub-problem recursively. If the sub-problem is small enough, solve it directly.

递归地解决每个子问题。如果子问题足够小，则直接解决。
Combine | 合并

Merge the solutions of the sub-problems to form the solution to the original problem.

将子问题的解合并，形成原始问题的解。

The time complexity of merge sort is O(n log n), which makes it significantly faster than bubble sort for large datasets.

归并排序的时间复杂度为 O(n log n)，这使得它在大规模数据集上明显快于冒泡排序。

10. Greedy Algorithms | 贪心算法

A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum. Greedy methods are simple and efficient, but they do not always produce the best solution for every problem.

贪心算法在每一步做出局部最优选择，希望找到全局最优解。贪心方法简单高效，但并不总是为每个问题产生最佳解决方案。

A classic greedy example is the coin change problem: to make a given amount using the fewest coins, always take the largest coin that does not exceed the remaining amount.

一个经典的贪心示例是找零问题：要用最少的硬币凑出给定金额，始终取不超过剩余金额的最大硬币。

Advantages | 优点

Greedy algorithms are usually easy to understand and implement, and they run quickly.

贪心算法通常易于理解和实现，运行速度快。
Disadvantages | 缺点

They may fail for problems requiring global planning, such as the travelling salesperson problem.

对于需要全局规划的问题，它们可能失效，例如旅行商问题。

11. Dynamic Programming | 动态规划

Dynamic programming (DP) solves problems by breaking them into overlapping sub-problems and storing the results of these sub-problems to avoid redundant computation. It is often used for optimisation problems.

动态规划通过将问题拆分为重叠子问题并存储这些子问题的结果来避免重复计算。它常用于最优化问题。

The Fibonacci sequence is a simple illustration. Without DP, computing Fibonacci(n) recursively repeats many calculations. With DP, each value is computed once and reused.

斐波那契数列是一个简单示例。不使用动态规划时，递归计算 Fibonacci(n) 会重复许多计算。使用动态规划时，每个值只计算一次并复用。

Fib(0) = 0, Fib(1) = 1, Fib(n) = Fib(n − 1) + Fib(n − 2)

Fib(0) = 0，Fib(1) = 1，Fib(n) = Fib(n − 1) + Fib(n − 2)

Top-down approach (memoisation) | 自顶向下方法（记忆化）

Start from the original problem and recurse downwards, storing results in a table when first computed.

从原始问题开始向下递归，在首次计算时将结果存储到表中。
Bottom-up approach (tabulation) | 自底向上方法（填表）

Compute the smallest sub-problems first and build up to the original problem iteratively.

先计算最小的子问题，再迭代构建到原始问题。

12. Comparing Problem-Solving Methods | 标准解题方法对比

When choosing a method, consider the problem size, whether the data is sorted, whether an exact answer is required, and how much memory is available.

选择方法时，要考虑问题规模、数据是否已排序、是否需要精确答案，以及可用内存有多少。

Method \| 方法	Typical Use \| 典型用途	Complexity \| 复杂度
Iteration \| 迭代	Simple repeated tasks	O(n) or O(n²)
Recursion \| 递归	Dividing problems naturally	Depends on depth \| 取决于深度
Divide and Conquer \| 分治	Sorting, searching	O(n log n)
Greedy \| 贪心	Optimisation with local choices	Often O(n log n)
Dynamic Programming \| 动态规划	Overlapping sub-problems	O(n²) or O(n·m)

In the CIE examination, always show your working clearly. Write pseudocode that matches the standard notation used in your syllabus, label each section of your algorithm, and state the complexity explicitly when asked.

在 CIE 考试中，始终清晰地展示你的步骤。编写与教学大纲中标准记法一致的伪代码，标注算法的每个部分，并在被问及时明确说明复杂度。

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

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

A Guide to Standard Problem-Solving Methods in Algorithm Design | 算法设计中的标准解题方法指南