AS Level 计算机科学 (9618) 学习笔记

第9章：算法设计与问题求解

你好！欢迎来到计算机科学的核心地带。本章的主题是学习计算机的思维方式——或者更准确地说，我们该如何“教”计算机思考。算法设计是将现实世界的问题转化为机器可以执行的分步解决方案的一项关键技能。

如果你能掌握这里的逻辑技巧，编程将变得轻松许多。如果起初觉得这些概念比较抽象，不必担心，我们将通过生活中的例子把它们拆解开来！

9.1 计算思维技能

计算思维 (Computational Thinking) 是我们利用基于计算机的方法高效解决问题时所运用的一系列心智工具。其中最重要的两项技能是抽象和分解。

A. 抽象 (Abstraction)

抽象是指专注于问题的本质特征，同时忽略或隐藏无关的细节。

当你为一个系统创建抽象模型时，你只需要包含解决当前问题所必需的细节。

类比：使用地图

想象一下，你正在使用 GPS 导航回家。

  • 地图展示了必不可少的细节：道路、路口和你当前的位置。
  • 它忽略了无关细节：每辆车的颜色、树上有多少片叶子，或者每家商店的名字。

这种经过过滤的视图就是一个抽象模型。如果地图包含了一切信息，它将变得过于复杂而无法用于导航。

为什么要使用抽象？

  • 它简化了复杂系统，使其更易于管理和理解。
  • 它允许开发者专注于核心功能，而不被具体的实现细节所困扰。
  • 它有助于清晰地定义必要的数据和处理过程。

快速复习：抽象的核心在于过滤掉噪音（非必要细节），以捕捉信号（必要细节）。

B. 分解 (Decomposition)

分解是将一个庞大而复杂的问题拆解为更小、更易于管理的子问题（或任务）的过程。然后，可以逐一解决这些子问题。

类比：烤蛋糕

烤一个复杂的生日蛋糕是一项艰巨的任务，但你可以将其分解：

  1. 制作海绵蛋糕胚（子问题 1）。
  2. 准备糖霜（子问题 2）。
  3. 装饰蛋糕（子问题 3）。

每个子问题都更容易解决，并且可以单独完成或分配给他人。在编程中，这些子问题通常会成为程序模块，例如过程 (Procedures) 或函数 (Functions)。

分解的好处：

  • 使问题更容易解决和调试。
  • 允许不同团队（或通过编写独立的模块）同时开发程序的各个部分。
  • 这些模块通常可以在其他项目中重复使用。

要点回顾：计算思维为我们提供了框架：分解负责把任务拆解，抽象负责简化所得的各个部分。

9.2 算法

A. 定义算法

算法是一组定义明确、按顺序排列的步骤或指令，遵循这些步骤即可保证问题的解决。

将算法想象成烹饪菜谱：它会准确告诉你需要采取哪些步骤、按什么顺序操作、使用哪些特定成分（数据），从而得到可预期的结果（解决问题）。

B. 算法的表示方法

在编写实际代码之前，我们需要用特定的方式写出算法。大纲要求你熟悉三种主要的表示形式：

1. 结构化英语 (Structured English) 或叙述描述

这是一种使用简明英语结合保留关键字（如 IF, THEN, ELSE, WHILE）来清晰描述逻辑的方法，适用于高层次的描述。

示例：IF 分数大于 90 THEN 输出 "优秀"。

2. 流程图 (Flowcharts)

流程图使用图形符号来展示步骤的顺序、控制流以及算法的逻辑。

你必须掌握标准符号：

  • 椭圆形： 开始/结束 (起止框)
  • 平行四边形： 输入/输出
  • 矩形： 处理/计算
  • 菱形： 决策/选择（通常询问“是/否”问题）
  • 箭头： 流程线（展示控制方向）
3. 伪代码 (Pseudocode)

伪代码是一种非正式的人工语言，旨在帮助程序员开发算法。它不依赖于任何特定的编程语言，但遵循通用的结构约定（如 IF, WHILE, FOR）。

重要性： 伪代码是你考试中编写算法的主要方式。它既详细到可以轻松转换为真实代码，又具备足够的可读性，方便人类理解逻辑。（请务必参考剑桥官方的伪代码指南来获取特定关键字！）

C. 使用标识符 (Identifiers)

解决问题时，我们需要为使用的数据（变量、常量、数组）命名。这些名字称为标识符。

规则： 一定要使用合适的标识符名称。它们应当具有明确意义，并准确反映数据的含义。

不推荐： x = y * 5
推荐： TotalCost = ItemPrice * Quantity

在考试中，你可能需要使用标识符表来记录问题中用到的数据：

标识符 数据类型 描述
NumItems INTEGER (整数) 存储购买的商品数量（必须为正数）。
ItemPrice REAL (实数) 存储单件商品的价格。

你知道吗？使用良好的标识符对于代码维护至关重要。如果五年后有人需要修改你的代码，他们会感谢你当初选择了有意义的命名！

9.2 算法结构：构建模块

所有算法，无论其复杂程度如何，都是由三种基本结构构建而成的：顺序、选择和迭代。

A. 顺序 (Sequence)

顺序意味着按照指令出现的先后顺序逐行执行。

示例（伪代码）：
INPUT Name
OUTPUT "Welcome"

B. 选择 (Selection) - 决策制定

选择允许算法根据条件（通常是布尔值：TRUE 或 FALSE）来决定执行哪条路径。

1. IF...THEN...ELSE

用于在两个或多个路径之间进行选择。

示例（伪代码）：
IF Temperature > 30 THEN
    OUTPUT "It's a hot day"
ELSE
    OUTPUT "It's comfortable"
ENDIF

2. CASE OF / OTHERWISE (SWITCH)

当你根据变量的单一值有许多固定的选项时，此结构非常有用。

示例（伪代码）：
CASE OF DayNumber
    1: OUTPUT "Monday"
    5: OUTPUT "Friday"
    OTHERWISE: OUTPUT "Weekend"
ENDCASE

C. 迭代 (Iteration) - 重复/循环

迭代允许一组指令被重复执行。

1. 计数控制循环 (FOR 循环)

重复固定的次数。

示例（伪代码）：
FOR Counter = 1 TO 10
    OUTPUT Counter
NEXT Counter

2. 前置条件循环 (WHILE 循环)

在循环体执行之前检查条件。如果条件初始为 FALSE，则循环体一次都不会执行。

示例（伪代码）：
WHILE Total < 100 DO
    INPUT Number
    Total = Total + Number
ENDWHILE

3. 后置条件循环 (REPEAT UNTIL 循环)

在循环体执行之后检查条件。这保证了循环至少会执行一次。

示例（伪代码）：
REPEAT
    INPUT Password
UNTIL Password = "secret"

常见错误警示： 学生经常混淆 WHILE 和 REPEAT UNTIL。记住：WHILE 先检查（可能执行 0 次）。REPEAT UNTIL 后检查（至少执行 1 次）。

要点回顾：所有软件逻辑仅由这三种结构构建而成：顺序、选择和迭代。

9.2 算法技术

D. 逐步求精 (Stepwise Refinement) - 自顶向下设计

逐步求精是将算法分解为越来越详细的层级的过程。你从一个非常通用的描述开始，逐步细化每个步骤，直到它详细到可以轻松编写代码。这是自顶向下设计 (Top-Down Design) 的核心。

过程示例：库存管理

第 1 层（高层）：
1. 启动库存系统。
2. 处理交易。
3. 生成报告。
4. 退出系统。

第 2 层（细化步骤 2）：
2. 处理交易：
    2.1 WHILE 未到当天结束 DO
    2.2     获取交易类型。
    2.3     IF 类型 = 销售 THEN 更新库存。
    2.4     IF 类型 = 到货 THEN 增加库存。
    2.5     ENDWHILE

当你达到第 3 层或第 4 层时，步骤就已经非常详细，可以直接转换为伪代码（或编程语言）。

E. 逻辑语句

逻辑语句使用布尔运算符（AND, OR, NOT）来定义算法的部分。它们对于复杂的选择和迭代条件至关重要。

示例： 如果学生得分超过 50 分 且 出勤率超过 80%，则通过。
IF Score > 50 AND Attendance > 80 THEN
    Pass = TRUE
ENDIF

标准算法（线性搜索与冒泡排序）

你必须能够为两种标准算法编写并追踪伪代码：线性搜索和冒泡排序。这些是与数组处理相关的必备技能（详见第 10 章）。

A. 线性搜索 (Linear Search)

搜索数组或列表的最简单方法。它从头开始按顺序（逐个）检查每个项目，直到找到目标项目或到达列表末尾。

过程：

  1. 从第一个元素（索引 0）开始。
  2. 将当前元素与目标值进行比较。
  3. 如果匹配，停止并返回索引。
  4. 如果不匹配，移动到下一个元素。
  5. 如果到达列表末尾，说明该项不存在。

性能： 对于大型数据集来说，它的速度较慢，因为在最坏的情况下，必须检查每一个项目。

线性搜索的伪代码示例：
FUNCTION LinearSearch(DataArray, Target)
    Found = FALSE
    Index = 0
    WHILE Found = FALSE AND Index < ArrayLength DO
        IF DataArray[Index] = Target THEN
            Found = TRUE
        ENDIF
        Index = Index + 1
    ENDWHILE
    IF Found = TRUE THEN
        RETURN Index - 1
    ELSE
        RETURN -1 // 表示未找到
    ENDIF
ENDFUNCTION

B. 冒泡排序 (Bubble Sort)

一种简单的排序算法，它通过重复遍历列表，比较相邻元素，如果顺序错误则交换它们。遍历列表的过程会一直持续直到列表有序为止。

类比：气泡上升

想象一杯汽水。最大、最重的气泡（最大值）会缓慢地“浮”到顶端，而较小的气泡则停留在底部。

过程：

  1. 从列表开头开始。
  2. 比较第一个元素和第二个元素。
  3. 如果顺序错误，交换它们。
  4. 移动到下一对（第二个和第三个元素）并重复。
  5. 持续此过程直到列表末尾（完成一轮）。此时最大的未排序项已处于其最终正确位置。
  6. 重复整个过程，每轮比较范围缩减一项，直到某一轮中没有发生任何交换为止。

性能： 冒泡排序对于大型数据集效率极低，尤其是当数据初始为随机乱序时。但其简洁性使其易于理解和实现。

冒泡排序伪代码示例（将大小为 N 的数组 A 按升序排列）：
PROCEDURE BubbleSort(A, N)
    SwapMade = TRUE
    Upper = N - 1
    WHILE SwapMade = TRUE DO
        SwapMade = FALSE
        FOR Index = 0 TO Upper - 1
            IF A[Index] > A[Index + 1] THEN
                Temp = A[Index]
                A[Index] = A[Index + 1]
                A[Index + 1] = Temp
                SwapMade = TRUE
            ENDIF
        NEXT Index
        Upper = Upper - 1
    ENDWHILE
ENDPROCEDURE

快速复习：算法设计基础
  • 计算思维： 使用抽象（简化）和分解（拆解）。
  • 算法： 解决问题的定义明确的步骤序列。
  • 表示形式： 流程图（图表）、结构化英语（叙述）、伪代码（结构化文本）。
  • 结构： 顺序、选择 (IF/CASE)、迭代 (FOR, WHILE, REPEAT UNTIL)。
  • 技术： 逐步求精（逐步增加细节）。