Algorithms

欢迎来到算法的世界！

你好！本章是计算机科学的核心。你可能觉得算法是复杂的代码，但实际上，它们仅仅是解决问题的绝妙方案。只要你会照着食谱做菜，你就能理解算法！

在这一节中，我们将学习如何正确地规划和构建计算机解决问题时所采取的步骤。无论是在编程还是其他领域，这种技能对于解决问题（problem solving）都是至关重要的。

如果起初觉得有些棘手，也不必担心。我们将把每个概念拆解成简单易懂的小步骤。

---

1. 定义算法：计算机的“食谱”

到底什么是算法？

算法只是一组用于解决特定问题或完成某项任务的定义明确、循序渐进的指令。

如果步骤执行正确，算法必须始终产生正确的结果，并且最终一定会结束。

优秀算法的关键特征：

• 清晰（Clear）：每个步骤都必须没有歧义（不让人产生困惑）。
• 有限（Finite）：它必须在有限的步骤后结束。它不能永远运行下去！
• 有效（Effective）：每条指令必须足够简单，以便于执行。

输入-处理-输出（IPO）模型

每一个程序和算法都遵循一个基本的结构，即 IPO 模型：

输入（INPUT） → 处理（PROCESS） → 输出（OUTPUT）

类比：泡一杯茶

• 输入：水、茶包、牛奶、糖。（你开始时使用的原始数据/原料）。
• 处理：烧水、浸泡茶包、加入牛奶/糖。（算法/步骤）。
• 输出：一杯泡好的茶。（结果/解决方案）。

在计算机科学中，输入可能是用户输入的一个数字，处理可能是将该数字与另一个数字相加，输出则是显示出来的结果。

---

2. 构建模块：控制结构

为了控制指令的执行流程，所有算法都使用三种基本结构。可以将它们视为你编写任何程序时所拥有的三大主要工具。

A. 顺序结构（按部就班）

顺序结构（Sequence）是最基本的结构。指令从上到下，一条接一条地执行。

• 先执行第 1 步，然后是第 2 步，再到第 3 步，以此类推。
• 示例：准备上学。
  1. 起床。
  2. 刷牙。
  3. 穿上校服。

B. 选择结构（做出选择）

选择结构（Selection）（或称决策）允许算法根据某个条件是“真”还是“假”，在两条或多条路径中做出选择。这通常使用 IF... THEN... ELSE（如果……那么……否则……）逻辑。

类比：交通信号灯决策

如果灯是绿的（条件为真）：那么通行。
否则（如果灯不是绿的，即红灯或黄灯）：那么停止。

关键点：选择结构意味着每次只遵循一条路径。

常见的选择结构：

• IF... THEN...（仅在条件为真时采取行动）
• IF... THEN... ELSE（条件为真时执行一种操作，为假时执行另一种操作）
• 嵌套选择（Nested Selection）（将一个 IF 语句放在另一个 IF 语句内部，用于处理复杂的决策）

C. 迭代结构（重复操作）

迭代结构（Iteration）（也称为重复或循环）意味着重复执行一组指令，直到满足特定条件为止。

当我们多次执行同一任务时（例如检查长列表中的每一个名字），就会用到迭代。

你需要了解两种主要的循环类型：

1. 固定迭代（FOR 循环）

当你确切知道循环需要运行多少次时使用。

示例： FOR（循环）10 次，举起哑铃。

2. 条件控制迭代（WHILE 循环）

当重复次数未知时使用。只要条件保持为真，循环就会持续 WHILE（当……时）运行。

示例： WHILE（当）密码不正确时，一直要求用户重新尝试。

给学生的警告：使用 WHILE 循环时要小心！如果条件永远无法变为假，算法就会无限运行下去。这被称为无限循环（infinite loop）——这是一种常见的编程错误！

---

3. 表示算法

在编写代码之前，你需要先规划好算法。我们主要使用两种工具来可视化或书写计划：

A. 流程图（可视化规划）

流程图（Flowchart）使用符号和线条来逐步展示逻辑流程。它们非常适合查看全貌，特别是在展示决策（选择）和循环（迭代）时。

你必须掌握的关键流程图符号：

符号	名称/形状	代表含义
椭圆形或圆角矩形	终端符号（Terminator）	算法的开始（START）或结束（END）点。
矩形	处理（Process）	数据被处理或执行计算的步骤（例如，将两个数字相加）。
平行四边形	输入/输出（I/O）	算法获取用户输入或显示输出的步骤。
菱形	决策（Decision）	对条件进行测试的点（例如：IF X > 10）。它有一个入口点和两个出口点（是/否 或 真/假）。
箭头	流线（Flow Line）	显示算法的执行方向。

B. 伪代码（结构化英语）

伪代码（Pseudocode）是一种使用结构化的英语来书写算法步骤的方法。它不是编程语言，但它使用常见的关键字（如 IF, WHILE, FOR, READ, PRINT）使结构变得清晰。

它非常适合在后续将你的计划轻松转换为任何编程语言。

伪代码片段示例：

READ Score
IF Score >= 50 THEN
    PRINT "Pass"
ELSE
    PRINT "Fail"
ENDIF

---

4. 常见的解决问题的算法

在解决问题时，计算机经常需要管理大量数据。其中最常见的两项任务是查找数据和排序数据。

A. 搜索算法

搜索算法是一种用于在数据集合中查找特定项的方法。

1. 线性搜索（或顺序搜索）

这是最简单的搜索方法。算法从头到尾逐个检查列表中的每一项，直到找到目标项或到达列表末尾。

• 适用情况：列表较小，或者列表未经过排序。
• 局限性：如果列表非常大，效率会非常低，因为它可能需要检查每一个项目。

2. 二分搜索

这是一种更快、更高效的搜索方法，但它有一个关键的前提条件：

数据列表在进行二分搜索之前，必须先经过排序。

类比：猜书页

如果你要在字典（已排序）中查找一个单词，你不会从第 1 页开始翻。你会大致翻开中间位置。

如果你要找的词在中间页之前，你就忽略书的后半部分。如果它在后面，你就忽略前半部分。

二分搜索的工作原理如下：

1. 找到列表的中间项。
2. 将目标项与中间项进行比较。
3. 如果不匹配，算法会立即剔除剩余数据中的一半。
4. 重复此过程，直到找到目标项。

对于大型的已排序数据集，二分搜索比线性搜索快得多。

B. 排序算法

排序算法是一种用于将数据元素按特定顺序（例如数字或字母顺序，升序或降序）排列的方法。

为什么我们需要排序？

我们对数据进行排序是为了让搜索变得更容易、更快捷（如二分搜索所示），并能清晰地呈现信息（例如按成绩排名的学生成绩单）。

概念示例：冒泡排序（简化版）

冒泡排序是最简单的排序方法之一。它重复遍历列表，比较相邻元素，如果顺序错误就交换它们。之所以叫“冒泡”排序，是因为小而轻的元素会像气泡一样慢慢“浮”到列表的顶部。

虽然它很容易理解，但与其它排序算法相比，在处理大型列表时效率并不高。

你已经成功掌握了规划计算问题的基础知识！现在你学会了如何使用顺序、选择和重复来给计算机下达指令。做得好！