算法设计与问题求解

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

抽象

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

例子:

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

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

分解

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

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

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

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

当你开始一个算法时,在一个标识符表(identifier table)中列出每一份数据——它的变量(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 循环在每一趟之后测试(总是至少运行一次)。

常见操作

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

输入 → 处理 → 输出

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

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

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

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

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

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

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

逐步求精(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

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

一个逻辑语句(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))——对简化条件很方便。

例题。 写出标识符表和伪代码:读入 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 只有当你的测试数据里包含负数时,追踪才会把它暴露出来。

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