CAIE IGCSE CS revision - Unit 7 (2023)
如遇到公式加载异常，请刷新页面！
Unit 7 Algorithm design and problem-solving 算法设计与求解
- 大纲要求
7.1 Understand the program development life cycle, limited to: analysis, design, coding and testing 了解程序开发生命周期，限于：分析、设计、编码和测试
• Including identifying each stage and performing these tasks for each stage: 包括识别每个阶段并为每个阶段执行这些任务：
- analysis: abstraction, decomposition of the problem, identification of the problem and requirements 分析：问题的抽象、分解、问题和需求的识别
- design: decomposition, structure diagrams, flowcharts, pseudocode 设计：分解、结构图、流程图、伪代码
- coding: writing program code and iterative testing 编码：编写程序代码和迭代测试
- testing: testing program code with the use of test data 测试：使用测试数据测试程序代码
- program development life cycle：程序开发生命周期，共分五个步骤。
- Analysis：分析。
- 分析的步骤：
- Abstraction：抽象。将现实中的问题抽象成数学问题，保留关键要素，舍弃细枝末节。
- Decomposition：分解。将一个复杂的问题不断分解成更小的部分，直到能够快速解决。【参考7.2(b)】
- Identification of the problem and requirements：识别问题和要求。能够抓住问题的重点，围绕待解决问题来分析。
- 分析的步骤：
- Design：设计。
- 常用的设计方法：Structure charts结构图、Flowcharts流程图、Pseudocode伪代码等。【参考7.2(c)】
- Coding：编码。使用合适的计算机语言进行代码书写。
- Iterative testing：迭代测试。对代码进行modular tests模块化测试，修改其中的错误，然后再次测试。重复上述过程，直到程序能够按照预期的设计完成任务。
- Testing：测试。完成后的程序需要使用多组数据进行测试，查找可能被忽略的问题和代码错误。
- Maintenance：维护。已经完成的程序仍需要及时维护，如果后续发现错误，需要及时为程序进行更新或打补丁。
- Analysis：分析。
7.2 (a) Understand that every computer system is made up of sub-systems, which are made up of further sub-systems 理解每个计算机系统都是由子系统组成的，而子系统又是由进一步的子系统组成的
- Computer system：计算机系统，由多个sub-systems子系统组成。而每个子系统同样也是更小的子系统组成的，以此类推，直到子系统小到仅能完成一个简单的动作或指令。
- 注意：对计算机系统的分解过程可称为Top-down design自上而下的设计、Stepwise refinement逐步细化。
7.2 (b) Understand how a problem can be decomposed into its component parts 理解一个问题如何分解成它的组成部分
• Including: 包括：
- inputs 输入
- processes 过程
- outputs 输出
- storage 存储
- 为了将现实中的问题抽象成计算机能解决的问题，需要明确四个部分：
- 需要哪些数据来解决该问题，即input输入。
- 如何解决该问题，即process过程（或算法）。
- 需要向用户展示哪些数据和信息，即output输出。
- 需要保留哪些数据以便后续查看或继续使用，即storage存储。
7.2 (c) Use different methods to design and construct a solution to a problem 使用不同的方法来设计和构建问题的解决方案
• Including: 包括：
- structure diagrams 结构图
- flowcharts 流程图
- pseudocode 伪代码
- structure diagrams：结构图，指通过等级结构来表示如何将计算机系统拆分为子系统的图像。如下图所示：
- flowcharts：流程图，指通过一系列节点和箭头表示完成任务所需的步骤和流程的图像。
- 注意：通过流程图能够给出解决问题的algorithm算法。
- 注意：流程图的节点和箭头有通用的规定。
- 流程图的画法：
- Flow line流程线：使用箭头表示流程的下一项。如下图所示：
- Begin/End开始/结束：使用圆角矩形表示。如下图所示：
- Process过程：过程中的每个步骤使用直角矩形表示。如果是函数或过程（在别处已经定义过了），则使用双竖线矩形表示。如下图所示：
- Input/output输入/输出：使用平行四边形表示。如下图所示：
- Decision决定（选择）：使用菱形表示选择条件，并有多个附加条件的输出箭头以表示如果该条件满足的下一步的流程方向。如下图所示：
- Pseudocode：伪代码，指一种展示算法的简易写法。伪代码中的语句与高级编程语言中使用的语句非常相似，但没有严格的编程语法规定。尽管如此，伪代码仍有一些通用的写法，以便更多的人能够相互理解所书写的内容。
- Assignment statement赋值语句：使用左箭头“←”表示为变量赋值。
- 例子如下图所示：
- Assignment statement赋值语句：使用左箭头“←”表示为变量赋值。
- 算术运算符：如下图所示：
- Conditional statement条件语句-IF类型：条件可以是Boolean类型变量，也可以进行逻辑运算。结果为TRUE则执行语句1，结果为FALSE则执行语句2。
- 常见写法与例子如下图所示：
- Conditional statement条件语句-IF类型：条件可以是Boolean类型变量，也可以进行逻辑运算。结果为TRUE则执行语句1，结果为FALSE则执行语句2。
IF 条件
THEN
语句1
ELSE
语句2
ENDIF
- Conditional statement条件语句-Nested IF类型：嵌套IF类型中包括多个IF语句。
- 常见写法与例子如下图所示：
- Conditional statement条件语句-Nested IF类型：嵌套IF类型中包括多个IF语句。
IF 条件1
THEN
语句1
ELSE
IF 条件2
THEN
语句2
ELSE
语句3
ENDIF
ENDIF
- Conditional statement条件语句-CASE类型：列举所有可能的条件及满足该条件后的操作。
- 常见写法与例子如下图所示：
- Conditional statement条件语句-CASE类型：列举所有可能的条件及满足该条件后的操作。
CASE OF 变量
数值1: 语句1
数值2: 语句2
...
OTHERWISE 语句n
ENDCASE
- Iteration循环语句-FOR…NEXT类型：该循环语句适用于循环次数已知的情况。
- 常见写法与例子如下图所示：
- Iteration循环语句-FOR…NEXT类型：该循环语句适用于循环次数已知的情况。
FOR 循环变量 ← 数值1 TO 数值2
语句
NEXT 变量
- Iteration循环语句-REPEAT…UNTIL类型：该循环语句适用于循环次数未知但至少循环一次的情况。
- 常见写法与例子如下图所示：
- Iteration循环语句-REPEAT…UNTIL类型：该循环语句适用于循环次数未知但至少循环一次的情况。
REPEAT
语句
(循环变量 ← 循环变量 + 1)
UNTIL 条件
- Iteration循环语句-WHILE…DO类型：该循环语句适用于循环次数未知，可能一次也不会循环的情况。
- 常见写法与例子如下图所示：
- Iteration循环语句-WHILE…DO类型：该循环语句适用于循环次数未知，可能一次也不会循环的情况。
WHILE 条件 DO
语句
(循环变量 ← 循环变量 + 1)
ENDWHILE
- Input语句：用于输入数值。
- 常见写法与例子如下图所示：
- Input语句：用于输入数值。
INPUT 变量
- Output语句：用于输出数值。
- 常见写法与例子如下图所示：
- Output语句：用于输出数值。
OUTPUT 变量/数值/字符串
7.3 Explain the purpose of a given algorithm 解释给定算法的目的
• Including: 包括：
- stating the purpose of an algorithm说明算法的目的
- describing the processes involved in an algorithm 描述算法中涉及的过程
- Algorithm：算法，指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
- 对算法的描述：
- Purpose：目的。说明算法解决的问题。
- Progress：过程。说明算法的每个步骤。
- 描述例子如下：
- Purpose: Output the alarm sound at the appropriate time.
- Processes:
- Waiting 10 seconds.
- Getting the current time.
- Checking the current time with the alarm time.
- Outputting the alarm sound when the times match.
7.4 Understand standard methods of solution 理解标准的求解方法
• Limited to: 仅限于：
- linear search线性搜索
- bubble sort冒泡排序
- totalling总计
- counting计数
- finding maximum, minimum and average values查找最大值、最小值和平均值
- Totalling：计算所有数值的总和。
- 算法：
- 设置总和统计量并初始化为0。
- 通过循环结构，将每个数值加入总和统计量中。
- 算法：
- Counting：对数值的个数进行统计。
- 算法：
- 设置个数统计量并初始化为0。
- 通过循环结构，每读取一个数，就在个数统计量上加一。
- 算法：
- Maximum and minimum：求最大值和最小值
- 算法：
- 设置最大值统计量和最小值统计量，均初始化为0。
- 通过循环结构穷举所有数值。当有数值大于最大值统计量，则将该数值赋给最大值统计量（覆盖原数值）；当有数值小于最小值统计量，则将该数值赋给最小值统计量（覆盖原数值）。
- 算法：
- Average：求平均数
- 算法：
- 按照Totalling的算法计算出总和。
- 按照数学公式，平均数等于总和除以个数。
- 算法：
- Linear search：线性搜索
- 算法：
- 设置找到标识并初始化为FALSE。
- 通过循环结构穷举所有数值。若当前数值即为搜索数值，则找到标识赋为TURE并跳出循环；若当前数值不是搜索数值，则读取下一个数值。
- 循环完毕后，如果找到标识为TRUE，则输出数值位置；如果找到标识为FALSE，则输出未找到提醒。
- 算法：
- Bubble sort：冒泡排序（升序排列）
- 原理：比较数列中每相邻两个数值的大小，将较大的数值交换到后面。如下图所示：
- 开始第一轮检查和调整顺序。
- 检查第1个数值25和第2个数值34，上小下大，无需交换。
- 检查第2个数值34和第3个数值98，上小下大，无需交换。
- 检查第3个数值98和第4个数值7，需要交换。7成为第3个数值，98成为第4个数值。
- 检查第4个数值98和第5个数值41，需要交换。41成为第4个数值，98成为第5个数值。
- 检查第5个数值98和第6个数值19，需要交换。19成为第5个数值，98成为第6个数值。
- 检查第6个数值98和第7个数值5，需要交换。5成为第6个数值，98成为第7个数值。
- 第一轮检查和调整顺序完毕。此时最大值98已经被换到数组最下方。（每轮最多会进行n-1次交换）
- 以此类推，进行多轮检查与调整（普通冒泡排序需要进行n-1轮），数组完全按照升序排列。如下图所示：
- 算法：
- 循环结构设定为进行n-1轮调整。（外层循环）
- 每一轮最多会进行n-1次交换。（内层循环）
- 如果出现上大下小的情况，需要进行交换操作。
- 设定暂存变量。将变量A存入暂存变量内，把变量B的值赋给变量A，再把暂存变量内的值赋给变量B，完成数值交换。（类似汉诺塔的交换方式）
- 完成全部调整任务。
- 算法：
7.5 (a) Understand the need for validation checks to be made on input data and the different types of validation check 了解对输入数据进行有效性检验的必要性以及不同类型的有效性检验
• Including: 包括：
- range check范围检查
- length check长度检查
- type check类型检查
- presence check存在性检查
- format check格式检查
- check digit校验位
- the purpose of each validation check and writing algorithms to implement each validation check每个验证检查的目的和编写算法以实现每个验证检查
- Validation：有效性检验。数据在被计算机系统读取之前，需要通过一些程序来检查是否符合相关输入要求。
- range check：范围检查，用于检查数据的大小是否超过了规定的数值范围（超过上下限）。
- 算法：
- 使用循环语句穷举所有数据。
- 对每个数据使用条件语句来进行判定。如果不满足条件语句的要求，则输出错误提示。
- 算法：
- range check：范围检查，用于检查数据的大小是否超过了规定的数值范围（超过上下限）。
- length check：长度检查，用于检查数据的字符数量是否符合要求。
- 算法：使用LENGTH()函数来判断指定的字符串长度。
- length check：长度检查，用于检查数据的字符数量是否符合要求。
- type check：类型检查，用于检查输入的数据是否是指定的数据类型。
- 算法：不同的数据类型，检测方法不一样。比如可以采用仅针对该数据类型的一些计算或函数来判断。
- type check：类型检查，用于检查输入的数据是否是指定的数据类型。
- presence check：存在性检查，用于检查数据是否输入。
- 算法：使用条件语句检查数据内容是否为空，如果为空则要求重新输入。
- presence check：存在性检查，用于检查数据是否输入。
- format check：格式检查，用于检查输入的数据是否符合要求的格式。
- 算法：不同的格式，检测方法不一样。一般使用条件语句。
- check digit：校验位，指附加在数字后的附加数位，用于检查输入的数据是否有错误。
- 注意：校验位是对输入数据的检验，而不是对传输数据的准确性进行检验。【检验位的内容可参考2.2.3；传输数据的准确性检验可参考2.2.2】
- 常见例子：ISBN、barcode条形码等。
- format check：格式检查，用于检查输入的数据是否符合要求的格式。
7.5 (b) Understand the need for verification checks to be made on input data and the different types of verification check 了解对输入数据进行验证检查的必要性以及不同类型的验证检查
• Including: 包括：
- visual check视觉检查
- double entry check复式检查
- Verification：验证检查，用于检查数据是否被正确复制或输入到计算机。
- double entry check：复式检查（二次检查）。数据会被要求输入两次，有时会采用不同的输入方式。计算机会检查两次的输入，如果完全一致则通过，如果存在不一致则输出错误提示。
- 常见例子：输入两次密码
- Screen/visual check：屏幕检查或视觉检查。输入的数据会被再次显示在屏幕上，要求用户手动检查输入结果并进行确认。
- 常见例子：确认对话框
- double entry check：复式检查（二次检查）。数据会被要求输入两次，有时会采用不同的输入方式。计算机会检查两次的输入，如果完全一致则通过，如果存在不一致则输出错误提示。
7.6 Suggest and apply suitable test data 建议和应用合适的测试数据
• Limited to: 仅限于：
- normal正常
- abnormal异常
- extreme极端
- boundary边界
• Extreme data is the largest/smallest acceptable value 极端数据是最大/最小可接受值
• Boundary data is the largest/smallest acceptable value and the corresponding smallest/largest rejected value 边界数据是最大/最小可接受值和相应的最小/最大拒绝值
- Normal data：正常数据，指能够被程序接受的普通数据（非异常、极端、边界值）。
- Abnormal data：异常数据，指不符合程序要求，被程序拒绝读入（或读入后输出错误提示）的数据。
- Extreme data：极端数据，指能够被程序接受的最大和最小值（极值）。
- Boundary data：边界数据，指能够被程序接受的最大和最小值，以及和其相邻的无法被程序接受的最小和最大的值。
7.7 Complete a trace table to document a dry-run of an algorithm 完成跟踪表以记录算法的试运行
• Including, at each step in an algorithm: 在算法的每一步包括：
- variables变量
- outputs输出
- user prompts用户提示
- Trace table：追踪表，用于记录算法中每一步的结果（每个变量值的变化情况）。通过追踪表可以发现和修正程序中存在的错误。
- Dry run：干运行，指手动逐步进行算法的每次计算。
- 追踪表的例子如下图所示：
7.8 Identify errors in given algorithms and suggest ways of correcting these errors 识别给定算法中的错误并提出纠正这些错误的方法
- 算法中常见的错误包括：
- 变量名笔误（多/少字母、抄错字符等）
- 数据类型不匹配
- 结构不完整（如IF结构后面没有ENDIF等）
- 逻辑错误（死循环、缺少循环变量的变化、循环次数计算错误等）
- 标点符号错误（英文句号写成中文句号等）
- 未注意处理异常数据
7.9 Write and amend algorithms for given problems or scenarios, using: pseudocode, program code and flowcharts 为给定的问题或场景编写和修改算法，使用：伪代码、程序代码和流程图
• Precision is required when writing algorithms, e.g. x > y is acceptable but x is greater than y is not acceptable 编写算法时要求精度，例如x > y是可以接受的，但x大于y是不可接受的
• See section 4 for flowchart symbols 流程图符号见第4节
• See section 4 for pseudocode 伪代码见第4节
- 准确书写算法的方法：
- Make sure that the problem is clearly specified. 确保清楚地理解了问题。
- Break the problem down in to sub-problems. 将问题分解为子问题。
- Decide on how any data is to be obtained and stored, what is going to happen to the data and how any results are going to be displayed. 决定如何获取和存储数据、对数据的具体操作以及如何展示结果。
- Design the structure of your algorithm using a structure diagram. 使用结构图设计算法的结构。
- Decide on how to construct your algorithm, either using a flowchart or pseudocode. 决定如何构建算法（可使用流程图或伪代码）。
- Construct your algorithm, making sure that it can be easily read and understood by someone else. 构建算法，确保其可以被其他人轻松阅读和理解。
- Use several sets of test data to dry run your algorithm and show the results in trace tables, to enable you to find any errors. 使用几组测试数据试运行算法，并在跟踪表中显示结果，以便能够发现可能的错误。
- If any errors are found, correct them and repeat the process until you think that your algorithm works perfectly. 如果发现任何错误，需要立即修正，并重复上述过程，直到认为算法完美运行为止。