CAIE AS and A Level CS revision - Unit 20 (2nd)

【点此返回复习要点目录】

如遇到公式加载异常，请刷新页面！

Unit 20 Further Programming 进一步编程

20.1 Programming Paradigms 编程范式

• 大纲要求

20.1.1 Understanding what is meant by a programming paradigm 理解编程范式的含义

• programming paradigm：编程范式，指一种基本的编程风格。不同的范式有不同的编程思维方式和解决问题方式。
  • 常见的一些编程范式包括：low-level programming paradigm低级编程范式、imperative programming paradigm命令式编程、object-oriented programming paradigm面向对象式编程、declarative programming paradigm声明式编程等。

20.1.2 Show understanding of the characteristics of a number of programming paradigms: 表现出对多种编程范式特征的理解：

low-level 低级
· Low-level Programming: 低级编程：
· · understanding of and ability to write low-level code that uses various addressing modes: immediate, direct, indirect, indexed and relative 理解和编写使用各种寻址模式的低级代码的能力：立即、直接、间接、索引和相对
Imperative (Procedural) 命令式（程序式）
· Imperative (Procedural) programming: 命令式（过程式）编程：
· · Assumed knowledge and understanding of Structural Programming  假定了解和理解结构化编程
· · understanding of and ability to write imperative (procedural) programming code that uses variables, constructs, procedures and functions. 理解和编写使用变量、构造、过程和函数的命令式（过程）编程代码的能力。
Object Oriented 面向对象
· Object-Oriented Programming (OOP): 面向对象编程（OOP）：
· · understanding of the terminology associated with OOP (including objects, properties, methods, classes, inheritance, polymorphism, containment (aggregation), encapsulation, getters, setters, instances) 理解与OOP相关的术语（包括对象、属性、方法、类、继承、多态、包含（聚合）、封装、getter、setter、实例）
· · understanding of how to solve a problem by designing appropriate classes 了解如何通过设计适当的类来解决问题
· · understanding of and ability to write code that demonstrates the use of OOP 理解和编写演示 OOP 使用的代码的能力
·Declarative 声明式
· Declarative programming: 声明式编程：
· · understanding of and ability to solve a problem by writing appropriate facts and rules based on supplied information 通过根据提供的信息编写适当的事实和规则来理解和解决问题的能力
· · understanding of and ability to write code that can satisfy a goal using facts and rules 理解和编写能够使用事实和规则实现目标的代码的能力

• low-level programming paradigm：低级编程范式，指可以直接操作内存和寄存器、利用处理器结构等的编程语言，比如x86 instruction set指令集。不同类型的处理器使用不同的编程语言（同一品牌体系下的处理器可能会采用类似的编程语言）。
  • 常用的低级编程语言指令表：

• • • 说明：
• ACC指Accumulator累加器。
• IX指Index Register指数寄存器。
  1. 指immediate addressing立即数寻址（后面直接加数字）
• B代表binary number二进制数字（B后方的数字为二进制表示）
• &代表hexadecimal number十六进制数字（&后方的数字为十六进制表示）
• <address>可以指absolute address绝对地址或symbolic address符号地址。

• • Symbolic address：符号地址，指使用类似高级编程语言变量名的标识符来指代数据存储的地址。使用符号地址编写代码，简单易懂，且比使用直接地址要更容易修改相应语句。

• • 使用低级语言代码进行操作：
    • assignment赋值：

Pseudocode examples	Assembly code examples	Explanation
A ← 34	LDM #34 STO A	将十进制数34导入ACC中 将ACC中的值存入A所在的地址
B ← B + 1	LDD B INC ACC STO B	将B所在地址内的数值加载入ACC ACC中的数值加1 将ACC中的值存入B所在的地址
B ← B + A	LDD B ADD A STO B	将B所在地址内的数值加载入ACC 将A所在地址中的数值加到ACC中 将ACC中的值存入B所在的地址
A ← -A	LDD A XOR #&FF INC ACC STO A	将A所在地址内的数值加载入ACC 将ACC中的值与十六进制数FF（即二进制数11111111）取异或值，获得原数值的反码 ACC中的数值加1，获得原数值的补码（即-A） 将ACC中的值存入A所在的地址
A ← -A	或采用： LDM #0 SUB A STO A	将十进制数0导入ACC中 将ACC中的值减去A所在地址内的数值 将ACC中的值存入A所在的地址

• • • selection选择结构：

Pseudocode examples	Assembly code examples	Explanation
IF A = 0   THEN    B ← B + 1 ENDIF	LDD A 　　　 CMP #0 　　　 JPN ENDIF THEN: LDD B 　　　 INC ACC 　　　 STO B ENDIF: ...	将A所在地址内的数值加载入ACC 将ACC中的数值与0相比较 如果为FALSE（不相等）则跳转至ENDIF（如果为TRUE相等则正常向下进行） 将B所在地址内的数值加载入ACC ACC中的数值加1 将ACC中的值存入B所在的地址 结束IF结构
IF A = B   THEN    OUTPUT "Y"   ELSE    OUTPUT "N" ENDIF	LDD A 　　　 SUB B 　　　 CMP #0 　　　 JPN ELSE THEN: LDM #89 　　　 OUT 　　　 JMP ENDIF ELSE: LDM #78 　　　 OUT ENDIF: ...	将A所在地址内的数值加载入ACC 将ACC中的值减去B所在地址内的数值 将ACC中的数值与0相比较 如果为FALSE（不相等）则跳转至ELSE（如果为TRUE相等则正常向下进行） 将十进制数89导入ACC中 输出ACC中的数值对应的ASCII值“Y” 跳转至ENDIF 将十进制数78导入ACC中 输出ACC中的数值对应的ASCII值“N” 结束IF结构

• • • repetition循环结构：

Pseudocode examples	Assembly code examples	Explanation
A = 0 REPEAT    OUTPUT "*"    A ← A + 1 UNTIL A = 5	LDM #0 　　　 STO A LOOP: LDM #42 　　　 OUT 　　　 LDD A 　　　 INC ACC 　　　 STO A 　　　 CMP #5 　　　 JPN LOOP	将十进制数0导入ACC中 将ACC中的值存入A所在的地址 执行循环：将十进制数42导入ACC中 输出ACC中的数值对应的ASCII值“*” 将A所在地址内的数值加载入ACC ACC中的数值加1 将ACC中的值存入A所在的地址 将ACC中的数值与5相比较 如果为FALSE（不相等）则跳转至LOOP（如果为TRUE相等则正常向下进行）

• • • input/output输入/输出：

Pseudocode examples	Assembly code examples	Explanation
INPUT A	IN 　　　 STO A	从键盘读取一个字符，并将ASCII码存入ACC 将ACC中的值存入A所在的地址
OUTPUT B	LDM #-1 　　　 MOV IX LOOP: INC IX 　　　 LDX B 　　　 OUT 　　　 CMP #13 　　　 JPN LOOP	将十进制数-1导入ACC中 将ACC中的数值移入指数寄存器 执行循环：指数寄存器中的数值加1 将“B所在地址号+寄存器内数值”所在地址内的数值加载入ACC（寄存器内的数值是相对于B的地址偏移量） 输出ACC中的数值对应的ASCII值 将ACC中的数值与13相比较（13代表回车符对应的ASCII码） 如果为FALSE（不相等）则跳转至LOOP（如果为TRUE相等则正常向下进行）
INPUT A	LDM #-1 　　　 MOV IX LOOP: INC IX 　　　 IN 　　　 STX A 　　　 CMP #13 　　　 JPN LOOP	将十进制数-1导入ACC中 将ACC中的数值移入指数寄存器 执行循环：指数寄存器中的数值加1 从键盘读取一个字符，并将ASCII码存入ACC 将ACC中的值存入“A所在地址号+寄存器内数值”所在地址（寄存器内的数值是相对于A的地址偏移量） 将ACC中的数值与13相比较（13代表回车符对应的ASCII码） 如果为FALSE（不相等）则跳转至LOOP（如果为TRUE相等则正常向下进行）

• • Absolute addressing：绝对寻址，即在指令格式的地址的字段中直接指出操作数在内存的地址（即内存中用数值表示的地址）。
    • 注意：使用绝对寻址的程序容易分辨存储位置，且不占原有分配地址；但程序不能将数据加载到除指定地址之外的地方，编程灵活度较差。
  • Relative addressing：相对寻址，即以执行完当前指令后的程序计数器中的数值为基址，以操作码后面的数值为地址偏移量，将基址与地址偏移量之和作为地址赋予程序计数器，程序计数器则跳到该地址来执行此地址单元的内容。
    • 注意：相对寻址可节省指令中的地址位数，也便于程序在内存中成块搬动。
  • 绝对寻址和相对寻址的例子：如下图所示。

• • Indirect addressing：间接寻址，是将数组和指针结合起来的一种方法，数组中存储数据元素的单元是指向该元素的指针。
    • 运用间接寻址进行队列操作的例子：

Instruction			Explaination
Label	Op code	Operand
JOINQ: （队列加数据）	STI	TAILPTR	将ACC中的数值存入TAILPTR尾指针指向的地址中（间接寻址）
	LDD	TAILPTR	将TAILPTR所在地址内的数值加载入ACC
	INC	ACC	ACC中的数值加1
	STO	TAILPTR	将ACC中的值存入TAILPTR所在的地址
	JMP	ENDQ	跳转至ENDQ
LEAVEQ: （队列删数据）	LDI	HEADPTR	将HEADPTR头指针指向的地址中的数值加载入ACC中（间接寻址）
	OUT		输出ACC中的数值对应的ASCII值
	LDD	HEADPTR	将HEADPTR所在地址内的数值加载入ACC
	INC	ACC	ACC中的数值加1
	STO	HEADPTR	将ACC中的值存入HEADPTR所在的地址
	JMP	ENDQ	跳转至ENDQ
ENDQ:			结束操作
HEADPTR:	QSTART		头指针
TAILPTR:	QSTART		尾指针
QSTART:	""		队列初始为空

• imperative programming paradigm：命令式编程，指将程序编写为一系列明确的命令式语言交由处理器运行，相当于告诉计算机如何一步步得到结果。常见的例子包括Pascal、C、Basic等语言。

• object-oriented programming paradigm：面向对象式编程，指以对象（即数据结构）作为基本程序结构单位的程序设计语言。许多命令式编程语言已经被进一步开放成面向对象式编程，比如Pascal (Delphi or Object Pascal)、Visual Basic等，新出现的语言很多直接是面向对象式编程，比如Python、Java等。
  • class：类，指一种用户自定义的数据类型，包含着数据结构和对数据结构进行操作的methods方法，是对记录的事物的抽象，可以看成是一个“模板”。
    • attribute：属性，指class类中的数据项，有时也可称为field字段，是对象的固有特征。属性是private私有的，意味着不能通过直接访问数据地址来修改，只能通过method方法来操作它。因此，属性不会受到意外更改这类影响。
    • method：方法，指class类中的子程序，用来访问attribute属性。方法是public公开的。
  • object：对象，指现实世界的实体或概念在计算机逻辑中的抽象表示，是class类的instantiation实例化（即根据模板创建了一个描述现实中实体的数据结构）。
    • encapsulation：封装，指将对象的属性和方法结合起来。

• • 设计类与对象：
    • Constructor：构造函数，指创建一个新的object对象并将其attribute属性初始化的method方法。
    • Getter：获取方法，指获取对应属性的属性值的方法。
    • Setter：赋值方法，指设定或修改对应属性的属性值的方法。
    • Property：性质，包含着attribute属性和与之相关的getter和setter方法。
    • 关于class类中的属性与方法的示意图如下所示：（以Set开头的是setter方法，以Get开头的是getter方法）

• • 编写面向对象代码：
    • 声明class类（使用普通的attribute属性和setter、getter方法）：

• • • 声明class类（使用property性质）：

• • • class类的instantiation实例化（创建对象）：

• • • 使用method方法对对象进行操作：

• • Inheritance：继承。面向对象语言可以只设计一个class类（称为base class基类或superclass超类），然后从中衍生出来众多subclass子类。子类可以利用基类的属性和方法，并增加一些子类自身独有的属性和方法。
    • 完全继承的子类：和基类的属性、方法完全一致。其示意图如下：

• • • 含有独有属性和方法的子类：除了包含基类的属性、方法之外，还有一些属于该子类独有的属性和方法。其示意图如下：

• • • Abstract class：抽象类，指虽然是base class基类，但从没有直接对象实例化情况的类。（具体的数据都是根据其子类进行对象实例化）

• • • 基类与子类的设计（例子）：
      • 图书馆中可供外接的有图书和CD两类资源，每类的属性如下表所示：

• • • • 注意到除了最后一行，其余所记录的属性基本一致，因此可考虑将前五条属性设计为base class基类，最后一行属性设计为含有独有属性和方法的子类，其设计图如下所示：

• • • • 将具体属性和方法填入类中，其设计图如下所示：（注意到这里LibraryItem就是抽象类，因为所有的具体对象都会按照Book或者CD两类来进行实体化）

• • • 编写设计和使用基类与子类的代码：
      • 声明基类与子类（使用普通的attribute属性和setter、getter方法）：

• 声明基类与子类（使用property性质）：

• 对象实例化：

• • • Polymorphism：多态化，指在子类中重新定义与基类中方法同名的方法，但该方法与基类中的同名方法执行后的结果可能不同。（比如在原基类方法中再增加一些操作等）
      • 多态化的例子：在基类PrintDetails的基础上再输出子类Book当中的独有属性。操作代码如下：

• • Containment：包含，也称为aggregation。子类是基类中的一部分。比如基类是车，子类是车轮、引擎、车外壳等。其设计示意图如下所示：

• • • 下图中，Course类中包含了Lesson子类和Assessment子类，基类中会访问到两个字类：

• • Garbage collection：“垃圾处理”，指对不再使用的内存单元进行处理和释放。不断创建对象时需要占用内存，如果不及时处理并释放掉不需要的内存，则可用内存会越来越少，程序最终会无内存空间可用，导致出错，该错误称为memory leakage内存泄露。
    • 各类程序语言处理不再使用的内存的方式：

• declarative programming paradigm：声明式编程，指编程者描述目标的性质，让计算机明白目标而非流程的程序语言。常见的例子包括SQL、Prolog等。
  • Prolog的基本构成：fact事实、rule规则和query查询。
    • Prolog中的程序逻辑靠clause子句（即事实与规则）实现，通过查询解决问题。
    • Knowledge base：知识库，指一系列子句的集合。
    • Term：项，指Prolog中唯一的数据类型。以下的情况均可作为项：
      • Atom：原子，指以小写字母开头的没有实际含义的名字。
      • Number：数字（integer整型或real实型）。
      • Variable：变量，指以大写字母或下划线“_”开头的标识符。
      • Predicate：谓词，指Prolog中内置或用户自定义的关系。
      • Compound term：复合项，指包含上述多个种类项的项。
      • Argument：参数，指跟在谓词后面括号中的项。
  • Clause子句的结构：

Head:- Body.

• • • 注意：
      • Head目标和Body主体分别代表一些语句。
      • “:-”代表IF如果。如果Body部分的语句是TRUE，则Head部分语句的运行结果为TRUE。
      • “,”代表AND并运算。
      • 子句的结尾必须是“.”。
      • Prolog区分大小写。
  • 关于Fact事实：指没有body主体的子句。如下例所示：

capitalCity(paris).
capitalCity(berlin).
capitalCity(cairo).

• • • 说明：
      • capitalCity(paris)是复合项，capitalCity和paris都是atom原子。其中capitalCity是谓词，paris是参数。
      • capitalCity拥有一个参数，写作capitalCity/1。
      • 上述facts事实组成了一个knowledge base知识库，后续可通过查询来解决相关问题。

• • 关于variable变量：指使用大写字母开头的标识符，在查询中可以查到多个合适的值并进行输出。
    • 例子：
      • 假设有以下知识库：

cityInCountry(paris, france).
cityInCountry(berlin, germany).
cityInCountry(cairo, egypt).
cityInCountry(munich, germany).

• • • • 如果想查询德国有哪些城市，则可以使用如下语句：

cityInCountry(City, germany).

• • • • • 注意：这里的City是大写字母开头，因此是variable变量。通过查询知识库，程序会给出berlin的查询结果。当存在更多可能性时，需要在给出的结果后手动输入“;”，Prolog会给出下一个可能的结果，即munich。
    • Anonymous variable：匿名变量，指不感兴趣的变量（无需查询该部分），在代码中用“_”表示。比如如下语句：

ingredient(tagine, Ingredient, _ ).

• • • • 注意：这里并不关心最后一个变量Amount，因此用“_”代替。

• • 关于rule规则：指对目标进行判断的标准。
    • 例子：假设有以下知识库：

parent(fred, jack).
parent(fred, alia).
parent(fred, paul).
parent(dave, fred).

• • • • 如果要判定爷孙关系，则可以将该规则写成：

grandparent(G, S) :- parent(G, P), parent(P, S). /*如果G是P的父辈，且P是S的父辈，则G和S是爷孙关系。*/

• • • • 如果要判定兄弟姐妹关系，则可以将该规则写成：

sibling(A, B) :-
　 parent(P, A),
　 parent(P, B),
　 not(A=B). /*如果P是A的父辈，且P是B的父辈，且A与B不是一个人，则A和B是兄弟姐妹关系。*/

• • Instantiation：实例化，指运行查询后得到的具体结果。
    • 比如当运行查询后，Prolog返回X=stew的结果。“=”符号此处是实例化的意思，意味着找到了一个具体的对象，而非赋值的含义。

• • Backtracking：回溯，指追踪Prolog程序寻找合适的对象的过程。在实际操作中，通过输入trace指令进入追踪过程。（可使用debugger窗口或在主窗口追踪）示意图如下：

• • • 追踪时的术语解释：
      • Call：初次进入一个谓词。
      • Creep：程序进入下一个谓词。
      • Exit：成功返回。
      • Redo：在同一个谓词范围内，进入下一个可能的对象。
      • Fail：没有找到合适的对象。

• • Recursion：递归。声明式编程也存在递归运算，且和命令式编程的递归要求一致，即要有base case基本情况、general case一般情况并且必须能在有限次数内达到基本情况。
    • 例子：判断二人是否存在血缘关系（祖先关系）。其rule规则如下：

ancestor(A, B) :- parent(A, B). /*基本情况*/
ancestor(A, B) :- parent(A, X), ancestor(X, B). /*一般情况*/

• • List：列表，指一系列项的有序集合，由中括号“[ ]”集合在一起。任何类型的数据都可以集合在同一个列表中。
    • Head：列表的头部，指列表中的第一项。
    • Tail：列表的尾部，指列表中第一项后的列表内容，也是一个列表形式。
    • 对列表头部和尾部的拆分使用“|”来表示。比如以下例子：

showHeadAndTail([fred, jack, emma], Head, Tail). /*输出列表[fred, jack, emma]的头部和尾部*/

输出结果如下：
Head = fred, /*头部是列表中的第一项*/
Tail = [jack, emma]. /*尾部是除第一项以外的剩余列表内容*/

• • • 空列表是中括号“[ ]”之中没有任何项的列表，可用如下规则表示：

emptyList(A) :- A = [].

• • • 列表的常见谓词使用：
      • append：列表的合并，属于内置谓词。其用法如下：

append(A, B, C). /*将A列表与B列表合并为C列表。其中A、B、C列表均可成为用户需求的目标*/

• • • • • 例子：

append([a, b], [c, d], MyList).

输出结果为：
MyList = [a, b, c, d]. /*将前面A、B位置两个列表内的项全部合并*/

append(FirstList, [c, d], [a, b, c, d]).

输出结果为：
FirstList = [a, b]. /*从C位置列表的项中，去除B位置列表中的项，可得A位置列表的各项*/

• • • • member：检查某项是否属于该列表内的项，属于内置谓词。其用法如下：

member(A, [List]).

• • • • • 例子：

member(c, [a, b, c, d, e]).

输出结果为：
true. /*判断c是否位于后面提供的列表中，结果为TRUE，代表在列表中*/

member(X,[a, b, c, d]).

输出结果为：
X = a;
X = b;
X = c;
X = d. /*变量X位于列表中，求X。可能性包括a、b、c、d四种，通过输入;来获得输出*/

• • • • write：输出，属于内置谓词。其用法如下：

write(…). /*…为要输出的内容，可以是以’’括起来的字符串，也可以是变量*/

• • • • • 例子：

write('message: ').

输出结果为：
message:

write(X). /*输出结果为当前存放于变量X中的实例*/

• • • • read：输入，属于内置谓词。其用法如下：

read(…). /*…为变量名，从键盘中读取的内容会成为该变量的当前实例。*/

• • • • • 注意：
          • 输入值必须以小写字母开头，不能带空格或被引号括起来。
          • nl代表下一次的输出转到新行。
        • 例子：

read(Name). /*从键盘中读取的内容会成为变量Name的当前实例*/

• • • • assert(…)：断言，将指定的clause子句作为参数加入knowledge base知识库中。
      • retractall(…)：撤销，将指定的clause子句从knowledge base知识库中撤出。

20.2 File Processing and Exception Handling 文件处理与异常处理

• 大纲要求

20.2.1 Write code to perform file-processing operations 编写代码来执行文件处理操作

Open (in read, write, append mode) and close a file 打开（以读、写、追加模式）和关闭文件
Read a record from a file and write a record to a file 从文件中读取一条记录，向文件中写入一条记录
Perform file-processing operations on serial, sequential, random files 对串行、顺序、随机文件执行文件处理操作

• 关于文件操作的伪代码：

• 对sequential file顺序文件的打开、关闭、读取、写入文件操作：
  • 伪代码：

• • 程序语言：

• 对random-access file随机访问文件的打开、关闭、读取、写入文件操作：
  • random-access file：随机访问文件，指通过哈希函数计算存储地址，可以直接对数据进行读取、写入操作而无需借助数组结构的文件。
  • 伪代码：

• • 程序语言：

20.2.2 Show understanding of an exception and the importance of exception handling 展示对异常的理解和异常处理的重要性

Know when it is appropriate to use exception handling 知道什么时候适合使用异常处理
Write program code to use exception handling 编写程序代码使用异常处理

• exception handling：异常处理，指如果程序中出现异常（运算错误、数据不存在等），则执行另一个操作以避免程序崩溃。
  • 重要性：避免程序崩溃。
• 常见的一些异常错误：
  • Python中的一些错误类型：
    • IOError：输入或输出过程出现错误（比如找不到要读取的文件）
    • ImportError：找不到module模块
    • ValueError：参数值错误
    • KeyboardInterrupt：用户按下了Ctrl+C或Ctrl+Del（中断键）
    • EOFError：从文件中未读取到任何数据就遇到了文件结束条件EOF。
    • ZeroDivisionError：程序中的计算企图除零（零成为分母）
  • Java中的一些错误类型：
    • IOException：输入或输出过程出现错误（比如找不到要读取的文件）
    • ArithmeticException：发生算术错误（比如程序中的计算企图除零）
    • ArrayIndexOutOfBoundsException：程序企图访问超过边界的数组元素

• 异常处理的操作：
  • 伪代码：

TRY
　　程序代码A //此处是正常运行时的代码
EXCEPT
　　程序代码B //如果程序代码A在运行时出现了错误，则运行程序代码B（这里可以有多个EXCEPT模块以应对不同种类的错误）
ENDTRY

• • 程序语言：