5.1 算法与伪代码

第 4 章研究了各种结构：函数把输入映射为输出，关系记录连接，偏序表达依赖。现在我们提出一个新问题：

> 怎样用一个有限过程，把允许的输入转换成要求的输出？

这样的过程称为算法。算法经常出现在软件中，但它并不局限于编程语言。长除法、按照菜谱做菜、找出手牌中的最大值、按前置条件安排任务，都是过程。

什么样的过程才是算法

算法是为解决一个明确问题而设计的、有限且精确描述的步骤序列。

其中四个部分必须清楚：

1. 输入：过程接收什么数据；

2. 输出：过程承诺产生什么结果；

3. 允许步骤：每种操作都必须含义明确；

4. 终止：对每个允许输入，过程都在有限步后结束。

考虑问题“找出两个实数中较大的一个”。

• 输入：实数 $a,b$；

• 输出：$\max(a,b)$；若二者相等，就输出这个共同值；

• 允许步骤：比较两个数并返回其中一个。

一个精确算法是：

LARGER(a, b)
    if a ≥ b
        return a
    else
        return b

缩进表示每个返回语句属于哪条分支。

与之相比，“看一看两个数，选择更好的那个”不是精确算法，因为“更好”没有定义，不同读者可能执行不同操作。算法必须精确到让相同输入遵循相同的指定规则。

算法不等于程序

算法是与语言无关的方法。程序是用 Python、JavaScript、Java 等具体语言实现这个方法。

同一个算法可以对应许多程序。伪代码让我们专注于核心推理，而不必先学习某种语言的语法。

阅读伪代码记号

本课程只使用一小组伪代码约定。

赋值

赋值会改变变量存储的值：

total ← 0
total ← total + 5

第一行执行后，$total=0$。第二行读取旧值，加上 $5$，再把新值存回去，所以最后 $total=5$。

箭头 $\leftarrow$ 不是数学等号。语句

表示更新，因此有意义；方程 $x=x+1$ 在实数中却没有解。

输入与返回

过程头

DOUBLE(x)

给出过程名称及其输入。语句

return 2x

会结束过程，并把 $2x$ 送回调用者作为输出。

顺序执行

除非控制结构另有规定，指令从上到下执行。

x ← x + 2
y ← 3x
return y

输入 $x=4$ 时，第一行把 $x$ 改为 $6$，第二行存储 $y=18$，最后返回 $18$。如果忽略中间更新，执行轨迹就会错误。

用追踪表看见状态变化

执行追踪记录算法在一个输入上的运行过程。追踪表列出每个重要步骤之后的变量值。

对于

MIX(a, b)
    a ← a + b
    b ← a - b
    return (a, b)

输入 $(a,b)=(3,5)$ 时：

追踪一个输入不能证明算法对全部输入都正确，但它会揭示赋值与控制流怎样运行。第 5.2 节会把这种观察提升为证明。

在指令甲板上重建被打乱的伪代码过程，再逐条执行。变量控制台会展示旧值与新值；步骤顺序错误时，系统会产生具体输出失败，而不是只显示笼统的“错误”。

条件执行

if 条件语句决定哪些指令会被执行。

ABSOLUTE(x)
    if x < 0
        return -x
    else
        return x

当 $x=-7$ 时，条件为真，过程返回 $7$；当 $x=4$ 时，条件为假，过程返回 $4$。

条件结构必须覆盖每个允许输入。如果算法只有

if x > 0
    return x

那么 $x=0$ 或负数时的行为没有规定。遗漏情况是算法设计缺陷，不只是格式问题。

多个互斥情况可以使用 else if：

SIGN(x)
    if x < 0
        return -1
    else if x = 0
        return 0
    else
        return 1

输出可以表示为分段函数：

这也连接回第 4 章：算法实现了一个从允许输入到输出的函数。

用循环进行重复

循环会重复一段指令。当重复次数由有限范围确定时，可以使用 for 循环。

SUM-TO(n)
    total ← 0
    for i ← 1 to n
        total ← total + i
    return total

对正整数输入 $n=4$，变量 $i$ 依次取 $1,2,3,4$：

算法返回

一般地，循环结束后

循环体通过缩进表示。如果把 return 放进循环内部，第一次迭代后过程就会结束，于是对每个 $n\ge1$ 都只返回 $1$。

while 循环必须产生进展

while 循环会在条件保持为真时重复：

COUNTDOWN(n)
    while n > 0
        output n
        n ← n - 1

更新 $n\leftarrow n-1$ 会让 $n$ 向停止条件靠近。如果缺少这个更新，正数输入就会造成无限循环。

设计 while 循环时要问：

1. 什么条件允许再执行一次？

2. 每次迭代改变了什么？

3. 为什么这个改变最终会使条件变成假？

这些问题正好为第 5.2 节的终止性证明做准备。

从规格说明设计算法

假设机器人从直线轨道的位置 $0$ 出发，需要收集位置 $1,2,\ldots,n$ 的包裹，并停在位置 $n$。它能理解：

• MOVE：前进一个位置；

• PICK：收集当前位置的包裹；

• REPEAT $n$ TIMES：把缩进块执行 $n$ 次。

一个正确且紧凑的算法是：

COLLECT-LINE(n)
    repeat n times
        MOVE
        PICK

顺序非常重要。若先 PICK 再 MOVE，机器人会先在没有包裹的位置 $0$ 尝试收集，并最终漏掉位置 $n$ 的包裹。

这个例子展示了一种实用设计过程：

1. 写清初始状态；

2. 找出重复的局部动作；

3. 选择能执行所需次数的循环；

4. 追踪一个小输入，也要包含最小允许输入；

5. 同时检查最终输出与终止性。

用移动、收集、条件与重复积木为包裹机器人编程。机器人会精确动画化执行轨迹，对不安全或不终止的控制流扣分，并奖励能够适用于多个轨道长度的紧凑程序。

本节衔接

现在我们能够描述算法，并追踪它在例子上的行为。但例子不能证明每个允许输入都会产生承诺的输出。第 5.2 节将引入前置条件、后置条件、循环不变量与终止性论证，把算法正确性变成可以证明的数学命题。