算法设计与问题求解

计算思维(computational thinking)是分析一个问题并设计一个计算机能运行的解决方案的一套心智工具。两个关键的是抽象和分解。

抽象

抽象(abstraction)意味着保留一个问题的本质特征并忽略无关的细节,给出一个更简单的模型。

例子:

• 一张铁路网络图保留车站和线路,但去掉地理。
• 面向对象编程中的一个类只保留系统需要的属性和方法。
• 一个函数把一段工作隐藏在一个名称后面。

任何真实问题的完整模型都太大而无法推理,所以抽象是必不可少的。

考官会问抽象的目的和它的好处。目的:得到一个只包含解决问题所需细节的更简单的模型。好处:问题更容易理解和编程;程序更小,写起来和测试起来更快;同一个模型可以在类似的问题上重用。当题目要求你建立一个抽象模型时,只列出任务需要的数据和操作。对于学校课表来说,那就是班级、教室、教师和课时;而不是教室的颜色或教师的年龄。

分解

分解(decomposition)意味着把一个大问题分成更小的子问题,每个更容易解决并一次处理一个。

1. 找出任务的主要部分。
2. 把每个分成更小的子任务。
3. 继续直到每个都小到能直接设计。
4. 解决小任务并把它们组合起来。

对于库存控制:"管理库存" → "记录销售"、"记录到货"、"生成报表" → ("记录销售")"查找产品"、"减少库存计数"、"保存交易"。分解使大问题可管理、让一个团队分担工作,并给出模块化的代码——每个模块成为一个过程(procedure)或函数。

"解释为什么使用分解"是一道有固定形状的三分题。给出三个各自独立的好处:每个子问题(sub-problem)都小到可以单独设计、编码和测试;不同的程序员可以同时做不同的模块(module);已经存在的模块(或库例程)可以重用,而且错误更容易找到,因为它只在一个模块里。结构图(主题 12)就是分解的图示:程序在顶部,它的模块在下面,以及它们之间传递的数据。

一个算法(algorithm)是表述为一系列已定义步骤的解决方案。每一步是无歧义的(unambiguous,一个意思)、确定性的(deterministic,相同输入 → 相同输出)、有限的(finite,步骤会结束),以及有效的(effective,每一步都能做)。一个算法说明做什么,与用来实现它的编程语言无关。

当你开始一个算法时,在一个标识符表(identifier table)中列出每一份数据——它的标识符(identifier,即变量(variable)名)、数据类型(data type)和描述。考试中的表恰好就是这三列:

使用描述性的名称(ItemCost,而不是 x):标识符以字母开头,不含空格,并且每次出现都写得一模一样。常见类型是 INTEGER、REAL、STRING、CHAR、BOOLEAN、DATE,加上数组。这个表迫使你在写代码之前命名每一份数据;"补全标识符表"的题目每个正确的数据类型或描述各给一分,所以类型要严格按伪代码指南的写法写。

伪代码(pseudocode)是一种描述算法的结构化、语言中立的方式。

1. 顺序

步骤一个接一个地运行(顺序(sequence)):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. 选择

基于一个条件选择运行哪些步骤(选择(selection)):

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

对于更多的选项,用 CASE OF ... ENDCASE。

3. 迭代

重复一个块(迭代(iteration),一个循环(loop)):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

一个 WHILE 循环在每一趟之前测试条件(可能运行零次);一个 REPEAT...UNTIL 循环在每一趟之后测试(总是至少运行一次)。

WHILE Total < 100 DO
    INPUT Value
    Total ← Total + Value
ENDWHILE

REPEAT
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100

选对循环本身就是一分:知道重复多少次时用 FOR(计数循环(count-controlled loop));循环可能一次都不运行时用 WHILE(前测循环(pre-condition loop));必须至少运行一次时用 REPEAT ... UNTIL,例如验证一次输入(后测循环(post-condition loop))。"描述迭代结构"的答案要说出结构的名称、条件在哪里测试,以及后果(零次或至少一次)。

常见操作

• 赋值(assignment):x ← 5(一个箭头;= 用于比较)。
• 输入/输出:INPUT variable、OUTPUT expression。
• 比较 =、<>、<、>、<=、>=;逻辑 AND、OR、NOT。
• 算术 + - * /,加上 DIV(整数除法)和 MOD(余数)。
• 字符串:LENGTH、LEFT、RIGHT、MID,以及 & 用于拼接(concatenation,连接)。

考试要求的伪代码

每一个伪代码答案都按剑桥公布的伪代码指南评分。要严格按这些形式写:

有两个习惯在每道题上都能得分:声明你用到的每个变量,类型取自你的标识符表;在改变它们的循环之前,初始化(initialise)每个计数器(counter)和总和(Count ← 0、Total ← 0)。

输入 → 处理 → 输出

每个程序都遵循这个形状:

INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area

先列出输入和输出使算法更清晰。

例题。 写伪代码:输入 100 个整数,输出其中落在 10 到 20(含)之间的数有多少个,以及这些数的总和。

标识符表:Count : INTEGER(循环计数器)、Value : INTEGER(刚输入的整数)、InRange : INTEGER(在范围内的个数)、Total : INTEGER(它们的和)。

DECLARE Count, Value, InRange, Total : INTEGER
InRange ← 0
Total ← 0
FOR Count ← 1 TO 100
    INPUT Value
    IF Value >= 10 AND Value <= 20 THEN
        InRange ← InRange + 1
        Total ← Total + Value
    ENDIF
NEXT Count
OUTPUT InRange, Total

如果题目接着要求你"指出两种结构并说明各自如何使用",就用同样的形状回答:迭代,即 FOR 循环,把输入重复 100 次;选择,即 IF 语句,只在数值处于范围内时才把它加上。

例题。 程序从 1 到 100 中选一个秘密整数。用户一直猜到猜对为止;每次猜错后程序说"Too low"或"Too high",最后输出一共猜了多少次。

标识符表:Secret : INTEGER(要猜的数)、Guess : INTEGER(用户的输入)、Tries : INTEGER(到目前为止猜了多少次)。

DECLARE Secret, Guess, Tries : INTEGER
Secret ← INT(RAND(100)) + 1
Tries ← 0
REPEAT
    INPUT Guess
    Tries ← Tries + 1
    IF Guess < Secret THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Secret THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Secret
OUTPUT "You took ", Tries, " guesses"

REPEAT ... UNTIL 循环是正确的选择,因为用户必须至少猜一次。给分点是:范围正确的随机数、猜对时结束的循环、从零开始并在循环内递增的计数器、在正确条件下输出的两条信息,以及最后的输出。

例题。 输出两个不同的随机整数,每个都在 $-10$ 到 $10$(含)之间。

可能的值有 21 个,所以 INT(RAND(21)) 给出 0 到 20,减去 10 就把它移到 $-10$ 到 $10$ 的范围。第二个数必须重新生成,直到它与第一个不同:

DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
    Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second

同一个算法可以用三种方式书写。

• 结构化英语(structured English)——带缩进和固定关键字的自然语言;适合一个高层描述。
• 流程图(flowchart)——一个带标准形状的图:

• 伪代码——上面的关键字记法;最接近代码。

你应当能够在任何一对之间转换:每个 IF 是一个判断菱形,每个循环是一个回箭头,一个顺序是堆叠的矩形。

把流程图转换成伪代码:从终止符开始,按顺序沿箭头走;平行四边形变成 INPUT 或 OUTPUT;矩形变成赋值;两个出口在下方重新汇合的菱形变成 IF ... THEN ... ELSE ... ENDIF;只有一个出口且箭头向上回去的菱形是循环——如果菱形在被重复的方框之前就是 WHILE 循环,如果在之后就是 REPEAT ... UNTIL 循环。反过来转换时,每条语句恰好画一个方框、每个条件恰好画一个菱形,并给菱形的每个出口标上"是"或"否"。

逐步求精(stepwise refinement)从一个高层大纲开始,展开每一步直到它小到能编码。对于 $n$ 个数字的平均值:

第 1 层:

Read in the numbers
Compute the average
Output the average

第 2 层:

INPUT n
total ← 0
FOR i ← 1 TO n
    INPUT value
    total ← total + value
NEXT i
average ← total / n
OUTPUT average

每次求精都保留之前的结构并添加细节。

六分的"应用逐步求精"题会给你一个高层大纲,要你把每一步展开成程序员能直接编码的具体语句。保持步骤的顺序不变,写出每一步读入或产生的数据的名称,直到每一行都是单独的一个输入、赋值、输出、循环或条件为止。例如,"验证密码"展开为:输入密码;检查它的长度至少为 8;检查它至少含一个数字;两项检查都通过则输出"accepted",否则输出"rejected"。

一个逻辑语句(logic statement)是一个控制分支的布尔(Boolean)条件,由比较(x > 10)、连接词(AND、OR、NOT)和括号构成。把它用作 IF、WHILE 或 REPEAT...UNTIL 的条件:

WHILE attempts < 3 AND NOT loggedIn DO
    INPUT password
    IF password = correctPassword THEN
        loggedIn ← TRUE
    ELSE
        attempts ← attempts + 1
    ENDIF
ENDWHILE

优先级(precedence,从高到低):NOT,然后 AND,然后 OR。不确定时用括号。常见错误:

• a = 1 OR 2 是错的——写 a = 1 OR a = 2。
• NOT a > 5 意味着 NOT (a > 5),即 a <= 5。
• NOT (A AND B) 与 (NOT A) OR (NOT B) 相同(德摩根定律(De Morgan's law))——对简化条件很方便。

把一句话变成逻辑语句是试卷直接考查的技能。"5 岁以下或 65 岁以上免票"变成 Age < 5 OR Age > 65。"分数有效当且仅当它是 0 到 100 的整数"变成 Mark >= 0 AND Mark <= 100。"文件结束或已读 10 条记录时循环停止"变成 UNTIL EOF(File) OR Count = 10。每个比较都要写完整:Age > 65 和 Age < 5,绝不能写 Age > 65 OR < 5。

例题。 写出标识符表和伪代码:读入 10 个数并输出最大的那个。标识符表为每个变量写明数据类型和用途:Count : INTEGER(循环计数器)、Num : REAL(刚读入的数)、Max : REAL(到目前为止的最大值)。

Max ← -999999
FOR Count ← 1 TO 10
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT Max

承载分数的设计决定是 Max 的初始化:它必须从一个比任何可能的输入都低的值开始 - 或者更稳妥地,把它设成第一个读入的数。若把它初始化为 0,那么对一串负数,该算法会错误地返回 0;这个 bug 只有当你的测试数据里包含负数时,追踪才会把它暴露出来。

定义题按固定的表述给分。把这些记准确,并且只写一个答案。

• 把一个算法定义为一个无歧义、有限、确定性的步骤序列,与语言无关。
• 正确地使用三种结构——顺序、选择、迭代——并保留一个带数据类型的标识符表。
• 通过分解和抽象把一个问题分解,然后逐步求精。
• 写实际能运行的伪代码:声明变量并遵循考试的伪代码风格。

常见错误

• 用 = 来赋值。赋值是 ←;= 是比较。
• 漏掉 ENDIF、ENDWHILE、ENDCASE 或 NEXT。每种结构都要闭合,而结构的分数正是在闭合词处检查的。
• 循环之前不初始化总和或计数器,导致算法往一个从未存在的值上累加。
• 在重复次数未知时使用 FOR 循环。读到哨兵值或猜对为止需要 WHILE 或 REPEAT ... UNTIL。
• 写成 Age > 65 OR < 5。OR 和 AND 的每一边都必须是一个完整的比较。
• 用同一个好处的三种说法来回答"解释为什么使用分解"。三分需要三个不同的好处。