程序设计

From design to code

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

1. 找出变量(variables)及其数据类型(data types)。
2. 把输入/输出框变成 INPUT / OUTPUT。
3. 把判断菱形变成 IF...ELSE...ENDIF(或 CASE)。
4. 把循环箭头变成 WHILE、REPEAT...UNTIL 或 FOR。
5. 把处理框变成赋值或计算。
6. 通过追踪一个小输入来检查。

Constants and variables

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

CONSTANT Pi ← 3.14159
DECLARE Radius : REAL
DECLARE Area : REAL

Radius ← 5
Area ← Pi * Radius * Radius

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

Assignment and expressions

用 ← 表示赋值(assignment):

Total ← Total + 1
Average ← Sum / Count

表达式用运算符(operators):

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

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

Input and output

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

Built-in functions and library routines

许多任务有现成的库例程(library routines),所以你不必自己写它们:

• 字符串:LENGTH(s)、LEFT(s, n)、RIGHT(s, n)、MID(s, start, len)、UCASE(s)、LCASE(s)。
• 数值:INT(x)、ROUND(x)、ABS(x)、MOD(a, b)、RANDOM()。
• 转换:STR(x)(数 → 字符串)、VAL(s)(字符串 → 数)。

使用题目参考列表里确切的名称。

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

IF age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

对于多于两种情况,你可以用一个嵌套(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:)。

迭代(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。
• 可能需要零趟 → WHILE。
• 总是至少一趟 → REPEAT...UNTIL。

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

结构化编程(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

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

Parameters

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

• 传值(pass by value)——例程得到一个副本;它内部的改变不影响调用者。用于它只读取的输入。
• 传引用(pass by reference)——例程得到一个到调用者变量的引用;改变确实影响调用者。当它必须更新一个参数时用。

PROCEDURE Swap(BYREF a : INTEGER, BYREF b : INTEGER)
    DECLARE temp : INTEGER
    temp ← a
    a ← b
    b ← temp
ENDPROCEDURE

Local vs global variables

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

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(签名)——名称 + 参数 + 返回类型:一个调用者要用它必须知道什么。

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

• 把不变量移出循环——若一个值(一个不变量(invariant))不随循环计数器改变,在循环之前计算它一次。
• 当答案被找到时尽早退出一个循环(一旦目标出现就停止一个线性查找(linear search))。
• 避免冗余的工作——存储一个结果并重用它,而不是重新计算。
• 选择正确的数据结构——当各项属于一起时,一个数组胜过许多分开的变量。
• 当把一个值对照许多选项测试时,用 CASE 替换深度嵌套的 IF。
• 注释意图,而不是机制(// validate the postcode,而不是 // loop 6 times)。
• 使用有意义的名称(numberOfPupils,而不是 n)并在使用前初始化变量。

• 区分一个过程(无返回值)和一个函数(返回一个值);知道传值对传引用。
• 选择正确的循环:当重复次数已知时用计数循环(FOR),否则用条件控制循环(WHILE/REPEAT)。
• 区分局部对全局变量和作用域;在可重用模块中优先用局部变量。