7 · Algorithm design and problem-solving

7 · 算法设计与问题解决

Designing, checking and fixing algorithms

设计、检查与修正算法

The half of Paper 2 that is not about writing code: breaking a problem down, recognising the standard algorithms, choosing test data, tracing a dry run, and correcting errors. Every skill here is marked on precision.

试卷二中与编写代码无关的那一半:把问题拆解开来、识别标准算法、选择测试数据、手动追踪演算,以及修正错误。这里的每一项技能都以精确度评分。

Core for all candidates 所有考生均需掌握的核心内容 Covers 7.1 to 7.9 涵盖 7.1 至 7.9 Roughly a third of Paper 2 约占试卷二的三分之一

Explainer · 7.1

讲解 · 7.1

The program development life cycle

程序开发生命周期

For 0478 the life cycle is limited to four stages, in order:

在 0478 中,生命周期限定为按顺序排列的四个阶段:

Stage	阶段	What happens, and the tasks in it	发生的过程及其中的任务
Analysis	分析	abstraction (keep only what the solution needs, discard the rest), decomposition of the problem, and identifying the problem and its requirements	抽象化(只保留解决方案所需的内容,舍弃其余部分)、对问题进行分解,以及识别问题及其需求
Design	设计	decomposition into parts, then structure diagrams, flowcharts and pseudocode to set out the solution	将问题分解为若干部分,然后用结构图、流程图和伪代码写出解决方案
Coding	编码	writing the program code, with iterative testing as each module is written	编写程序代码,并在编写每个模块时进行迭代测试
Testing	测试	testing the finished program code with chosen test data	用选定的测试数据测试完成的程序代码

Abstraction and decomposition both belong to the analysis stage. Abstraction is deciding what matters and ignoring the rest; decomposition is breaking the problem into smaller parts. Don't place them in design.

抽象化和分解都属于分析阶段。抽象化是判断哪些是重要的、忽略其余部分;分解是把问题拆解成更小的部分。不要把它们归入设计阶段。

Explainer · 7.2

讲解 · 7.2

Computer systems, sub-systems and decomposition

计算机系统、子系统与分解

Every computer system is built from sub-systems, and each sub-system can be split into smaller sub-systems until each one does a single job. Decomposing a problem means splitting it into four component parts:

每一个计算机系统都由子系统构成,而每个子系统又可以拆分成更小的子系统,直到每个子系统只完成一项工作为止。分解一个问题意味着把它拆分成四个组成部分:

Part	部分	Meaning	含义
Inputs	输入	the data the system needs, entered while it runs	系统运行期间输入的、系统所需要的数据
Processes	处理	the tasks carried out on the input data, together with any data already stored	对输入数据以及任何已存储数据所执行的任务
Outputs	输出	information displayed or printed for the user	显示给用户或为用户打印出来的信息
Storage	存储	data saved to a file for use in the future	保存到文件中以供将来使用的数据

The design methods you must be able to use are structure diagrams (a hierarchy showing the system split into sub-systems), flowcharts (steps and their order, using the standard symbols), and pseudocode.

你必须能够运用的设计方法包括:结构图(展示系统如何拆分为各子系统的层级图)、流程图(用标准符号表示各步骤及其顺序),以及伪代码。

Try it yourself

动手试试

Decompose a system

分解一个系统

A gym uses a card reader at a turnstile to let members in. Click each item to tag it as an input, process, output or storage part. Then check your answers.

某健身房在旋转闸门处使用读卡器放会员进入。点击每一项,将其标记为输入、处理、输出或存储部分,然后检查你的答案。

Explainer · 7.3

讲解 · 7.3

Explaining the purpose of a given algorithm

解释给定算法的目的

Given a flowchart or pseudocode, you may be asked two different things:

给定一份流程图或伪代码,题目可能会问两种不同的内容:

Asked for	题目要求	What that means	含义
The purpose	目的	a one-line statement of what the algorithm achieves overall, for example “it finds the largest and smallest values in a list”	用一句话说明该算法整体上实现了什么,例如"它找出列表中的最大值和最小值"
The processes involved	涉及的处理过程	a description of the steps: what is input, what comparisons and calculations happen, what is output	描述具体步骤:输入了什么、发生了哪些比较和计算、输出了什么

Read which one the question wants. Markers report candidates giving the purpose when asked for the processes, and describing the steps when asked only for the purpose. Questions often use single-letter variable names on purpose so you have to work the meaning out.

要看清题目问的是哪一种。考官报告称,考生在被要求描述处理过程时却给出了目的,而在只被要求说明目的时却描述了各个步骤。题目常常故意使用单字母变量名,逼你自己去推断其含义。

Explainer · 7.4

讲解 · 7.4

Standard methods of solution

标准解法

Five methods recur across algorithms. You must be able to recognise them and write them in Cambridge pseudocode.

有五种方法会反复出现在各种算法中。你必须能够识别它们,并用剑桥伪代码把它们写出来。

Method	方法	How it works	工作原理
Totalling	累加	a variable starts at `0` and each value is added to it inside a loop	一个变量从 `0` 开始,每个数值在循环中被依次加到它上面
Counting	计数	a counter starts at `0` and adds `1` each time a condition is met	一个计数器从 `0` 开始,每当满足某个条件就加 `1`
Maximum / minimum	最大值 / 最小值	track the largest / smallest seen so far; replace it when a value beats it. Safest to start both at the first value in the list	记录目前为止见过的最大值/最小值;当出现更极端的数值时就替换它。最稳妥的做法是把两者都先设为列表中的第一个值
Average	平均值	total the values, then divide the total by how many there were	把各数值相加求和,再用总和除以数值的个数
Linear search	线性搜索	check each item in turn against the search value; stop when found or the list ends. Uses a `Found` flag	依次将每个项目与搜索值比较;找到时或列表结束时停止。使用一个 `Found` 标志变量
Bubble sort	冒泡排序	compare each item with the next and swap if out of order; repeat passes until a pass makes no swaps. After each pass the next-largest item is in place	将每个项目与下一个比较,顺序不对就交换;重复多轮,直到某一轮没有发生任何交换为止。每一轮结束后,次大的项目就归位了

A totalling or counting variable must be set to 0 before the loop, not inside it. Markers report this omission constantly. When asked to identify an algorithm, name it precisely: “a linear search” or “a bubble sort”, not just “a search” or “a sorting algorithm”.

累加或计数变量必须在循环之前设为 0,而不是在循环内部。考官经常报告这一遗漏。被要求识别某个算法时,要精确地说出名称:"线性搜索"或"冒泡排序",而不是笼统地说"一种搜索"或"一种排序算法"。

Try it yourself

动手试试

Run the standard methods

运行标准解法

The same list of six numbers, five methods. Step through each one and watch exactly what it compares, adds or swaps.

同一组六个数字,五种方法。逐步演示每一种方法,准确观察它比较、相加或交换的内容。

Explainer · 7.5

讲解 · 7.5

Validation and verification

验证(validation)与核实(verification)

	Validation	验证	Verification	核实
What it checks	检查的内容	that input data is reasonable / sensible before it is accepted	输入数据在被接受之前是否合理 / 说得通	that data has not changed as it was entered or copied from one place to another	数据在输入或从一处复制到另一处的过程中没有发生改变
Done by	执行方	the program, automatically	由程序自动执行	the user, or the program comparing two copies	由用户执行,或由程序比较两份副本
Types	类型	range, length, type, presence, format, check digit	范围检查、长度检查、类型检查、存在性检查、格式检查、校验位	visual (screen) check, double entry check	视觉(屏幕)检查、双重输入检查

Validation check	验证检查	Accepts only if…	仅在以下情况接受…
Range check	范围检查	the value is between a stated lower and upper limit	数值在规定的上下限之间
Length check	长度检查	the number of characters is exactly, or within, a stated range	字符数恰好等于,或落在规定的范围之内
Type check	类型检查	the data is the right type (for example a whole number)	数据类型正确(例如是一个整数)
Presence check	存在性检查	something was entered, not left blank	已输入了内容,而非留空
Format check	格式检查	the characters match a set pattern, for example `CUB9999`	字符符合设定的模式,例如 `CUB9999`
Check digit	校验位	an extra digit calculated from the others matches, catching mis-typed or transposed digits	由其余数字计算出的额外一位数字相符,以捕捉输错或换位的数字

Verification is not “checking the data is correct”. It checks the data was not altered during entry. Double entry (type it twice, compare) and a visual check (read it back on screen) are the two methods. Naming a range check or presence check for a verification question earns nothing.

核实(verification)不是"检查数据是否正确"。它检查的是数据在输入过程中是否被更改过。双重输入(输入两次并比较)和视觉检查(在屏幕上读回核对)是这两种方法。在核实类问题中说出范围检查或存在性检查得不到任何分数。

A validation check in pseudocode needs a loop that re-inputs the value until it is acceptable, and it should output a message saying why a value was rejected.

伪代码中的验证检查需要一个循环,不断重新输入数值,直到该值被接受为止,并且应当输出一条消息说明该数值为何被拒绝。

Try it yourself

动手试试

Validation tester

验证检测器

Pick a check, enter a value, and see whether the program accepts it and what message it gives. A real validation routine would then loop back and ask again.

选择一种检查方式,输入一个数值,查看程序是否接受它,以及给出的消息内容。真正的验证程序随后会循环回去再次询问。

Explainer · 7.6

讲解 · 7.6

Suggesting and applying test data

提出并应用测试数据

Type	类型	Meaning (for a rule that accepts whole numbers 1 to 100)	含义(针对一条接受 1 至 100 整数的规则)
Normal	正常数据	data the program should accept and process, e.g. `45`, `72`	程序应当接受并处理的数据,例如 `45`、`72`
Abnormal	异常数据	data the program should reject, e.g. `-5`, `"twenty"`, `3.5`	程序应当拒绝的数据,例如 `-5`、`"twenty"`、`3.5`
Extreme	极端数据	the largest and smallest values that are accepted, e.g. `1` and `100`	会被接受的最大值与最小值,例如 `1` 和 `100`
Boundary	边界数据	a pair either side of a limit: one accepted, one rejected, e.g. `0` and `1`, or `100` and `101`	位于某一界限两侧的一对数值:一个被接受,一个被拒绝,例如 `0` 和 `1`,或 `100` 和 `101`

When asked for test data, give the actual value and say whether it should be accepted or rejected. Naming the type (“normal”, “boundary”) is not test data. Only add validation to an algorithm if the question asks for it.

被要求提供测试数据时,要给出具体数值,并说明它应当被接受还是拒绝。只说出类型名称("正常""边界")并不算测试数据。只有在题目要求时,才为算法添加验证。

Try it yourself

动手试试

Classify test data

为测试数据分类

Rule: a program accepts whole numbers from 1 to 100. Click a value, then click the bin it belongs in. Check when you are done.

规则:程序接受从 1 到 100 的整数。点击一个数值,再点击它所属的分类框。完成后进行检查。

Explainer · 7.7

讲解 · 7.7

Trace tables and dry runs

追踪表与手动演算

A dry run is working through an algorithm by hand. A trace table records it: one column per variable, plus a column for output. Every time a variable changes you write its new value; every time something is output you write it in the output column, including the first prompt and without quotation marks.

手动演算是指用手工的方式一步步执行一个算法。追踪表用来记录这个过程:每个变量一列,再加一列记录输出。每当一个变量的值发生变化,就写下它的新值;每当有内容被输出,就把它写在输出列中,包括第一次的提示信息,且不加引号。

Try it yourself

动手试试

Dry-run a trace table

手动演算一个追踪表

Step through this algorithm with the input list 4, 9, 2, 7, 3. Each step fills in the cell that changed.

用输入列表 4, 9, 2, 7, 3 逐步演示这个算法。每一步都会填入发生变化的单元格。

Total ← 0
Largest ← 0
FOR Count ← 1 TO 5
    INPUT Value
    Total ← Total + Value
    IF Value > Largest
        THEN Largest ← Value
    ENDIF
NEXT Count
Average ← Total / 5
OUTPUT Largest, Average

Count	Value	Total	Largest	Average	OUTPUT

Explainer · 7.8 and 7.9

讲解 · 7.8 与 7.9

Finding errors, and writing algorithms

发现错误与编写算法

A dry run with well-chosen test data is how you find errors: trace it, spot where the output is wrong, and describe the correction. The trace-table algorithm above has a hidden fault, if every number input is negative, Largest stays 0 and the answer is wrong; the fix is to set Largest to the first value input.

用精心选择的测试数据进行手动演算,是发现错误的方法:追踪它,找出输出错误的地方,并描述如何修正。上面追踪表中的算法藏有一个隐患:如果输入的每个数字都是负数,Largest 会一直保持 0,答案就是错的;修正方法是把 Largest 设为第一个输入的值。

When writing or amending an algorithm:

编写或修改算法时:

Rule	规则	Why	原因
Answer in the form asked for	以题目要求的形式作答	a pseudocode question wants pseudocode; a flowchart question wants a flowchart. The other form scores nothing	伪代码题目要求伪代码;流程图题目要求流程图。用另一种形式作答得不到分
Match the syllabus pseudocode	与考纲伪代码格式一致	use the Cambridge keywords and layout, not a real programming language and not invented syntax	使用剑桥的关键字和排版格式,不要使用真实编程语言,也不要自创语法
Be precise with conditions	条件表达要精确	`Counter >= 10` is acceptable; “Counter ten or over” is not	`Counter >= 10` 可以接受;"Counter 达到十或以上"这种写法不行
Use meaningful names and indentation	使用有意义的名称并正确缩进	someone else has to read it	因为别人也需要读懂它

Check your understanding

检验你的理解

During which stage of the program development life cycle are abstraction and decomposition carried out?

程序开发生命周期的哪个阶段执行抽象化和分解?

Check your understanding

检验你的理解

Which of these is a verification check?

以下哪一项是核实(verification)检查?

Check your understanding

检验你的理解

A program accepts whole numbers from 1 to 80. Which pair is extreme test data?

某程序接受1 到 80之间的整数。以下哪一对是极端测试数据?

Common mistakes

常见错误

Markers reported these patterns for 7.1 to 7.9 考官针对 7.1 至 7.9 报告了以下模式

RecurringCandidates confuse validation and verification: they say verification “makes sure the data is correct”, or they name a range check or presence check for a verification question. Verification checks the data was not changed during entry; its two methods are double entry and a visual check.

反复出现考生混淆了验证(validation)和核实(verification):他们说核实"确保数据正确",或者在核实类问题中说出范围检查或存在性检查。核实检查的是数据在输入过程中是否被更改过;它的两种方法是双重输入和视觉检查。

When asked for the purpose of an algorithm, candidates describe the step-by-step processes instead, and when asked for the processes, they give only a one-line purpose. Read which the question wants.

被要求说明算法的目的时,考生却描述了逐步的处理过程;而被要求说明处理过程时,却只给出一句话的目的。要看清题目究竟问的是哪一个。

In written algorithms, markers report program code or invented syntax where pseudocode was asked for, flowchart answers to pseudocode questions, and a missing line to set a total or counter to 0 before the loop. Validation answers often leave out the loop that re-inputs the value.

在书写算法时,考官报告称,考生在要求伪代码时写出真实编程语言的代码或自创语法,用流程图回答伪代码问题,以及遗漏了在循环之前把总和或计数器设为 0 的那一行。验证类答案也常常遗漏了重新输入数值的循环。

On test data, candidates state the type (“normal”, “boundary”) instead of giving a value, or give a value without saying whether it is accepted or rejected. On identification, only stronger candidates name a linear search; many stop at “a sorting algorithm” for a bubble sort.

在测试数据方面,考生只说出类型("正常""边界")而不给出具体数值,或者给出数值却不说明它是被接受还是被拒绝。在识别算法方面,只有较强的考生才会准确说出"线性搜索";许多考生对冒泡排序只写出"一种排序算法"就止步了。

Verification misdefined: “A verification check makes sure the data entered is correct, for example a range check.”

核实定义错误:"核实检查确保输入的数据是正确的,例如范围检查。"

✓

Precise: “Verification checks the data has not changed during entry. Double entry: the data is typed twice and the two copies are compared.”

精确:"核实检查数据在输入过程中是否发生了改变。双重输入:数据被输入两次,并比较这两份副本。"

Type, not data: “Test data: normal, abnormal and extreme.”

只有类型,没有数据:"测试数据:正常、异常和极端。"

✓

Value plus outcome: “45 (accepted, normal); 0 (rejected, boundary); 101 (rejected, boundary); 1 and 100 (accepted, extreme).”

数值加结果:"45(接受,正常);0(拒绝,边界);101(拒绝,边界);1 和 100(接受,极端)。"

Revision questions

复习题

Past-paper style. Write an answer, then reveal the marking points and mark yourself.

采用历年真题风格。写下答案,然后展开评分要点给自己打分。

Question 1 · 3 marks 第 1 题 · 3 分

[3]State the four stages of the program development life cycle used in 0478, in order, and name one task carried out in the analysis stage.

[3]按顺序陈述 0478 中使用的程序开发生命周期的四个阶段,并说出分析阶段中执行的一项任务。

Question 2 · 4 marks 第 2 题 · 4 分

[4]Give one difference between validation and verification, and describe one verification check.

[4]给出验证(validation)与核实(verification)之间的一项区别,并描述一种核实检查。

Question 3 · 5 marks 第 3 题 · 5 分

[5]A program accepts a mark from 0 to 100. Give one item each of normal, abnormal, extreme and boundary test data, stating for each whether it is accepted or rejected.

[5]某程序接受 0 到 100 之间的分数。请分别给出一项正常、异常、极端和边界测试数据,并说明每一项是被接受还是被拒绝。

Question 4 · 6 marks 第 4 题 · 6 分

[6]Write pseudocode for a range check that keeps asking for a temperature until a value from -10 to 40 inclusive is entered.

[6]编写一段范围检查的伪代码,不断要求输入温度,直到输入的数值在 -10 到 40(含两端)之间为止。

Question 5 · 4 marks 第 5 题 · 4 分

[4]Complete a trace table (columns: Total, Largest, Value, Count, Average, OUTPUT) for the algorithm below using the input data 6, 2, 9, 4, 7, and state the purpose of the algorithm.
Total ← 0 Largest ← 0 FOR Count ← 1 TO 5 INPUT Value Total ← Total + Value IF Value > Largest THEN Largest ← Value ENDIF NEXT Count Average ← Total / 5 OUTPUT Largest, Average

[4]使用输入数据 6, 2, 9, 4, 7 为下面的算法完成追踪表(列:Total、Largest、Value、Count、Average、OUTPUT),并说明该算法的目的。
Total ← 0 Largest ← 0 FOR Count ← 1 TO 5 INPUT Value Total ← Total + Value IF Value > Largest THEN Largest ← Value ENDIF NEXT Count Average ← Total / 5 OUTPUT Largest, Average

Flashcards

记忆卡片

Active recall for this topic’s key terms.

针对本主题关键术语的主动回忆练习。

Keep this topic’s practice with you

把这个主题的练习保存下来

Free account: unlock every revision question and flashcard for Topic 7, and every other IGCSE 0478 statement.

免费账户:解锁主题 7 以及所有其他 IGCSE 0478 考纲陈述的全部复习题和记忆卡片。