CAIE AS and A Level CS revision - Unit 9 (2nd)
如遇到公式加载异常，请刷新页面！
Unit 9 Algorithm Design and Problem Solving 算法设计与问题解决
9.1 Computational Thinking Skills 计算思维能力
- 大纲要求
9.1.1 Show an understanding of abstraction 展示对抽象的理解
Need for and benefits of using abstraction 使用抽象的需要和好处
Describe the purpose of abstraction 描述抽象的目的
Produce an abstract model of a system by only including essential details 通过仅包含基本细节来生成系统的抽象模型
- Computational thinking：计算思维，包含五个部分：abstraction抽象、decomposition分解、data modelling数据建模、pattern recognition模式识别和algorithm design算法设计。
- data modelling：数据建模，指通过抽象的数据类型来模拟现实世界中的情况。
- pattern recognition：模式识别，指寻找问题的解决方案并用这些方案来有效处理问题。
- 其余的部分见下。【参考9.1.1、9.1.2、9.2】
- Abstraction：抽象。通过简化、符号化，将现实问题转化为数学、计算机等理论问题。
- 抽象可以去除掉对问题研究影响不大的各类因素，仅保留对研究对象有较大影响的部分，突出问题关键，更容易得出研究结果。
- 抽象可以简化现实，降低复杂性，便于研究。
- 算法就是对现实情况的抽象，通过输入、一系列指令和输出来解决问题。
9.1.2 Describe and use decomposition 描述和使用分解
Break down problems into sub-problems leading to the concept of a program module (procedure / function) 将问题分解为子问题，形成程序模块（过程/函数）的概念
- Decomposition：分解。思考问题时应善于将问题分解成多个sub-problems子问题，逐个解决，最后结合在一起。程序中的函数、过程模块都是运用了该思想。
9.2 Algorithms 算法
- 大纲要求
9.2.1 Show understanding that an algorithm is a solution to a problem expressed as a sequence of defined steps 理解算法是问题的解决方案，表示为一系列定义的步骤
- Algorithms：算法，指使用结构化的语句编写的流程步骤，按照流程顺序进行，将能够解决相关问题。
- 常用的算法表述方法：
- Structured English：结构性语言，由一系列命令式语句构成。虽然结构组织上像程序代码，但语句表达近似于自然语言，方便易懂。
- Pseudocode：伪代码，结构组织和语句表达均近似于程序代码，但不遵循特定计算机语言的语法规则（类似于表达思路的通用代码）。
- Flowchart：流程图，通过一系列特定形状的对象和其前后关系来表达算法的步骤。
- 算法的基本结构类型：
- Assignment：赋值。将数值赋予identifier标识符或修改标识符对应的数值。
- Sequence：顺序。一步一步按顺序执行命令语句。
- Selection：选择。在两个或多个选项中做出选择，满足相关条件则执行对应的命令语句。
- Repetition（iteration/looping）：重复（迭代/循环）。反复执行某些命令语句。
- 使用算法的不同表述方式来表示算法的各类基本结构：
9.2.2 Use suitable identifier names for the representation of data used by a problem and represent these using an identifier table 使用合适的标识符名称来表示问题使用的数据，并使用标识符表来表示这些
- Variable：变量，指拥有标识符的数据存储位置。当读入数据时，数据将被存储在变量所指向的地址。
- 标识符应当遵循易读易记的原则，尽量使用能够表达其变量用途的名称。标识符名称中不能含有空格，只能由字母、数字和下划线“_”组成。
- Identifier table：标识符表，用于罗列使用的变量及其解释。比如：
9.2.3 Write pseudocode that contains input, process and output 编写包含输入、处理和输出的伪代码
- input输入：
INPUT 变量名
- assignment赋值：
变量名 ← 数值 //伪代码中使用“←”表示赋值，使用等号表示相等
- update修改数值：
变量名 ← 变量名 + 数值
- copy复制数值：
变量名2 ← 变量名1
- swap交换数值：
Temp ← 变量名1 //Temp是临时变量，暂时寄存变量1的值
变量名1 ← 变量名2
变量名2 ← Temp
- output输出：
OUTPUT 变量名
9.2.4 Write pseudocode using the three basic constructs of sequence, selection and iteration (repetition) 使用序列、选择和迭代（repetition）这三种基本结构编写伪代码
- Sequence顺序结构：按照语句顺序排列即可。大部分的程序代码都含有顺序结构。
- Selection选择结构：表达从多个选项中选择一项进行的结构，以含有IF…ELSE…的语法结构为代表。
IF 条件
THEN //如果条件满足，则执行指令1
<指令1>
ELSE //如果条件未满足，则执行指令2
<指令2>
ENDIF
- 在选择结构的条件中常用的表示比较关系的符号如下表所示：
- 特别需要注意大于等于、小于等于和不等于这三个符号的伪代码表达式。
- 如果在IF语句中再使用IF语句，则构成nested IF statements嵌套IF语句。
IF 条件
THEN
<指令1>
ELSE
IF 条件 //嵌套IF语句。可多层嵌套，但程序可读性降低。
THEN
<指令2>
ELSE
<指令3>
ENDIF
ENDIF
- 嵌套IF语句可以通过改写，转为单一IF语句。
- 单一IF语句的优点：可读性强；新增数据和变量时，算法调整更加容易。
- 单一IF语句的缺点：有些变量不能进行实时同步，如果手动忘记修改，则会造成计算出错。
- Iteration (repetition)迭代循环结构：反复使用某些指令语句，常见的循环结构包括REPEAT…UNTIL…、FOR…NEXT…和WHILE…ENDWHILE…三种。
- REPEAT…UNTIL…：
REPEAT
（变量名 ← 变量名 + 1） //如果循环需要完成规定轮数，则必须加该条件
<重复操作指令>
UNTIL 循环结束条件
- FOR…NEXT…：
FOR 变量名 ← 起始值 TO 终值 STEP 步长 //如果是降序，则使用DOWNTO。STEP+步长是选填项。步长为等差量，如果不填则默认为1（降序则为-1）。
<重复操作指令>
NEXT 变量名
- WHILE…ENDWHILE…：
WHILE 循环进行条件 DO
<重复操作指令>
（变量名 ← 变量名 + 1） //如果循环需要完成规定轮数，则必须加该条件
ENDWHILE
- 循环可以多层嵌套，构成nested loop。
9.2.5 Document a simple algorithm using pseudocode Write pseudocode from: 使用伪代码记录一个简单的算法
- 【参考9.2.3和9.2.4】。
9.2.6 从以下位置编写伪代码：
a structured English description 结构化的英文描述
a flowchart 流程图
- 【参考9.2.1】。
9.2.7 Describe and use the process of stepwise refinement to express an algorithm to a level of detail from which the task may be programmed 描述和使用逐步细化的过程来将算法表达到可以对任务进行编程的详细程度
- Stepwise refinement：逐步细化，指为了解决复杂问题，可以将该问题拆分成更小的步骤，直到这些步骤小到可以轻松解决。
- 对编程问题，一般会拆分成sequence顺序、assignment赋值、selection选择、repetition循环、input输入和output输出等步骤。
9.2.8 Use logic statements to define parts of an algorithm Solution 使用逻辑语句定义算法的各个部分
- Module：模块，指将程序细化后形成的功能块，每个功能块完成一个特定的任务。模块包括procedure过程和function函数。
- Procedure：过程，指一系列指令形成的功能块。该功能块会有identifier标识符的命名，如果在程序中用到这些指令，则通过引用identifier标识符即可调用这个功能块。identifier标识符的命名要求与变量标识符一致。【参考9.2.2】
- Procedure过程的构建：
- Procedure：过程，指一系列指令形成的功能块。该功能块会有identifier标识符的命名，如果在程序中用到这些指令，则通过引用identifier标识符即可调用这个功能块。identifier标识符的命名要求与变量标识符一致。【参考9.2.2】
PROCEDURE 过程名(参数列表) //参数列表的写法为“BYREF 参数 : 数据类型”或“BYVALUE 参数 : 数据类型”。BYREF代表传递的是参数地址，BYVALUE代表传递的是值
<操作指令>
ENDPROCEDURE
- Procedure过程的引用：
CALL 过程名(变量名1, 变量名2…)
- Function：函数，指一系列指令形成的功能块，执行结束会返回一个值。该功能块会有identifier标识符的命名，如果在程序中用到这些指令，则通过引用identifier标识符即可调用这个功能块。调用时，函数需要赋值给相应变量。identifier标识符的命名要求与变量标识符一致。【参考9.2.2】
- Function函数的构建：
- Function：函数，指一系列指令形成的功能块，执行结束会返回一个值。该功能块会有identifier标识符的命名，如果在程序中用到这些指令，则通过引用identifier标识符即可调用这个功能块。调用时，函数需要赋值给相应变量。identifier标识符的命名要求与变量标识符一致。【参考9.2.2】
FUNCTION 函数名 (参数列表) RETURNS 数据类型 //参数列表的写法为“参数 : 数据类型”。主程序中被赋值变量的数据类型应该与函数中定义的数据类型一致
<操作指令>
RETURN 变量名 //将该变量对应的数值赋给主程序中引用该函数的变量
ENDFUNCTION
- Function函数的引用：
变量名 ← 函数名(变量名1, 变量名2…)
- 注意：过程与函数均应能够独立运行，即不应当依赖于外部的变量。所有内部的变量值都需要通过arguments参数的形式由外部传递给内部。
- Argument：参数（实参），指在程序中实际输入的值，将会由外部的程序通过参数列表的形式传递给过程或函数内部以使用。
- Parameter：参数（形参），指过程或函数内部的变量，使用范围仅限于其内部。程序里，通常会按照过程或函数的参数列表顺序，将数值或变量名写在调用过程或函数的标识符后的括号里。
- Local variable：局部变量，指仅能在某个过程或函数内部使用的变量。
- Global variable：全局变量，指在所有模块内部均能使用的变量。
- 注意：过程与函数均应能够独立运行，即不应当依赖于外部的变量。所有内部的变量值都需要通过arguments参数的形式由外部传递给内部。