算法设计与问题求解

计算思维是用于分析问题并设计计算机可执行的解决方案的一套思维工具。其中两个关键概念是抽象和分解。

抽象

抽象意味着保留问题的本质特征并忽略无关细节，从而提供一个更简单的模型。

例子:

• 列车网络图保留了车站和线路，但省略了地理信息。
• 面向对象编程中的类只保留系统所需的属性和方法。
• 函数用一个名称隐藏了一部分工作。

任何真实问题的完整模型都会过于庞大而无法推理，因此抽象是必不可少的。

考官要求说明抽象的目的及其优点。目的：生成一个更简单的问题模型，仅包含解决问题所需的细节。优点：问题更容易理解和编程；程序更小，编写和测试速度更快；同一模型可重复用于类似问题。当被要求构建系统的抽象模型时，只列出任务所需的数据和操作。例如学校课程表只需包括课程、教室、教师和课时；无需考虑教室颜色或教师年龄。

分解

分解 means 将一个复杂问题拆解为若干子问题，每个子问题更易解决，且可逐一处理。

1. 找出任务的主要组成部分。
2. 将每个部分拆分为更小的子任务。
3. 持续拆分直至每个子任务足够小，可直接设计。
4. 解决各子任务并将其组合。

库存管理示例：“管理库存” → “记录销售”、“记录进货”、“生成报告” → （“记录销售”）→ “查询产品”、“减少库存数量”、“保存交易”。分解使复杂问题易于管理，便于团队分工，并实现模块化代码——每个模块成为过程 or 函数。

“解释为何使用分解”是三分题，有固定答题结构。需列出三个独立优点：每个子问题足够小，可独立设计、编码和测试；不同程序员可同时开发不同模块；已有模块（或库例程）可复用，且因故障局限于单一模块，更易定位。结构图（主题 12）即分解示意图：顶部为程序，下方为各模块，中间显示数据传递关系。

算法 is a solution expressed as a sequence of defined steps. Each step is unambiguous (one meaning), deterministic (same input → same output), finite (steps terminate), and effective (each can be executed). Algorithm describes what to do, independent of implementation language.

开始编写算法前，需在标识符表中列出所有数据项，包括其标识符（即变量名称）、数据类型及描述。考题表格严格包含以下三列：

使用描述性名称（如 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当你确切知道循环次数时（计数循环）；WHILE当循环可能一次都不执行时（前测循环）；REPEAT ... UNTIL当循环至少需执行一次时，例如验证输入（后测循环）。描述迭代结构的回答需指出结构名称、说明条件检测位置，并阐明后果（零次或至少一次）。

常见操作

• 赋值（Assignment）：x ← 5（箭头符号；= 用于比较）。
• 输入/输出：INPUT variable，OUTPUT expression。
• 比较运算符 =，<>，<，>，<=，>=；逻辑运算符 AND，OR，NOT。
• 算术运算 + - * /，加号 DIV（整数除法）和 MOD（取余数）。
• 字符串操作：LENGTH，LEFT，RIGHT，MID，以及用于 拼接（Concatenation，即连接）的 &。

考试要求的伪代码

所有伪代码答案均依据剑桥发布的伪代码指南进行评分。请严格书写以下格式：

RAND(100) 生成从 0 开始到（但不包括）100 的实数。INT(RAND(100)) + 1 生成从 1 到 100 的整数。

两个习惯能在每道题中得分：声明你使用的每一个变量，并注明标识符表中的类型；在改变它的循环之前，初始化 初始化每一个 计数器 计数器和总数（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 随机选取一个秘密整数。用户不断猜测直到猜对为止；每次猜错后，程序提示“太低”或“太高”，最后输出总共猜了多少次。

标识符表：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

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

• 结构化英语 — 使用缩进和固定关键词的自然语言，适合高层次描述。
• 流程图 — 使用标准图形符号的图表：

• 伪代码 — 上述关键字表示法；最接近实际代码。

你应该能够进行任意一对之间的转换：每个 IF 是判断菱形，每个循环是回指箭头，序列是堆叠的矩形。

IF ... THEN ... ELSE ... ENDIF（结束IF）

*使用标准形状计算数值列表平均值的流程图

逐步求精 从高层大纲开始，并 展开每一步，直到其足够小以便编码。对于求 $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”。

*逐步求精：将每个高层步骤展开为详细伪代码

逻辑语句 是由比较运算符（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

优先级 （从高到低）：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) 等价（德摩根定律）— 有助于简化条件。

将句子转化为逻辑语句是试卷直接考查的技能。“任何5以下或65以上的人持票免费”变为Age < 5 OR Age > 65。“分数有效当且仅当它是从0到100之间的整数”变为Mark >= 0 AND Mark <= 100。“当文件读取完毕或已读取十条记录时循环停止”变为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；只有当测试数据包含负数时，你的追踪过程才能暴露这一缺陷。

算法题所需的编程基础

在编写或追踪算法之前，请使用第11.1.1–11.1.2页上的表达式与内置函数方法。TO_UPPER和TO_LOWER接受完整的字符串；而指南中的UCASE和LCASE则作用于单个字符。请遵循题目中的插入要求。

使用&拼接字符串；在拼接前需用NUM_TO_STR将数字转换为字符串。调用过程时使用CALL Name(arguments)；将函数作为表达式使用。SETDATE(day, month, year)用于构建DATE值。评估前检查类型：无效表达式的结果是ERROR，而非猜测的转换结果。

对于包含多个总计的流程图，请在循环开始前分别初始化每个累加器。在正确的分支上更新它们，推进计数器，然后测试终止条件。平均值计算应放在循环之后，并使用实际包含的数值个数。

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

• 将算法定义为一种不依赖于语言的、无歧义的、有限的、确定性的步骤序列。
• 正确使用三种结构——顺序、选择、迭代——并维护包含数据类型的标识符表。
• 通过分解与抽象对问题进行拆解，然后进行逐步细化。
• 编写可实际运行的伪代码：声明变量并遵循考试指定的伪代码风格。

常见错误

• 使用=赋值。赋值操作是←；=是比较操作。
• 忘记ENDIF、ENDWHILE、ENDCASE或NEXT。每种结构都必须有结束标记，且评分时检查的是该结构的结束词。
• 在循环开始前未初始化累加器或计数器，导致算法向一个从未存在的值添加内容。
• 在重复次数未知的情况下使用了FOR循环。读取直到哨兵值或正确猜测需要WHILE或REPEAT ... UNTIL。
• 写出Age > 65 OR < 5。OR和AND的两侧都必须是完整的比较表达式。
• 回答“解释为何使用分解”时，用三种不同的方式书写同一个好处。三分的题目需要三个不同的好处。