算法设计与问题求解

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

Analysis

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

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

Design

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

Coding and testing

在编码中你编写程序代码。你用迭代测试(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 ← x DIV 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)是你用来测试一个程序的数据。有四种你必须知道的类型。

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

Linear search

一个线性查找(linear search)逐个检查一个列表中的每个项,直到它找到它想要的值或到达末端。

found ← FALSE
FOR i ← 0 TO 9
    IF list[i] = searchValue THEN
        found ← TRUE
    ENDIF
NEXT i
OUTPUT found

Bubble sort

一个冒泡排序(bubble sort)把一个列表排序。它比较每对并排的项,若它们顺序错误就交换它们。它重复这个直到不再需要交换。

FOR i ← 0 TO 8
    IF list[i] > list[i + 1] THEN
        temp ← list[i]
        list[i] ← list[i + 1]
        list[i + 1] ← temp
    ENDIF
NEXT i

Totalling and counting

• 求和(totalling)——不断把值加到一个运行中的总数(total ← total + value)。
• 计数(counting)——每次某样东西发生时给一个计数器加 1(count ← count + 1)。

Maximum, minimum and average

• 要求最大值(maximum):保留到目前为止见过的最大值。
• 要求最小值(minimum):保留到目前为止见过的最小值。
• 要求平均值(average):把总数除以有多少个值。

total ← 0
FOR i ← 0 TO 9
    total ← total + list[i]
NEXT i
average ← total / 10
OUTPUT average

• 学习四个生命周期阶段:分析 → 设计 → 编码 → 测试。抽象只保留重要的细节;分解把一个问题分成更小的部分。
• 验证检查数据是合理的(范围、长度、类型、存在性、格式检查);核实检查它被正确地复制(一个目视检查或双重输入)。
• 学习四种测试数据类型:正常(被接受)、异常(被拒绝)、极端(仍被允许的最大/最小)、边界(一个限制两侧的值)。
• 要算出一个算法做什么,填一个追踪表——写下每个变量在每一步的值。
• 知道标准算法:线性查找(依次检查每个项)和冒泡排序(交换并排的对直到不需要交换)。