跳到主要内容

程序设计

A-Level 计算机科学 · 第 11 主题

训练
11.1

编程基础

大纲
Candidates should be able to: Notes and guidance
Implement and write pseudocode from a given design presented as either a program flowchart or structured English
Write pseudocode statements for: • the declaration and initialisation of constants • the declaration of variables • the assignment of values to variables • expressions involving any of the arithmetic or logical operators input from the keyboard and output to the console
Use built-in functions and library routines Any functions not given in the pseudocode guide will be provided String manipulation functions will always be given

来源:剑桥国际大纲

深色屏幕上的一行行源代码
编程把一个设计变成写成代码的指令
一个程序员在电脑前工作
一个程序员写代码并随手测试它

From design to code

你应当能够把一个设计——一张流程图(flowchart,程序流程图)或结构化英语(structured English)——变成伪代码(pseudocode),然后变成一门真实的语言:

  1. 找出变量(variables)及其数据类型(data types)。
  2. 把输入/输出框变成 INPUT / OUTPUT
  3. 把判断菱形变成 IF...ELSE...ENDIF(或 CASE)。
  4. 把循环箭头变成 WHILEREPEAT...UNTILFOR
  5. 把处理框变成赋值或计算。
  6. 通过追踪一个小输入来检查。
一个从流程图符号到伪代码的映射:一个输入/输出平行四边形变成 INPUT 或 OUTPUT,一个判断菱形变成 IF...THEN 或 CASE,一个处理框变成一个赋值 x = expression,而一个循环箭头变成 WHILE、FOR 或 REPEAT
每个流程图符号变成一个伪代码关键字

Constants and variables

一个常量(constant)容纳一个从不改变的值;一个变量容纳一个可能改变的值。用一个类型声明它们:

一个变量的值可以改变;一个常量保持固定
一个变量的值可以改变;一个常量保持固定
CONSTANT Pi ← 3.14159
DECLARE Radius : REAL
DECLARE Area : REAL

Radius ← 5
Area ← Pi * Radius * Radius

对反复出现的固定值用常量(PiMaxScore);它们使代码更清晰,并且易于在一处改变。

在考试中,常量是"指出一种更合适的表示方式"这类题的答案:一个固定值,例如税率或最高分,在伪代码的好几处出现。评分标准列出的好处:该值只设定一次,不会被程序意外改变;修改只需在一处进行,并作用于每一条使用它的语句;标识符赋予该值一个含义(MaxScore 而不是 100),所以代码更易读、更易检查;而且像 3.14159 这样的长数值打错的风险更小。"说出一个可以用常量代替的值"这类题要的是伪代码里的字面值(0.240),而不是一个新名字。

每个变量在使用之前只声明一次,带一个标识符(identifier,即它的名字)和一个数据类型。9618 伪代码指南中的六种类型:

类型 存放 在代码中写成 典型用途
INTEGER 整数 42-3 计数、数组下标、循环计数器
REAL 带小数部分的数 3.75 价格、平均值
CHAR 一个字符 'A'(单引号) 等级字母、菜单按键
STRING 一串字符 "Hello"(双引号) 姓名、邮政编码
BOOLEAN TRUEFALSE TRUE Found 这样的标志
DATE 一个日历日期 12/05/2026 出生日期

"给出合适的数据类型"这类题目要从变量在伪代码中怎样被使用来回答:带小数点的值是 REAL;被赋为 TRUEFALSE 的是 BOOLEAN;单引号里的值是 CHAR;用作数组下标、或与 DIVMOD 一起用的值是 INTEGER。类型用大写字母写,拼写与指南一致。

例题。 说出每个变量合适的数据类型。

Found ← FALSE
Initial ← 'K'
Price ← 12.99
Count ← Count + 1
Name ← "Li Wei"

FoundBOOLEAN(它存放 FALSE);InitialCHAR(单引号里的一个字符);PriceREAL(一个小数值);CountINTEGER(一个每次加一的计数器);NameSTRING(双引号里的文本)。

Assignment and expressions

表示赋值(assignment):

Total ← Total + 1
Average ← Sum / Count

表达式用运算符(operators):

  • 算术 + - * /,加上 DIV(整数除法)和 MOD(余数):7 DIV 2 = 3;7 MOD 2 = 1
  • 比较 =<><><=>=
  • 逻辑 ANDORNOT

优先级(precedence,从高到低):NOT* / DIV MOD+ - → 比较 → ANDOR。不确定时用括号。

Input and output

OUTPUT "Enter your name:"
INPUT Name
OUTPUT "Hello, ", Name

Built-in functions and library routines

许多任务有现成的库例程(library routines),所以你不必自己写它们。Paper 2 的附页(insert)列出了你可以使用的例程,以及它们确切的名称、参数和返回类型;题目需要的任何其他函数会在题目中给出。下面是 9618 的名称——IGCSE 的名称(UCASEVALSTR)不被接受。

一个程序库(program library)存放已经写好、编译好并测试过的例程;程序调用它们,而不是自己再写。评分标准接受的好处,用于"说出三个好处"的题:这些例程已经测试过,所以更不容易含有错误;它们节省开发时间;它们可能做到程序员自己写不出的事(复杂的统计、图形);它们由专家编写并在许多程序中重复使用;而且接口固定的例程可以在程序的任何地方调用。

例程 返回 例子
LENGTH(s) s 中的字符个数 LENGTH("Hello") = 5
LEFT(s, n) / RIGHT(s, n) 开头 / 末尾的 n 个字符 RIGHT("Hello", 2) = "lo"
MID(s, start, n) 从位置 start 起的 n 个字符(位置从 1 数起) MID("Hello", 2, 3) = "ell"
TO_UPPER(s) / TO_LOWER(s) 大写 / 小写的 s TO_UPPER("ab1") = "AB1"
NUM_TO_STR(x) / STR_TO_NUM(s) 数变成字符串 / 字符串变成数 STR_TO_NUM("3.5") = 3.5
IS_NUM(s) s 是一个有效的数则为 TRUE IS_NUM("12a") = FALSE
ASC(c) / CHR(n) c 的字符编码 / 编码为 n 的字符 ASC('A') = 65CHR(66) = 'B'
INT(x) x 的整数部分 INT(7.9) = 7
RAND(n) 从 0 到(不含)n 的一个随机实数 INT(RAND(6)) + 1 是掷一次骰子
DAY(d)MONTH(d)YEAR(d) 一个 DATE 的各部分 YEAR(TODAY())
DAYINDEX(d)SETDATE(d, m, y)TODAY() 星期几(1 = 星期日);由三个整数构成的日期;今天的日期
EOF(f) 当文件 f 没有更多行可读时为 TRUE WHILE NOT EOF("data.txt")

字符串用 & 连接(连接(concatenation)):"A" & "BC""ABC"。使用附页里确切的名称,参数按它的顺序。

日期和随机数常以单行语句出现。SETDATE(17, 11, 2007) 构造 2007 年 11 月 17 日;12 - MONTH(MyDOB) 是从出生月份到年底的月数;IF DAYINDEX(MyDOB) = 5 THEN 检验是否星期四,因为星期日是第 1 天。RAND(n) 返回一个从 0 到(不含)n 的实数,所以从 LowHigh(含)的随机整数INT(RAND(High - Low + 1)) + Low:INT(RAND(21)) - 10 给出 -1010 之间的值。

字符串 COMPUTER 显示为八个带编号的字符框(位置 1 到 8),带算出的结果:LENGTH(s) = 8、LEFT(s, 3) = COM、MID(s, 4, 3) = PUT、RIGHT(s, 2) = ER,以及 UCASE/LCASE 改变字母的大小写
常见的字符串例程作用于 s = "COMPUTER"(位置 1–8)

例题。 已知 Word ← "Program"Code ← 'Q'N ← 7,求每个表达式的值。

表达式 原因
LENGTH(Word) 7 七个字符
MID(Word, 4, 2) "gr" 从位置 4 起的两个字符
LEFT(Word, 3) & "!" "Pro!" & 连接
TO_UPPER(RIGHT(Word, 2)) "AM" 内层函数先运行
ASC(Code) - ASC('A') 16 'Q' 是 81,'A' 是 65
N DIV 2 + N MOD 2 4 3 + 1
NUM_TO_STR(N) & "th" "7th" 数先变成字符串
INT(N / 2) 3 3.5 截去小数部分

由内向外计算,并保留引号:"7" 是字符串,而 7 是数。

例题。 每条语句在函数或运算符的使用上都可能有错误。描述错误,或写 NO ERROR。(假设每个变量的类型都正确。)

语句 错误
Result ← 2 & 4 & 连接字符串;24 是整数,所以需要 +
SubString ← MID("pseudocode", 4, 1) NO ERROR:从位置 4 起的一个字符,"u"
IF x = 3 OR 4 THEN OR 两边各需要一个布尔值:IF x = 3 OR x = 4 THEN
Result ← Status AND INT(x / 2) AND 需要两个布尔值;INT(x / 2) 是整数
Message ← "Done" + LENGTH(MyString) + 不能把字符串和整数相加:"Done" & NUM_TO_STR(LENGTH(MyString))

每个运算符只作用于特定的类型:& 作用于字符串,+ - * / DIV MOD 作用于数,AND OR NOT 作用于布尔值,而 = <> 作用于两个同一类型的值。"求每个表达式的值,或写 ERROR"的表格按同样的方式评分:LENGTH(42)"A" + 1 是 ERROR,因为类型与函数或运算符不匹配。

例题。 已知 Points ← 100Active ← TRUEExempt ← FALSE,求每个表达式的值。

表达式 原因
(Points > 99) OR Active TRUE 两边都为真;一边为真就够了
(Points MOD 2 = 0) OR Exempt TRUE 100 MOD 20
(Points <= 75) AND (Active OR Exempt) FALSE 第一边为假,而 AND 需要两边都为真
(Active OR NOT Active) AND NOT Exempt TRUE Active OR NOT Active 永远为真

最后一个表达式可以化简:无论 X 是什么,X OR NOT X 都是 TRUE,所以整个表达式就是 NOT Exempt。先算括号,再算 NOT,然后 AND,最后 OR

探索

A variable is a labelled box

Each assignment stores one value in a named box; reassigning the same name overwrites it. Step through the program and watch each box take its current value.

词汇表 训练
英文 中文 拼音
flowchart 流程图 liú chéng tú
structured English 结构化英语 jié gòu huà yīng yǔ
pseudocode 伪代码 wěi dài mǎ
variables 变量 biàn liàng
data types 数据类型 shù jù lèi xíng
constant 常量 cháng liàng
identifier 标识符 biāo shí fú
assignment 赋值 fù zhí
operators 运算符 yùn suàn fú
Precedence 优先级 yōu xiān jí
library routines 库例程 kù lì chéng
insert 附页 fù yè
program library 程序库 chéng xù kù
concatenation 连接 lián jiē
IDE 集成开发环境 jí chéng kāi fā huán jìng
练习卷
11.2

程序结构

大纲
Candidates should be able to: Notes and guidance
Use pseudocode to write: • an ‘IF’ statement including the ‘ELSE’ clause and nested IF statements • a ‘CASE’ structure • a ‘count-controlled’ loop: • a ‘post-condition’ loop • a ‘pre-condition’ loop
Justify why one loop structure may be better suited to solve a problem than the others

来源:剑桥国际大纲

选择(selection)选择哪些步骤运行。

IF age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF
一张流程图:从开始,一个判断菱形测试 age >= 18;TRUE 分支输出 Adult,FALSE 分支输出 Minor,两者在末端汇合
一个 IF...ELSE 测试条件一次,然后恰好运行一个分支

对于多于两种情况,你可以用一个嵌套(nested)IF,但深度嵌套难以阅读——当把一个值对照几个选项测试时,一个 CASE 更清爽:

CASE OF Grade
    "A": OUTPUT "Excellent"
    "B": OUTPUT "Good"
    OTHERWISE: OUTPUT "Try again"
ENDCASE

Cambridge 的 CASE 允许单个值、值列表(1, 2, 3:)和范围(1 TO 5:)。

嵌套 IF 是放在另一个 IF 的某个分支里的 IF。每个 IF 都需要自己的 ENDIF,而且阅卷人会检查每个结构是否都被关闭:

IF Mark >= 50 THEN
    IF Mark >= 80 THEN
        OUTPUT "Distinction"
    ELSE
        OUTPUT "Pass"
    ENDIF
ELSE
    OUTPUT "Fail"
ENDIF

边界是丢分的地方。"50 分或以上及格"是 Mark >= 50,不是 Mark > 50;CASE 中"其他情况"的最后一个分支写成 OTHERWISE,而不是 > 200 这样的条件。这里一个错误的比较就是一个逻辑错误(logic error):程序能运行,但对某些输入给出错误的输出——而用 50 这样的边界值做一张跟踪表就是找到它的方法。

一个 CASE OF Grade 语句的流程图:该值被依次对照每个卫式(一个单值、一个值列表,然后一个范围)测试;第一个匹配的分支运行它的语句,否则 OTHERWISE 分支运行,而所有分支在 ENDCASE 汇合
一个 CASE 语句运行匹配该值的分支

例题。 不使用 CASE 结构,改写出功能相同的伪代码。

CASE OF MySwitch
    1: ThisChar ← 'a'
    2: ThisChar ← 'y'
    3: ThisChar ← '7'
    OTHERWISE: ThisChar ← '*'
ENDCASE

每个值变成 IF 链中的一个分支,OTHERWISE 变成最后的 ELSE:

IF MySwitch = 1 THEN
    ThisChar ← 'a'
ELSE
    IF MySwitch = 2 THEN
        ThisChar ← 'y'
    ELSE
        IF MySwitch = 3 THEN
            ThisChar ← '7'
        ELSE
            ThisChar ← '*'
        ENDIF
    ENDIF
ENDIF

赋同一个值的两个子句合并成一个带值列表的子句:1, 2: ThisChar ← 'a'。卫式按顺序检验:对于 1 TO 50: 后面跟着 40 TO 60: 这样的范围,值 45 走第一个匹配的分支,所以后面分支里的赋值可能永远不会执行——而当前面的分支已经覆盖了所有可能的值时,OTHERWISE 分支也永远不会到达。

反过来,检验几个布尔值的嵌套 IF 写成每种结果一个条件会更清楚:IF A AND B AND C THEN CALL Sub1(),然后 IF A AND B AND NOT C THEN CALL Sub2(),依此类推。用 ANDOR 把检验连起来就去掉了嵌套,而且 IF A THEN 可以代替 IF A = TRUE THEN

探索

Selection (IF / ELSE)

Change the input and see which branch runs — the essence of selection.

词汇表 训练
英文 中文 拼音
Selection 选择 xuǎn zé
nested 嵌套 qiàn tào
logic error 逻辑错误 luó jí cuò wù
练习卷
11.2

迭代

迭代(iteration)重复一个块。三个循环在主体运行多少次上不同。

Count-controlled (FOR) loop

一个计数循环(count-controlled loop)——当你知道要重复多少次时用它:

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

一个 STEP 可以改变计数(例如 FOR i ← 10 TO 1 STEP -1)。最适合固定次数的重复或处理一个数组(array)的每个元素。

Pre-condition (WHILE) loop

一个前测循环(pre-condition loop)在每一趟之前测试条件,所以它可能运行次:

WHILE total < 100 DO
    INPUT n
    total ← total + n
ENDWHILE

Post-condition (REPEAT...UNTIL) loop

一个后测循环(post-condition loop)在每一趟之后测试条件,所以它总是至少运行一次:

REPEAT
    INPUT password
UNTIL password = correctPassword

Choosing the right loop

三个流程图列。FOR:一个计数框(i = 1 到 N)然后一个主体框,循环回去,做设定次数的趟数。WHILE:一个测试菱形在一个主体框之上,所以条件在主体之前被检查,循环可能运行零次。REPEAT:一个主体框在一个测试菱形之上,所以条件在主体之后被检查,循环至少运行一次
三个循环在条件被测试的位置上不同——在主体之前(WHILE)、之后(REPEAT),或做设定的次数(FOR)
  • 事先知道计数 → FOR
  • 可能需要零趟 → WHILE
  • 总是至少一趟 → REPEAT...UNTIL

用计数是否已知、以及主体是否必须至少运行一次来为你的选择辩护。一个典型的题目给出一个场景("要求密码直到正确,但总是至少要求一次")并问哪个循环合适。

这两分分别给循环的名称和按评分标准措辞的理由:计数控制,因为迭代次数在循环开始前已知;后测,因为循环体必须至少执行一次;前测,因为循环可能根本不需要执行。一个遍历数组四个元素、却写成带计数器的 WHILE 的循环"不是最合适的":次数(四)已知,所以 FOR 循环合适。

例题。 每个任务适合哪种循环?(a) 打印 12 的乘法表;(b) 不断读入数字,直到用户输入 0;(c) 反复要求输入密码,直到正确为止。判断的依据是循环体运行多少次,以及在何时检验条件。(a) 次数事先已知(12 次),所以用 FOR 循环。(b) 次数未知,而且第一个输入就可能已经是 0 - 所以条件必须在循环体之前检验:用 WHILE 循环,它可以运行次或多次。(c) 次数未知,但你必须至少问一次之后才有东西可检验 - 所以条件在循环体之后检验:用 REPEAT...UNTIL,它运行次或多次。决定性的问题是:循环体是否必须至少运行一次 - WHILE 可能运行零次,REPEAT 总是运行一次。

Dry running with a trace table

跟踪表(trace table)记录你手工跟踪(dry run,即用手一步步走一遍)一个算法时每个变量的值。它是在纸上测试一个循环的方法,也是大多数 Paper 2 上一道六分的题。

DECLARE Count, Total : INTEGER
Count ← 1
Total ← 0
WHILE Total < 10
    Total ← Total + Count * 2
    Count ← Count + 1
ENDWHILE
OUTPUT Count, Total
Count Total Total < 10 OUTPUT
1 0 TRUE
2 2 TRUE
3 6 TRUE
4 12 FALSE 4, 12

得分的规则:每个变量一列,按题目给出的顺序;只在值改变时才写它;循环每重复一次就另起一行;用当前的值计算条件,并在它变为 FALSE 的那一刻停止;把输出放在它自己的一列里,与实际显示的完全一样。按算法写的那样去跟踪,而不是按你认为它想要的那样——如果它永不停止,就说明这一点。

例题。 每一行用了哪些结构——选择、迭代还是子程序调用?

伪代码 选择 迭代 子程序
IF Ready = TRUE THEN CALL Start() ENDIF
FOR I ← 1 TO 20 ... NEXT I
WHILE NOT IsFull() ... ENDWHILE
CASE OF Key ... OTHERWISE ... ENDCASE

IFCASE 是选择;FORWHILEREPEAT 是迭代;名字后面跟着括号——Start()IsFull()——就是对过程或函数的调用,无论它出现在哪里,包括在条件里面。

探索

Trace a loop, pass by pass

A trace table records each variable after every pass of the loop. Watch the counter i climb while the running total builds up — exactly what an exam trace question asks you to fill in.

探索

Tracing a loop

Step through the loop and watch the variables change each pass — exactly what a trace table records.

词汇表 训练
英文 中文 拼音
Iteration 迭代 dié dài
count-controlled loop 计数循环 jì shù xún huán
array 数组 shù zǔ
pre-condition loop 前测循环 qián cè xún huán
post-condition loop 后测循环 hòu cè xún huán
trace table 跟踪表 gēn zōng biǎo
dry run 手工跟踪 shǒu gōng gēn zōng
11.3

结构化编程

大纲
Candidates should be able to: Notes and guidance
Define and use a procedure
Explain where in the construction of an algorithm it would be appropriate to use a procedure
Use parameters A procedure may have none, one or more parameters A parameter can be passed by reference or by value
Define and use a function
Explain where in the construction of an algorithm it is appropriate to use a function A function is used in an expression, e.g. the return value replaces the call
Use the terminology associated with procedures and functions including procedure/function header, procedure/function interface, parameter, argument, return value
Write efficient pseudocode

来源:剑桥国际大纲

结构化编程(structured programming)从小的、有名字的子程序(subroutines)构建一个程序,每个有一件工作。

Procedure

一个过程(procedure)是一个有名字的块,它做一个动作;它可以取参数(parameters),但不返回一个值

PROCEDURE Greet(name : STRING)
    OUTPUT "Hello, ", name
ENDPROCEDURE

CALL Greet("Ada")

Function

一个函数(function)像一个过程,但它返回一个值,该值成为一个表达式的一部分。

FUNCTION Square(x : INTEGER) RETURNS INTEGER
    RETURN x * x
ENDFUNCTION

result ← Square(5) + 1     // result = 26

当子程序执行一个动作时用一个过程;当它为调用者计算一个值时用一个函数

教学大纲问的是在构造算法的哪里用哪一个合适。在同一组步骤在几处都需要的地方(验证一个输入、打印一个菜单、交换两个值),用过程合适:步骤只写一次,然后按名字 CALL。在必须算出一个值然后在表达式中使用的地方——一个总数、一个 TRUE/FALSE 的结果、两个数中较大的一个——用函数合适,因为返回值(return value)替换了调用:IF IsValid(Code) THEN

两个面板。过程:调用 Greet(Ada) 做一个动作并打印 Hello, Ada,不返回值。函数:设 y = Square(5) 计算 5 乘 5 = 25,返回 25,所以 y 随即容纳 25
一个过程做一个动作并不返回任何东西;一个函数返回一个你在表达式中使用的值

Parameters

一个参数(parameter)是一个子程序声明用来接收输入的变量;调用者提供的值是实参(arguments)。传递它们的两种方式:

  • 传值(pass by value)——例程得到一个副本;它内部的改变不影响调用者。用于它只读取的输入。
  • 传引用(pass by reference)——例程得到一个到调用者变量的引用;改变确实影响调用者。当它必须更新一个参数时用。
两个内存框图。传值:调用者的变量 x = 5 被复制到一个单独的参数框 a = 5,所以改变 a 使 x 保持为 5。传引用:参数 a 是一个指向调用者自己的 x 框的箭头,所以改变 a 也改变 x
传值把值复制到一个新框;传引用让例程改变调用者自己的变量
PROCEDURE Swap(BYREF a : INTEGER, BYREF b : INTEGER)
    DECLARE temp : INTEGER
    temp ← a
    a ← b
    b ← temp
ENDPROCEDURE

Cambridge 伪代码在头部里、每个参数前写出传递方式 BYVALBYREF。两者都不写时默认是 BYVAL,所以必须改变调用者变量的例程——Swap,或者更新一个累计总数的过程——头部里需要 BYREF

例题。 输出是什么?

PROCEDURE Adjust(BYREF X : INTEGER, BYVAL Y : INTEGER)
    X ← X + Y
    Y ← Y * 2
ENDPROCEDURE

A ← 5
B ← 3
CALL Adjust(A, B)
OUTPUT A, B

X 是到 A 的引用,所以 A 变成 8YB 的一个副本,所以把 Y 加倍后 B 仍是 3。输出是 8, 3。如果头部写的是 BYVAL X,A 仍会是 5

Local vs global variables

一个局部变量(local variable)在一个子程序内部声明,只在它运行时存在。一个全局变量(global variable)在外部声明,处处可见。优先用局部变量和参数——大量使用全局变量使代码难以理解和测试。(一个名称可见的区域是它的作用域(scope)。)

一句话的区别:全局变量可以在程序的任何地方访问,局部变量只能在声明它的子程序内部访问。评分标准接受的局部变量的好处:同一个标识符可以在另一个子程序里使用而不冲突;它的值不会被程序的其他部分意外改变;子程序结束时内存被释放;而且子程序是自包含的,所以可以单独测试并在另一个程序中重用。

局部变量在子程序每次被调用时创建、返回时销毁,所以它不能把一个值从一次调用带到下一次。因此,一个在多次调用中逐步拼接字符串的过程需要那个字符串是全局的(或以 BYREF 传入)。如果把 MyString 从全局变量改成在 MyOutput() 内部声明的局部变量,每次调用都从一个新的、空的 MyString 开始,之前调用加上的文本就丢失了,过程"不能按预期工作"。

同一个过程在时间线上的三次调用;每次调用创建自己的局部 MyString 框,新的且为空,调用返回时就消失了,而它们上方的一个全局 MyString 框在各次调用之间保持它的值
局部变量在每次调用时都是一个新的、空的框;只有全局变量(或 BYREF 参数)能在各次调用之间保留值
一个大的外框标注为全局作用域,容纳全局变量 Total,处处可见,而一个较小的内框标注为 PROCEDURE Calc、局部作用域,容纳局部变量 temp,它只在 Calc 运行时存在
一个全局变量处处可见;一个局部变量只在它自己的过程内部存在

When to use a subroutine

在以下情况用一个子程序:

  • 同样的逻辑出现在不止一处——写它一次,调用它多次。
  • 一个块有一个清晰、有名字的目的——名称记录它做什么。
  • 程序复杂——把它分成部分(分解(decomposition))。
  • 你想孤立地测试一个片段

不要把它们做得那么小,以至于调用的代价超过里面的工作。

Terminology

  • definition——PROCEDURE ... ENDPROCEDURE(或函数)块。
  • call——它被调用的地方。argument——一个被传入的值。parameter——接收它的变量。
  • return value——一个函数传回什么。
  • procedure/function header——给出名称和参数的第一行(PROCEDURE Name(params)FUNCTION Name(params) RETURNS type)。
  • procedure/function interface / signature(签名)——名称 + 参数 + 返回类型:一个调用者要用它必须知道什么。

例题。 描述头部 FUNCTION Pass2(Count : INTEGER) RETURNS BOOLEAN 中用到的每个术语。

术语 含义
FUNCTION 一个返回值的子程序
Pass2 用来调用它的标识符
Count 参数:接收传入的实参的标识符
INTEGER 参数的数据类型
RETURNS BOOLEAN 函数返回的值的数据类型

PROCEDURE MyProc(Count : INTEGER, Message : STRING) 里的两个标识符是参数:它们在过程被调用时接收传入的值,并在过程内部像局部变量一样使用。

把过程改成函数:把 PROCEDURE 改为 FUNCTION 并加上 RETURNS <type>;把 OUTPUT(或者把结果带出去的 BYREF 参数)换成一条 RETURN 语句;并修改每一处调用,使返回值被使用,即 Result ← Unpack(Text) 而不是 CALL Unpack(Text, Result)。对于"写出头部"的题,写出整行:FUNCTION Calculate(Expression : STRING) RETURNS INTEGER。数组参数是按引用传递的,所以向数组里写入的过程会改变调用者的数组。

当一个程序增加一个新模块时,首先要商定的就是接口:名称、参数(几个、什么顺序、什么类型)和返回类型,再加上该模块读取或写入的任何全局数据。一个在到期日之前发送提醒的模块需要把记录(或它的下标)作为参数,并且不返回任何东西,所以它是一个过程;主程序对每条记录调用它一次。

Writing a module for Paper 2

Paper 2 的一半是"为模块 X 写伪代码"。评分标准按特征逐项给分,所以一个没写完的模块仍能为每个正确的部分得分。阅卷人要找的部分:

一个带注释的伪代码函数 CountAbove,每个得分的部分都有一条标注:带参数和返回类型的头部、局部声明、循环前初始化的总数、遍历每个元素的 FOR 循环、带正确边界的 IF 条件、IF 内部的更新、关闭的结构,以及循环之后的 RETURN
模块答案的每个部分都有自己的分,所以即使某一部分没有把握,也要把所有部分写出来
  1. 头部,按题目描述的写:PROCEDURE Name(Param : TYPE)FUNCTION Name(Param : TYPE) RETURNS TYPE,在例程必须改变实参的地方加 BYREF
  2. 局部声明:用 DECLARE 声明每个局部变量及其类型,并初始化计数器和总数(Count ← 0)。
  3. 访问每个元素的循环:对于给出了大小的数组用 FOR Index ← 1 TO 50;对于文件用 WHILE NOT EOF(...)
  4. 条件,用正确的比较和边界,针对正确的项:IF Score[Index] > Limit THEN
  5. 分支内部的更新:计数增加、值被存储,或消息被输出。
  6. 结尾:函数中在循环之后 RETURN 一次;ENDFUNCTIONENDPROCEDURE;并且每个 IFFORWHILE 都关闭。

例题。 一个全局数组 Score : ARRAY[1:50] OF INTEGER 存放测验分数。写一个函数 CountAbove(Limit : INTEGER),返回有多少个分数大于 Limit

FUNCTION CountAbove(BYVAL Limit : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 50
        IF Score[Index] > Limit THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count
ENDFUNCTION

给分点:带参数和 RETURNS INTEGER 的头部;Count 被声明并设为 0;遍历全部 50 个元素的循环;比较 > Limit(不是 >=);在 IF 内部更新计数;循环之后 RETURN Count。主程序在表达式或输出中使用返回值:OUTPUT "Above 70: ", CountAbove(70)

例题。 写一个函数 IsValid(Code : STRING),当 Code 是两个大写字母后跟四个数字——即格式(format)AB1234——时返回 TRUE,否则返回 FALSE

FUNCTION IsValid(BYVAL Code : STRING) RETURNS BOOLEAN
    DECLARE Index : INTEGER
    DECLARE Ch : STRING
    IF LENGTH(Code) <> 6 THEN
        RETURN FALSE
    ENDIF
    FOR Index ← 1 TO 6
        Ch ← MID(Code, Index, 1)
        IF Index <= 2 THEN
            IF Ch < "A" OR Ch > "Z" THEN
                RETURN FALSE
            ENDIF
        ELSE
            IF Ch < "0" OR Ch > "9" THEN
                RETURN FALSE
            ENDIF
        ENDIF
    NEXT Index
    RETURN TRUE
ENDFUNCTION

长度检查放在最前面,这样 MID 就永远不会被要求取一个不存在的位置。这样的验证(validation)返回一个 BOOLEAN,以便调用者可以写 IF IsValid(Entry) THEN ... ELSE OUTPUT "Invalid code" ENDIF:给用户的消息由调用者输出,而不是由函数输出——函数计算,过程行动。

例题。 写一个函数 IsPalindrome(Word : STRING),当 Word 倒过来读也一样(例如 "RACECAR")时返回 TRUE

从两端向中间比较字符:位置 Index 与位置 Len - Index + 1 配对,只需检验前一半。

单词 RACECAR 放在七个编号的框里;弧线把位置 1 与 7、2 与 6、3 与 5 配对,标注为位置 i 和位置 Len 减 i 加 1;中间的字符没有配对
回文检验把位置 i 与位置 Len - i + 1 配对,到中间为止
FUNCTION IsPalindrome(BYVAL Word : STRING) RETURNS BOOLEAN
    DECLARE Len, Index : INTEGER
    Len ← LENGTH(Word)
    FOR Index ← 1 TO Len DIV 2
        IF MID(Word, Index, 1) <> MID(Word, Len - Index + 1, 1) THEN
            RETURN FALSE
        ENDIF
    NEXT Index
    RETURN TRUE
ENDFUNCTION

同样的三件工具——遍历各位置的 FOR、读取一个字符的 MID(s, i, 1)、拼出新字符串的 &——能解答 Paper 2 上大多数字符串模块:数一个字符出现多少次(IF MID(s, i, 1) = Ch THEN Count ← Count + 1),替换某个字符的每一次出现(在每个位置把 NewChar 或原字符加到 NewString 上),隐藏银行卡号除最后四位以外的数字(直到 Len - 4 的每个位置都加一个 '*'),或者自己写一个 MID()(把从 StartStart + Length - 1 的字符连接起来)。向 MID 要一个超出字符串末尾的位置是运行时错误,所以先检查 LENGTH

文件。 变量里的值在程序结束时就消失了,所以一个必须为下一次运行保留数据的模块要把数据写到文件里:OPENFILE "scores.txt" FOR WRITE,在循环里每行一个 WRITEFILE "scores.txt", NUM_TO_STR(Score[Index]),循环之后 CLOSEFILE "scores.txt" 一次;读回来用 FOR READREADFILEWHILE NOT EOF("scores.txt")。主题 10 有完整的文件部分;这里的分给以正确的模式打开、在循环内读或写、以及在循环之后关闭一次。

探索

The call stack: push on call, pop on return

Calling a subroutine pushes a new frame on top; returning pops it and hands a value back to the caller. The call that is running is always the frame on top.

词汇表 训练
英文 中文 拼音
Structured programming 结构化编程 jié gòu huà biān chéng
subroutines 子程序 zi chéng xù
procedure 过程 guò chéng
parameters 参数 cān shù
function 函数 hán shù
return value 返回值 fǎn huí zhí
arguments 实参 shí cān
pass by value 传值 chuán zhí
pass by reference 传引用 chuán yǐn yòng
local variable 局部变量 jú bù biàn liàng
global variable 全局变量 quán jú biàn liàng
scope 作用域 zuò yòng yù
decomposition 分解 fēn jiě
signature 签名 qiān míng
format 格式 gé shì
Validation 验证 yàn zhèng
练习卷
11.3

编写高效的伪代码

让伪代码更易理解的三个特征——"说出三个特征"这类题的答案——是有意义的标识符(Total,而不是 t)、每个结构内部语句的缩进,以及说明目的的注释(// ...);关键字大写、一行一条语句、各部分之间留空行也被接受。高效的伪代码更进一步:

  • 把不变量移出循环——若一个值(一个不变量(invariant))不随循环计数器改变,在循环之前计算它一次。
  • 当答案被找到时尽早退出一个循环(一旦目标出现就停止一个线性查找(linear search))。
  • 避免冗余的工作——存储一个结果并重用它,而不是重新计算。
  • 选择正确的数据结构——当各项属于一起时,一个数组胜过许多分开的变量。
  • 当把一个值对照许多选项测试时,用 CASE 替换深度嵌套的 IF
  • 注释意图,而不是机制(// validate the postcode,而不是 // loop 6 times)。
  • 使用有意义的名称(numberOfPupils,而不是 n)并在使用前初始化变量
把从不改变的工作移出循环,所以它运行一次而不是每一趟
把不变的工作移出循环,所以它运行一次
词汇表 训练
英文 中文 拼音
invariant 不变量 bù biàn liàng
linear search 线性查找 xiàn xìng chá zhǎo
11.3

测试与错误

三种错误,每种用不同的方式发现:

错误 是什么 例子 由什么发现
语法错误(syntax error) 违反语言规则的语句 缺少 ENDIF;OUTPT "Hi" 翻译程序,在程序运行之前
运行时错误(run-time error) 程序能运行,但某条语句无法执行 除以零;数组下标为 0 或 51;用无效的参数调用函数;永不结束的循环,使程序"卡死" 运行时:程序停止或挂起
逻辑错误 程序运行到结束,但输出是错的 该用 >= 的地方用了 >;总数从未设为 0 用跟踪表和选定的测试数据进行测试

集成开发环境(IDE)帮助发现后两种:断点(breakpoint)让程序在选定的一行停下;然后单步执行(single stepping)一次运行一条语句;而报告(或监视)窗口显示那一刻每个变量的值,于是值出错的那一行可以直接看到。测试方法和测试数据在主题 12。

词汇表 训练
英文 中文 拼音
syntax error 语法错误 yǔ fǎ cuò wù
run-time error 运行时错误 yùn xíng shí cuò wù
breakpoint 断点 duàn diǎn
single stepping 单步执行 dān bù zhí xíng
11.3

考官认可的定义

定义题按固定的表述给分。把这些记准确。

术语 定义
过程(procedure) 执行一项任务(一系列步骤)且不返回值的子程序;用 CALL 调用
函数(function) 把一个值返回到调用它的地方的子程序,因此可以在表达式中使用
参数(parameter) 子程序头部中的标识符,在子程序被调用时接收一个值或一个引用
实参(argument) 调用中提供的值(或变量),与一个参数对应
传值(passing by value) 把实参值的一个副本交给子程序,所以子程序内部的改变不影响原来的变量
传引用(passing by reference) 把变量的地址交给子程序,所以子程序内部的改变会改变原来的变量
头部(header) 子程序定义的第一行:它的名称、它的参数,以及函数的返回类型
接口(interface) 调用程序使用一个子程序必须知道的东西:它的名称、参数(个数、顺序、类型)和返回类型
返回值(return value) 函数传回给调用它的表达式的值
局部变量(local variable) 在子程序内部声明;只在子程序运行时存在,并且只能在其内部使用
全局变量(global variable) 在所有子程序之外声明;可以在程序的任何地方使用
计数循环(count-controlled loop) 由一个计数器控制,重复固定的次数(FOR ... NEXT)
前测循环(pre-condition loop) 在每次迭代之前检验条件,所以循环体可能一次也不运行(WHILE ... ENDWHILE)
后测循环(post-condition loop) 在每次迭代之后检验条件,所以循环体至少运行一次(REPEAT ... UNTIL)
常量(constant) 一个在程序运行期间不能改变的、有名字的值
子程序(subroutine) 一段自包含的、执行一项任务并按名字调用的代码:过程或函数
库例程(library routine) 已经写好并测试过、可供程序调用的子程序
11.3

考试技巧

  • 区分一个过程(无返回值)和一个函数(返回一个值);知道传值对传引用
  • 选择正确的循环:当重复次数已知时用计数循环(FOR),否则用条件控制循环(WHILE/REPEAT)
  • 区分局部对全局变量和作用域;在可重用模块中优先用局部变量。
  • 使用附页里确切的例程名称和参数顺序;UCASEVAL 是 IGCSE 的名称,在这里不得分。
  • 在"写伪代码"的答案里,头部、声明、循环、条件、更新和 RETURN 各有一分:即使某一部分没有把握,也要把六个部分都写出来。

常见错误

  • 调用了函数却不使用它返回的值。把结果赋给变量,或在表达式或输出中使用它:Sorted ← BubbleSort(MyArray, 7)
  • 传入的长度差一:七个元素的数组传了 6,或者在要长度的地方传了最后一个下标。想清楚参数是长度还是下标,并检查最后一个元素是否被访问到。
  • 在读文件的循环里面关闭文件。打开一次,在循环之后关闭一次。
  • 直接把输入当作文件名。加上题目给的扩展名:FileName ← Choice & ".txt"
  • 结构没有关闭。每个 IF 都需要它的 ENDIF,每个 FOR 需要它的 NEXT,每个 WHILE 需要它的 ENDWHILE,每个函数需要它的 RETURN;评分标准里有这一分。
  • 错误的边界:"至少"用了 >(应该是 >=),或者对声明为 [1:50] 的数组从 0 开始 FOR 循环。
  • 计数器或总数在循环之前从未设为 0
  • 在跟踪表里每一行都重写所有变量,或者在改变某个值的语句运行之前就改了它。
  • 半个条件:IF x = 3 OR 4——ORAND 的两边都必须是完整的比较。而且 + 不连接字符串,& 才是。
  • 把必须在各次调用之间保留的值声明为局部变量。累计总数或在多次调用中拼起来的字符串应该是全局的或 BYREF

本主题的互动课程

逐步学习,并即时检测练习。

A-Level 计算机科学历年真题

A-Level 计算机科学的更多主题

登录或创建账号

IGCSE, A-Level & AP