算法设计与问题求解

程序开发生命周期(program development life cycle)是用来制作一个程序的一套阶段。有四个阶段。

分析

在分析中你理解问题。两个关键技能有帮助:

• 抽象(abstraction)——只保留重要的细节并忽略其余的;
• 分解(decomposition)——把一个大问题分成更小、更容易的部分。

设计

在设计中你规划解决方案,常常用分解。你可以把各部分显示为一个结构图(structure diagram,一个把一个系统分成更小的框的图)中的子系统(sub-systems)。

编码与测试

在编码中你编写程序代码。你用迭代测试(iterative testing)——在你构建小部分时一遍又一遍地测试它们。在测试中你用测试数据(test data)运行整个程序以检查它工作。

你可以用三种主要方式规划一个解决方案。

• 一个结构图(structure diagram)——显示一个系统的各部分以及它们如何组合在一起;
• 一个流程图(flowchart)——一个用框和箭头按顺序显示步骤的图;
• 伪代码(pseudocode)——用简单的、类似代码的英语书写的步骤(不是一门真实的语言)。

一个算法(algorithm)是解决一个问题的一套步骤,以正确的顺序。每个算法能被分成三部分:

• 输入(input)——进去的数据;
• 处理(processing)——对数据做的工作;
• 输出(output)——出来的结果。

这叫分解成输入、处理和输出。例如,对于"求三个分数的平均值":输入是三个分数;处理是把它们相加并除以 3;输出是平均值。

当数据被输入时,你检查它以减少错误。

验证(validation)检查数据是合理的并遵循规则。它不能检查数据是真的,只能检查它是被允许的。

核实(verification)检查数据被正确地复制或输入(键入它时没有错误)。两种方法:

• 目视检查(visual check)——一个人把键入的数据与原始比较;
• 双重输入(double entry)——数据被输入两次,而两个副本被比较。

一个追踪表(trace table)一步步地记录一个算法运行时每个变量的值。它帮助你:

• 检查一个算法正确地工作;
• 通过用给定的数据跟随它来算出一个算法做什么。

例子:用输入 5 追踪这个算法。

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

追踪显示算法把 1 到 n 相加。用输入 5,输出是 15。

例题。 追踪这个算法并给出输出。

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV 只取除法的整数部分。每循环一次写一行:x 变成 10(count 为 1),然后 5(count 为 2),然后 2(count 为 3),然后 1(count 为 4)。此时 x > 1 为假,所以循环结束,输出是 4。有两个习惯能保住这些分:在每次循环之前而不是之后检验条件;以及每一次循环都新写一行 - 想把这些值记在脑子里,正是追踪出错的原因。

测试数据(test data)是你用来测试一个程序的数据。有四种你必须知道的类型。

你必须知道这些常见的算法。

线性查找

线性查找 从列表开头开始，将每个项目与目标值逐一比较。当找到目标值或列表结束时无需继续查找。列表不需要预先排序。以下示例使用位置 1 到 4。

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
    I ← I + 1
ENDWHILE
OUTPUT Found

范例对比。 查找 5 时依次比较了 8、3 和 5：共三次比较，此时 Found 变为 TRUE。第四个元素未被检查。查找 9 时需比较所有四个值；Found 保持为 FALSE。在尝试读取位置 5（超出此数组范围）之前停止。

冒泡排序

冒泡排序 将列表按序排列。比较相邻的值，如果左侧值大于右侧值则交换它们。通常情况下单次遍历不足以完成排序。这种完整版本会重复遍历，直到某次遍历中没有发生任何交换为止。

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
    Swapped ← FALSE
    FOR I ← 1 TO 3
        IF List[I] > List[I + 1]
          THEN
            Temp ← List[I]
            List[I] ← List[I + 1]
            List[I + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]

例题演示。 初始状态为8, 3, 5, 1。在第一轮遍历中，列表依次变为3, 8, 5, 1、3, 5, 8, 1、3, 5, 1, 8。这将最大值移至末尾，但其余元素仍无序。第二轮遍历结束于3, 1, 5, 8；第三轮结束于1, 3, 5, 8。第四轮未发生交换，确认该版本可以停止。每轮开始时将Swapped重置为FALSE；每次发生交换时将TRUE设为相应值。

累加与计数

求和 将每个所需值累加到运行总和中：Total ← Total + Value。计数 对每个所需项目加 1：Count ← Count + 1。在处理数值前将两者均初始化为零。

范例示例。 四次尝试输入的值为 −20、4、50 和 6。仅当值大于 −20 且小于 50 时才接受。本例处理的是四次尝试，而非四个被接受的值。

DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
    INPUT Value
    IF Value > -20 AND Value < 50
      THEN
        Total ← Total + Value
        Count ← Count + 1
    ENDIF
NEXT I
IF Count > 0
  THEN
    OUTPUT Total, ", ", Count, ", ", Total / Count
  ELSE
    OUTPUT "No accepted values"
ENDIF

严格限制排除了−20和50。两个更新都属于接受测试内部，因此被拒绝的尝试不会改变总数或计数。已接受值的平均值为：

不要除以四：只有两个值被添加。如果没有值被接受，计数为零，无法计算平均值；应输出提示信息代替除以零的操作。

转移至固定数量的已接受值。 如果任务要求50个已接受值而非四次尝试，请将固定的FOR循环替换为WHILE Count < 50并用ENDWHILE关闭。在其内部保留相同的输入和接受测试。被拒绝的输入不会更改Count，因此会请求另一个输入。完成时Count等于50，尽管尝试次数可能更多。输出总数并按Total / Count计算平均值。

最大、最小与平均

最大值 是最大的值，最小值 是最小的值。平均值 是总数除以值的数量。对于非空列表，从其第一个元素初始化两者。对于每个剩余元素，如果新值更大则替换最大值，如果更小则替换最小值。

示例。 列表为−8, −3, −12, −5。从零开始初始化最大值会失败：没有列表项大于零，算法将输出一个不在列表中的数字。从−8开始有效，无需假设数据为正数。

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
    IF List[I] > Maximum
      THEN
        Maximum ← List[I]
    ENDIF
    IF List[I] < Minimum
      THEN
        Minimum ← List[I]
    ENDIF
    Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4

最大值为−3，最小值为−12。平均值使用全部四个值计算：

平均值位于最小值和最大值之间；这是一个有用的检查，并非证明计算正确的依据。从第一个元素初始化需要非空列表。在读取该元素之前，需单独处理空列表的情况。

• 四个生命周期阶段：分析 → 设计 → 编码 → 测试。抽象保留关键要素；分解将问题拆分为若干部分。
• 验证检查数据是合理的(范围、长度、类型、存在性、格式检查);核实检查它被正确地复制(一个目视检查或双重输入)。
• 掌握四种测试数据类型：正常数据（被接受）、异常数据（被拒绝）、极端数据（允许范围内的最大/最小值）、边界数据（限值两侧的数据）。
• 跟踪表（记录每一步每个变量的值）展示了算法的执行过程。
• 知道标准算法:线性查找(依次检查每个项)和冒泡排序(交换并排的对直到不需要交换)。