第02课 · 算法——程序的灵魂

教材第2章《算法——程序的灵魂》（书页 15–36，共 22 页）｜ 时长：2h ｜ 日期：10/29

本章是全书最重要的一章，也是最"不像编程"的一章：几乎不写 C 代码，只练"想清楚步骤"。但它决定了你后面 8 章学得顺不顺——第 3~5 章的顺序、选择、循环，全是从这章的"三种基本结构"长出来的。

📖 背诵清单（先背这个，再往下看）

下面 11 块是第 2 章要背的全部内容，忠于教材原文，完整列出。先背熟，再进入后面的理解讲解。

1. 程序的组成公式（2.1）

一个程序主要包括以下两方面的信息：

1. 对数据的描述。在程序中要指定用到哪些数据，以及这些数据的类型和数据的组织形式。这就是数据结构（data structure）。
2. 对操作的描述。要求计算机进行操作的步骤，也就是算法（algorithm）。

著名计算机科学家沃思（Nikiklaus Wirth）提出一个公式：

算法 + 数据结构 = 程序

一个过程化的程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，算法、数据结构、程序设计方法和语言工具 4 个方面是一个程序设计人员所应具备的知识。

2. 什么是算法（2.2）

广义地说，为解决一个问题而采取的方法和步骤，就称为"算法"。

本书所关心的只限于计算机算法，即计算机能执行的算法。

3. 算法的 5 个特性（2.4）

一个有效算法应该具有以下特点：

1. 有穷性。一个算法应包含有限的操作步骤，而不能是无限的。（"有穷性"往往指"在合理的范围之内"——一个要运行 1000 年才结束的算法，虽然是有穷的，但人们也不把它视为有效算法。）
2. 确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。算法的含义应当是唯一的，不应当产生"歧义性"。
3. 有零个或多个输入。所谓输入，是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。
4. 有一个或多个输出。算法的目的是为了求解，"解"就是输出。没有输出的算法是没有意义的。（算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法得到的结果就是算法的输出。）
5. 有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。例如，若 b=0，则执行 a/b 是不能有效执行的。

4. 表示算法的常用方法（2.5）

常用的方法有：自然语言、传统流程图、结构化流程图（N-S 流程图）、伪代码。

5. 流程图常用符号（2.5.2）

一个流程图包括以下几部分：（1）表示相应操作的框；（2）带箭头的流程线；（3）框内外必要的文字说明。

6. 三种基本结构和共同特点（2.5.3）

1966 年，Bohra 和 Jacopini 提出了以下 3 种基本结构：

1. 顺序结构。A 和 B 两个框是顺序执行的：在执行完 A 框所指定的操作后，必然接着执行 B 框所指定的操作。顺序结构是最简单的一种基本结构。
2. 选择结构（又称选取结构或分支结构）。此结构中必包含一个判断框。根据给定的条件 P 是否成立而选择执行 A 框或 B 框。无论 P 条件是否成立，只能执行 A 框或 B 框之一，不可能既执行 A 框又执行 B 框。A 或 B 两个框中可以有一个是空的（不执行任何操作）。
3. 循环结构（又称重复结构），即反复执行某一部分的操作。有两类：
• 当型（while 型）循环结构：当给定的条件 p1 成立时，执行 A 框操作；执行完 A 后，再判断 p1 是否成立，如果仍然成立，再执行 A 框……如此反复执行 A 框，直到某一次 p1 条件不成立为止。
• 直到型（until 型）循环结构：先执行 A 框，然后判断给定的 p2 条件是否成立；如果 p2 条件不成立，则再执行 A……如此反复执行 A，直到给定的 p2 条件成立为止。

以上 3 种基本结构，有以下共同特点：

1. 只有一个入口。
2. 只有一个出口。（注意：一个判断框有两个出口，而一个选择结构只有一个出口，不要混淆。）
3. 结构内的每一部分都有机会被执行到（每一个框都应当有一条从入口到出口的路径通过它）。
4. 结构内不存在"死循环"（无终止的循环）。

7. 结构化算法（2.5.4 末）

归纳起来可知：

• 一个结构化的算法是由一些基本结构顺序组成的；
• 在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内（如循环中流程的跳转）；
• 一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变；
• 如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。

8. N-S 流程图（2.5.4）

• 1973 年，美国学者 I. Nassi 和 B. Shneiderman 提出。
• 在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他从属于它的框。
• 又称 N-S 结构化流程图（N 和 S 是两位美国学者的英文姓氏的首字母）。因形似多层盒子，又称盒图（box diagram）。
• 优点：直观、形象、易于理解；比传统流程图紧凑易画；废除了流程线，上下顺序就是执行顺序。

9. 伪代码（2.5.5）

• 定义：用介于自然语言和计算机语言之间的文字和符号来描述算法。
• 它如同写文章一样，自上而下地写下来，每一行（或几行）表示一个基本操作。
• 特点：不用图形符号，书写方便，格式紧凑，修改方便，容易看懂，也便于向计算机语言算法（即程序）过渡。
• 用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用。

10. 结构化程序设计方法（2.6）

• 核心方法：自顶向下，逐步细化。
• 用第一种方法（自顶向下）考虑周全，结构清晰，层次分明，作者容易写，读者容易看。发现某一部分中有一段内容不妥，只须找出该部分修改，与其他部分无关。
• 结构化程序设计方法用来解决人脑思维能力的局限性和被处理问题的复杂性之间的矛盾。
• 模块化设计：程序中子模块在 C 语言中通常用函数来实现；子模块一般不超过 50 行；划分时应注意模块的独立性（一个模块完成一项功能，耦合性愈少愈好）。模块化设计的思想实际上是一种"分而治之"的思想。
• 结构化编码（coding）：将已设计好的算法用计算机语言来表示，即根据已经细化的算法正确地写出计算机程序。

11. 设计与实现的关系（2.5.6）

• 完成一项工作，包括设计算法和实现算法两个部分。
• 计算机无法识别流程图和伪代码，只有用计算机语言编写的程序才能被计算机执行。因此，在用流程图或伪代码描述一个算法后，还要将它转换成计算机语言程序。
• 用计算机语言表示算法必须严格遵循所用语言的语法规则，这是和伪代码不同的。
• 设计算法的目的是为了实现算法。

课前一句话

这节课只解决一件事：把"想说清楚一件事"练成"每一步都精确到没有第二种理解"。学完你会明白——写程序 80% 的功夫不在敲键盘，而在动笔之前把步骤想清楚。

一、先补地基：为什么"算法"是程序的灵魂？

第 1 课我们说过一句话：

计算机很笨，但很快。它不会思考，只会一字不差地照着你写的"步骤清单"去做。

现在问题来了：

你想让它算 1×2×3×4×5 = 120。它凭什么会算？

计算机本身不认识乘法，也不认识"阶乘"这个词。它只会做极其简单的事：把两个数相加、比较大小、把数据搬来搬去。

所以你得告诉它：

1. 先准备一个"筐"，里面放 1
2. 再把 2 乘进去
3. 再把 3 乘进去
4. 再把 4 乘进去
5. 再把 5 乘进去
6. 把筐里的结果拿出来

这串步骤，就是算法。

拆名字：算 = 计算；法 = 方法、办法。合起来：算法 = 计算的方法和步骤。
教材给的定义更宽：为解决一个问题而采取的方法和步骤，就叫算法——所以"菜谱""乐谱""太极拳图解"都算算法，因为它们都是"照着做就能得到结果"的步骤。

打个比方（这个比喻本课从头用到尾）：

做一道菜 = 算法 + 数据结构
- 数据结构 = 原料：用哪些菜、多少克、怎么摆（对数据的描述）
- 算法 = 菜谱步骤：先下油、再下葱、炒几分钟（对操作的描述）

只有原料没有步骤，菜做不出来；只有步骤没有原料，也是空谈。 这就是沃思的公式：算法 + 数据结构 = 程序。

一个关键结论（本课反复回到这句）：

同一个问题，算法可以有好几种。方法有优劣之分——步骤少的、好懂的、不容易出错的，就是好算法。
例：1+2+…+100。笨办法是一步步加 99 次；聪明办法是 (1+100)+(2+99)+…+(50+51)=50×101=5050。两套步骤都是算法，但质量不同。

二、算法的 5 个特性（📖 要背）

这一节不要死背 5 个词。我们从那个"笨学徒"出发，一条条推出来。

特性 1：有穷性——步骤必须是有限的

问题：如果你告诉学徒"一直加下去"，他会永远加下去。你永远等不到结果。

所以：一个算法应包含有限的操作步骤，而不能是无限的。

教材补了一句很关键的话："有穷性"往往指"在合理的范围之内"。一个要跑 1000 年才结束的算法，虽然理论上有穷，但没人把它当有效算法。

反例：第 2.4 节的例子，如果把循环条件写成"只要分母大于 0 就继续加"，分母永远大于 0，循环永远不停——这就违反有穷性。

特性 2：确定性——每一步只能有一种理解

问题：你对学徒说"手举过头顶"。他会问：两只手还是一只手？举多高算过头顶？ 他不敢动。

所以：算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。算法的含义应当是唯一的，不应当产生"歧义性"。

反例（教材原例）：判断素数的算法里，如果写成"n 被一个整数除，得余数 r"——被哪个整数？ 没说清，没法执行。必须写成"n 被 i 除"。

所以写步骤时，每个变量是什么、从几开始、到几结束，都要交代得死死的。

特性 3：有零个或多个输入——可以不喂原料

输入 = 执行算法时需要从外界取得必要的信息。

• 求两个数的最大公约数：要输入 m 和 n → 两个输入
• 判断一个数是不是素数：要输入 n → 一个输入
• 求 5!：根本不用输入，题目已经把 5 写死了 → 零个输入

注意："零个输入"是合法的，不是错误。别一看到"输入"就以为必须有 scanf。

特性 4：有一个或多个输出——必须交出结果

算法的目的是为了求解，"解"就是输出。没有输出的算法是没有意义的。

• 素数判断的输出是"是素数 / 不是素数"
• 最大公约数的输出是一个数
• 可以有多个输出（比如输出 50 个学生里所有 80 分以上的人的学号和成绩）

这里的"输出"不限于屏幕或打印：算法得到的结果本身就是输出。

特性 5：有效性——每一步都得真能做得出来

算法中的每一个步骤都应当能有效地执行，并得到确定的结果。

反例：b = 0 时执行 a / b——数学上无意义，计算机也做不到，这一步就无效。

这条和第 2 条容易混：
- 确定性管的是"说得清不清楚"（有没有歧义）
- 有效性管的是"做不做得成"（能不能执行）
一句话：确定性 = 说得清；有效性 = 做得到。

一张表把 5 条钉死

三、三种基本结构：搭程序的三块积木（📖 要背）

先看问题：为什么非要"三种结构"？

早期的流程图有个大毛病——流程线可以随便乱跳。

教材把这个现象叫 BS 型算法：a bowl of spaghetti（一碗面条），线绕来绕去，看的人得拿着笔一路追，根本理不清逻辑。这样的算法难读、难改，可靠性没法保证。

怎么治？ 就像盖房子：不用想到哪砌到哪，而是先用几种标准预制件，按规矩拼起来。

1966 年，Bohra 和 Jacopini 给出了 3 种基本结构。任何复杂的算法，都能用这 3 块积木拼出来。

积木 1：顺序结构——一步一步往下走

┌─────┐
│  A  │
└──┬──┘
   ↓
┌─────┐
│  B  │
└─────┘

规则：执行完 A，必然接着执行 B。最简单的一块积木。

生活比喻：排队打饭——先刷卡，再端盘子，再走开。顺序不能乱。

积木 2：选择结构——岔路口二选一

        │
        ↓
     ╱ P ╲
    ╱     ╲
   Y       N
   ↓       ↓
 ┌───┐   ┌───┐
 │ A │   │ B │
 └─┬─┘   └─┬─┘
   └───┬───┘
       ↓

规则（三条，考试爱抠）：

1. 必包含一个判断框（菱形）。
2. 根据条件 P 是否成立，选择执行 A 或 B。
3. 只能执行 A 或 B 之一，不可能既执行 A 又执行 B。
4. A 或 B 可以有一个是空的（什么都不做，直接走）。

生活比喻：进门刷卡——卡对了走左边，卡错了走右边，不可能两条路同时走。

积木 3：循环结构——转圈跑

循环有两种，区别只在一个字：先判断还是先干活。

当型（while 型）：先看条件，成立才干活

     ┌──────────┐
     │          │
     ↓          │
  ╱ p1 ╲        │
 ╱      ╲       │
Y        N      │
↓        ↓      │
┌───┐    │      │
│ A │────┘      │
└───┘           │
                ↓
              （出口）

当 p1 成立时执行 A；执行完再判断 p1，仍成立就再执行 A……直到 p1 不成立为止。

直到型（until 型）：先干一次活，再看条件

     ┌──────────┐
     │          │
     ↓          │
 ┌───┐          │
 │ A │          │
 └─┬─┘          │
   ↓            │
 ╱ p2 ╲         │
╱      ╲        │
N        Y      │
└────────┘      ↓
             （出口）

先执行 A，然后判断 p2；p2 不成立就再执行 A……直到 p2 成立为止。

关键区别（必考）：
- 当型：条件先判断 → 可能一次都不执行
- 直到型：先执行一次再说 → 至少执行一次

例：教材图 2.18 和图 2.19 都在输出 1、2、3、4、5，一个问题两种循环都能做。

三种结构的 4 个共同特点（📖 要背）

1. 只有一个入口
2. 只有一个出口 —— 注意：一个判断框有两个出口，但一个选择结构只有一个出口。这两件事别混。
3. 结构内每一部分都有机会被执行到 —— 不许有"永远走不到"的框。
4. 结构内不存在死循环 —— 无终止的循环绝对不允许。

这 4 条可以当成"积木的质量检验标准"：一块积木如果满足这 4 条，它就是合格的基本结构。
教材还说：基本结构不一定只限这 3 种，你也可以自己定义（比如图 2.22 的多分支选择结构、图 2.23），只要满足这 4 个特点就行。但大家公认最基础的是这 3 种。

什么是"结构化的算法"（📖 要背）

把上面的东西串起来：

由一些基本结构顺序组成的算法，就是结构化的算法。
- 基本结构之间不许向前/向后乱跳；
- 跳转只允许发生在一个基本结构内部（比如循环里的回头）；
- 非结构化的算法，一定能用一个等价的结构化算法代替，功能不变；
- 反过来，拆不成基本结构的，就必然不是结构化算法。

四、四种"把算法写下来"的方式（📖 要背）

想清楚步骤以后，得记下来。教材给了四种工具，各有各的脾气——就像记菜谱，你可以口述、画图、画表格、写提纲。

方式 1：自然语言——用嘴说

优点：通俗易懂。 缺点：文字冗长，容易有歧义；描述分支和循环很别扭。

教材的例子超经典："张先生对李先生说他的孩子考上了大学"——到底是谁的孩子？光看这句话判断不了。这就是歧义。

结论：除了很简单的问题，一般不用自然语言表示算法。

方式 2：传统流程图——画图

用图框表示操作，用带箭头的流程线表示先后。

优点：直观形象，逻辑关系一眼看清。 缺点：占篇幅；算法一复杂，画起来又费时又不方便。

一个必须记住的细节：流程线不要忘记画箭头。没有箭头，就没法判断谁先谁后。

方式 3：N-S 流程图——去掉箭头的"盒子图"

核心思想：既然只用 3 种基本结构、按顺序拼，那箭头就是多余的——不是从上往下读就完了吗？

所以 N-S 图：

• 完全去掉带箭头的流程线
• 全部算法写在一个矩形框里
• 框里可以套框（盒图 box diagram）

优点：紧凑易画；上下顺序就是执行顺序，从上看下去就行。 而且：用 N-S 图画出来的算法必然是结构化的（因为根本没有地方可以乱跳）。

三种基本结构的 N-S 画法：

顺序                选择                    当型循环
┌─────────┐      ┌─────────────┐        ┌─────────────┐
│    A    │      │  当 P 成立？ │        │  当 p1 成立  │
├─────────┤      ├──────┬──────┤        ├─────────────┤
│    B    │      │  A   │  B   │        │      A      │
└─────────┘      └──────┴──────┘        └─────────────┘
                                          （回上去再判断）

选择结构的 N-S 图：上面一横条写条件，下面左右两半分别写 P 成立 / 不成立时做的事。
循环结构的 N-S 图：上面一横条写条件，下面一整块写循环体，默认回到上面再判断。

方式 4：伪代码——写给"半懂行"的人看

定义：用介于自然语言和计算机语言之间的文字和符号来描述算法。

它像写文章一样自上而下写，一行（或几行）表示一个基本操作。

优点：不用画图、写得快、改得快、好懂、离真代码最近。 缺点：不如流程图直观，容易把循环/选择的范围弄错。

伪代码没有严格语法，可以中英文混写，意思清楚就行。

例（教材例 2.16，求 5!）：

begin
    1 => t
    2 => i
    while i <= 5
    {
        t * i => t
        i + 1 => i
    }
    print t
end

=> 读作"存入"：1 => t 就是"把 1 放进 t 里"。
教材特意注明：写算法时用 =>，是为了和 C 语言的 =（赋值）区分开——在伪代码里 = 表示"等于"，=> 才是"放进去"。

四种方式一张表对比

教材的取舍：软件专业人员一般习惯用伪代码；本书为了照顾初学读者、便于理解，主要采用形象化的 N-S 图。但四种都要看得懂。

五、把算法变成程序：5! 的完整旅程（⌨️ 本课唯一的代码）

现在把前面学的全部串起来：同一个问题，从"话"走到"代码"。

第 1 站：自然语言（最笨的写法）

教材例 2.1：

步骤 1：先求 1 乘以 2，得到 2。
步骤 2：将步骤 1 得到的乘积 2 再乘以 3，得到 6。
步骤 3：将 6 再乘以 4，得 24。
步骤 4：将 24 再乘以 5，得 120。这就是最后的结果。

问题来了：如果求 1×2×…×1000 呢？要写 999 个步骤。显然不可取。

第 2 站：找准"规律"，引入变量和循环

教材的改写思路（这段是本章精华）：

设置两个变量：一个代表被乘数，一个代表乘数。不另设变量存放乘积，而是直接把每一步的乘积放回被乘数变量中。

设 t 为被乘数，i 为乘数，用循环来求：

S1: 1 => t          （把 1 放进 t）
S2: 2 => i          （把 2 放进 i）
S3: t × i => t      （t 乘 i，结果还放回 t）
S4: i + 1 => i      （i 加 1）
S5: 如果 i 不大于 5，返回重新执行 S3 及其后的 S4、S5；
    否则，算法结束。最后 t 的值就是 5! 的值。

为什么这样写就"通用了"？ 因为步骤的条数固定了（就 5 步），变的只是"转多少圈"。求 1000! 也只是把这 5 步跑 999 圈而已。

注意教材的一个细节：S3 里 t × i => t，结果放回 t 自己。这就是"累乘"——像往同一个筐里不断塞东西。
对比一下第 5 章会学的"累加" sum = sum + i：套路完全一样，只是乘法换加法。

第 3 站：画传统流程图

        开始
          ↓
       1 => t
          ↓
       2 => i
          ↓
     ┌→ t × i => t
     │    ↓
     │  i + 1 => i
     │    ↓
     │  i ≤ 5 ? ──N──→ 输出 t → 结束
     └────Y

读法：菱形是判断框，Y（Yes）表示条件成立，回到上面继续乘；N（No）表示不成立，跳出循环、输出结果。
这张图如果放到考试里，流程线的箭头一个都不能少。

第 4 站：画 N-S 图

┌───────────────────────┐
│        1 => t         │
├───────────────────────┤
│        2 => i         │
├───────────────────────┤
│      当 i ≤ 5          │
│  ┌─────────────────┐  │
│  │   t × i => t    │  │
│  │   i + 1 => i    │  │
│  └─────────────────┘  │
├───────────────────────┤
│       输出 t          │
└───────────────────────┘

注意 N-S 图的写法：条件写成一条横杠，循环体缩进在下面，默认"跑完回去再判断"，不用画箭头。

第 5 站：写伪代码（教材例 2.16）

begin
    1 => t
    2 => i
    while i <= 5
    {
        t * i => t
        i + 1 => i
    }
    print t
end

第 6 站：翻译成 C 语言（教材例 2.18）

#include <stdio.h>
int main()
{
    int i, t;              // 声明两个整型变量：i 当乘数，t 当"筐"
    t = 1;                 // S1：筐里先放 1
    i = 2;                 // S2：乘数从 2 开始
    while (i <= 5)         // S5：只要 i 不大于 5，就继续循环
    {
        t = t * i;         // S3：把 i 乘进筐里，结果仍放回 t
        i = i + 1;         // S4：乘数加 1
    }
    printf("%d\n", t);     // 输出结果（%d = 输出一个整数）
    return 0;
}

运行结果：

120

逐行对照：伪代码 → C 代码

重点理解 t = t * i：等号不是数学里的"相等"，而是"赋值"——把右边的计算结果，装进左边的变量里。
所以 t = t * i 读作："新的 t = 旧的 t 乘以 i"。左边和右边同名不矛盾，因为左边的 t 是"装结果的筐"，右边的 t 是"筐里原来的东西"。

上机验证（可选）

你的电脑里装了 Visual Studio 2022（Professional 版），新建一个"空项目 → 添加 .c 文件"就能编译运行。也可以把代码贴到任意在线 C 编译器跑。

本章的重点不是这个程序的语法（while、int 这些第 3~5 章才正式讲），而是：你能看着一份算法描述，知道它在说什么、它在哪一步转了弯。

六、书上题目（📝 重点，考试可能抽题）

第 2 章习题共 8 题，几乎全是"画图 / 写步骤"，正是考试最容易考的形式。

题 1（概念）：什么是算法？试从日常生活中找 3 个例子，描述它们的算法。

答：广义地说，为解决一个问题而采取的方法和步骤，就称为算法。

3 个例子：

1. 泡方便面

   ① 烧开水
   ② 撕开包装，取出面饼和调料包
   ③ 把面饼和调料放进碗里
   ④ 倒入开水，盖盖
   ⑤ 等 3 分钟
   ⑥ 打开，搅拌，吃

1. 从宿舍去教室

   ① 出门
   ② 判断：有共享单车吗？有→骑到教学楼；没有→走到教学楼
   ③ 进楼，看课表找教室号
   ④ 找到教室，坐下

1. 在银行取钱

   ① 插卡
   ② 输入密码
   ③ 判断：密码正确吗？不正确→重新输入；正确→下一步
   ④ 输入取款金额
   ⑤ 判断：余额够吗？够→出钞；不够→提示余额不足，退回
   ⑥ 取卡，拿钱

注意这三个例子里已经自然出现了顺序、选择、循环——你每天都在用算法，只是没意识到。

题 2（概念）：什么叫结构化的算法？为什么要提倡结构化的算法？

答： 结构化的算法是由一些基本结构顺序组成的算法。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内。

为什么提倡：

1. 结构清晰、层次分明，容易阅读、容易理解；
2. 各部分相对独立，容易修改、容易维护；
3. 容易检查正确性，可靠性高；
4. 非结构化的算法（如 BS 型"一碗面条"）可以用等价的结构化算法代替，功能不变但更好用。

题 3（概念）：试述 3 种基本结构的特点，请另外设计两种基本结构（要符合基本结构的特点）。

3 种基本结构的特点：

1. 顺序结构：A、B 顺序执行，执行完 A 必然接着执行 B。
2. 选择结构：含判断框，按条件 P 是否成立选择执行 A 或 B，只能执行其一。
3. 循环结构：反复执行 A。当型是先判断后执行（可能一次都不执行）；直到型是先执行后判断（至少执行一次）。

另设计两种（教材图 2.22、图 2.23 的思路）：

• 多分支选择结构：根据一个表达式的值，从多个框中选一个执行。

         ┌──────────────┐
         │ 按表达式的值选择 │
   ┌─────┼──────┬───────┼─────┐
   ↓     ↓      ↓       ↓
  A1    A2     A3      A4
   └─────┴──────┴───────┘

• "当型 + 直到型"组合结构（教材图 2.22 形式）：先执行一次，然后当条件成立时继续执行。

         ┌────────┐
         ↓        │
       ┌───┐      │
       │ A │      │
       └─┬─┘      │
         ↓        │
      ╱ p1 ╲──────┘
     ╱      ╲
    N        Y
    ↓        ↓
  （出口）

验证它们合格：都有一个入口、一个出口；每一部分都有机会被执行到；没有死循环。所以符合基本结构的特点。

这道题考的是：你不必只会书上那 3 种，只要满足 4 个共同特点，就是合格的基本结构。

题 4（画流程图，8 小问）

教材要求用传统流程图表示以下 8 个问题的算法。这里逐题给思路和流程图。

(1) 两个瓶子 A、B 分别盛醋和酱油，要求互换

思路（经典"三只杯子"）：只靠 A、B 两个瓶子换不了——A 倒进 B，B 原来的东西就没了。必须借第三个空瓶 t。

        开始
          ↓
       输入 A, B
          ↓
        A => t          （先把 A 的醋倒进空瓶 t）
          ↓
        B => A          （把 B 的酱油倒进 A）
          ↓
        t => B          （把 t 里的醋倒进 B）
          ↓
       输出 A, B
          ↓
        结束

这是本章最重要的一个"套路"，第 8 章讲指针时还会回来：交换两个数，永远需要第三个临时变量。
在 C 里就是三行：t = a; a = b; b = t;

(2) 依次输入 10 个数，输出其中最大的数

思路：设一个"当前最大值"变量 max。先让 max 等于第 1 个数，然后每读一个数就和 max 比一次，谁大就把谁放进 max。

        开始
          ↓
      输入第 1 个数 => max
          ↓
         i => 2
          ↓
  ┌→ i ≤ 10 ? ──N──→ 输出 max → 结束
  │     ↓Y
  │  输入第 i 个数 => x
  │     ↓
  │  x > max ? ──N──┐
  │     ↓Y          │
  │   x => max      │
  │     ↓←──────────┘
  │   i + 1 => i
  └─────┘

(3) 有 3 个数 a、b、c，要求按大小顺序输出

思路：两两比较，把大的往前挪。先让 a 和 b 比（a<b 就交换），再让 a 和 c 比，再让 b 和 c 比。三轮之后 a≥b≥c。

        开始
          ↓
      输入 a, b, c
          ↓
     a < b ? ─Y→ 交换 a, b
          ↓
     a < c ? ─Y→ 交换 a, c
          ↓
     b < c ? ─Y→ 交换 b, c
          ↓
      输出 a, b, c
          ↓
        结束

交换用题 (1) 的三只杯子法。这个"两两比较、冒泡前移"就是第 6 章冒泡排序的雏形。

(4) 求 1 + 2 + 3 + … + 100

思路：和第 5 节的 5! 一模一样，只是乘法换成加法，初值从 0 开始。

        开始
          ↓
      0 => sum
      1 => i
          ↓
  ┌→ i ≤ 100 ? ──N──→ 输出 sum → 结束
  │     ↓Y
  │  sum + i => sum
  │     ↓
  │   i + 1 => i
  └─────┘

累加三件套：sum = 0 起手 → sum = sum + i 累加 → i = i + 1 推进。
这三个动作背下来，第 5 章能省你一半力气。

(5) 判断一个数（如 77）能否同时被 3 和 5 整除

思路：两个条件同时满足。先判断能不能被 3 整除，不满足就直接判"不能"；满足再判断能不能被 5 整除。

        开始
          ↓
        n => 77
          ↓
    n 能被 3 整除 ? ──N──→ 输出"不能" → 结束
          ↓Y
    n 能被 5 整除 ? ──N──→ 输出"不能" → 结束
          ↓Y
       输出"能"
          ↓
        结束

注意这里用了两次选择结构串联。在 C 里，第 4 章会把它压缩成一个逻辑表达式：n % 3 == 0 && n % 5 == 0。

(6) 输出 100~200 之间的素数

思路：对 100~200 的每一个数 n，都用"试除法"判断它是不是素数：

• 用 2 到 √n 的每个整数 i 去除 n；
• 只要有一个除得尽（余数为 0），n 就不是素数，直接换下一个 n；
• 如果全部除不尽，n 就是素数，输出。

        开始
          ↓
       100 => n
          ↓
  ┌→ n ≤ 200 ? ──N──→ 结束
  │     ↓Y
  │   2 => i
  │     ↓
  │  ┌→ i ≤ √n ? ──N──→ 输出 n（是素数）
  │  │     ↓Y              ↓
  │  │  n 被 i 除的余数 r  │
  │  │     ↓               │
  │  │   r = 0 ? ─Y──────→（不输出，换下一个 n）
  │  │     ↓N              │
  │  │   i + 1 => i        │
  │  └─────┘               │
  │        ↓←──────────────┘
  │   n + 1 => n
  └─────┘

两个循环嵌套：外层控制 n 从 100 走到 200，内层控制 i 从 2 试到 √n。这就是"循环嵌套"，第 5 章的重点。
教材补充：实际不必试到 n−1，试到 √n 就够了——如果 n 能被大于 √n 的数整除，那它必然也能被小于 √n 的数整除。

(7) 求两个数 m 和 n 的最大公约数

思路：辗转相除法。用 m 除以 n 得余数 r；若 r≠0，则把 n 给 m、r 给 n，再除一次；直到 r=0 为止，此时 n 就是最大公约数。

        开始
          ↓
       输入 m, n
          ↓
  ┌→  m 被 n 除的余数 r
  │     ↓
  │   r = 0 ? ──Y──→ 输出 n → 结束
  │     ↓N
  │   n => m
  │     ↓
  │   r => n
  └─────┘

举例：m=12，n=8

• 12÷8 余 4 → r=4≠0 → m=8, n=4
• 8÷4 余 0 → r=0 → 最大公约数 = n = 4 ✓

(8) 求方程 ax² + bx + c = 0 的根（分两种情况）

思路：先算判别式 d = b² − 4ac，再根据 d 的符号分支。

        开始
          ↓
     输入 a, b, c
          ↓
    d = b² − 4ac
          ↓
    d ≥ 0 ? ──N──→ 输出"无实根" → 结束
          ↓Y
    d = 0 ? ──Y──→ 输出两个相等实根 x = −b/(2a) → 结束
          ↓N
  输出两个不等实根
  x1 = (−b+√d)/(2a)
  x2 = (−b−√d)/(2a)
          ↓
        结束

教材原题只要求"有两个不等实根"和"有两个相等实根"两种情况。完整版还要处理 d<0（无实根）和 a=0（不是二次方程）——真正的算法要考虑所有边界情况，这正是"确定性/有效性"的体现。

题 5（N-S 图）：用 N-S 图表示第 4 题中各题的算法。

只需把三种基本结构的"标准画法"套上去。以第 (4) 题 1+…+100 为例：

┌─────────────────────────┐
│        0 => sum         │
│        1 => i           │
├─────────────────────────┤
│      当 i ≤ 100          │
│  ┌───────────────────┐  │
│  │  sum + i => sum   │  │
│  │     i + 1 => i    │  │
│  └───────────────────┘  │
├─────────────────────────┤
│       输出 sum          │
└─────────────────────────┘

画 N-S 图的三个口诀：
1. 顺序 = 上下摞起来写；
2. 选择 = 上面一横条写条件，下面左右分开写两支；
3. 循环 = 上面一横条写条件，下面一整块写循环体，默认会回到上面。
全程不画箭头。

题 6（伪代码）：用伪代码表示第 4 题中各题的算法。

以第 (4) 题 1+…+100 为例：

begin
    0 => sum
    1 => i
    while i <= 100
    {
        sum + i => sum
        i + 1 => i
    }
    print sum
end

以第 (7) 题最大公约数为例：

begin
    input m, n
    m ÷ n 的余数 => r
    while r ≠ 0
    {
        n => m
        r => n
        m ÷ n 的余数 => r
    }
    print n
end

伪代码只要意思清楚就行，不用纠结语法。但循环的范围（{ } 里包哪几行）一定要写对——教材特意提醒，伪代码最容易出的错就是"循环或选择结构的范围弄错"。

题 7（概念）：什么叫结构化程序设计？它的主要内容是什么？

答： 结构化程序设计是一种程序设计方法，核心是自顶向下、逐步细化，用模块化的方式把复杂问题分解成若干子问题，再用三种基本结构组成的算法来实现，最后进行结构化编码。

主要内容：

1. 自顶向下，逐步细化：先想整体，再一层层拆细节。就像写文章先列提纲，再分章、分节、分段。
2. 模块化设计：把程序分成若干子模块（C 语言中用函数实现），每个子模块完成一项功能，规模一般不超过 50 行，耦合性愈少愈好——即"分而治之"。
3. 结构化编码：用结构化的语言（C、Basic 等）把算法翻译成程序。

目的：解决人脑思维能力的局限性和被处理问题的复杂性之间的矛盾。

教材的比喻特别形象：写文章先拟提纲（自顶向下），有的人不拟提纲想到哪写到哪（自下而上），前者结构清晰、好写好看；盖房子先做整体规划，再设计房间门窗，绝不会在没有整体方案之前先设计厕所。

题 8（自顶向下、逐步细化）：用逐步细化的方法设计算法

(1) 输出 1900—2000 年中的闰年

第一步（顶层设计）：问题可分成三块——

① 让 year 从 1900 走到 2000
② 对每一年，判断它是不是闰年
③ 是闰年就输出

第二步（细化"判断闰年"）：

闰年条件（两个条件之一满足即可）：
  A. 能被 4 整除，但不能被 100 整除
  B. 能被 100 整除，且能被 400 整除

第三步（继续细化成可执行步骤）：

year = 1900
当 year ≤ 2000 时：
    ├─ year 不能被 4 整除？         → 不是闰年
    ├─ 能被 4 整除，但不能被 100 整除 → 是闰年
    ├─ 能被 100 整除，也能被 400 整除 → 是闰年
    └─ 其他                          → 不是闰年
    若是闰年，输出 year
    year = year + 1

教材提醒：这里判断的先后顺序不能随便颠倒——必须先判断"能不能被 4 整除"，再判断"能不能被 100 整除"，最后判断"能不能被 400 整除"，这样才能一步步缩小范围。

(2) 求 ax²+bx+c=0 的根（按 d 的 3 种情况）

顶层设计：

① 输入 a, b, c
② 计算 d = b² − 4ac
③ 按 d 与 0 的关系分三种情况处理

细化第 ③ 步：

d > 0  → 两个不等实根
d = 0  → 两个相等实根
d < 0  → 无实根

再细化每种情况的计算公式（同题 4 (8)）。

(3) 输入 10 个数，输出其中最大的一个数

顶层设计：

① 读入第一个数，作为"当前最大值"
② 把剩下的 9 个数依次读入，每个都和"当前最大值"比较
③ 比较完输出"当前最大值"

细化第 ② 步：

i 从 2 到 10：
    读入第 i 个数 x
    如果 x > max，则 max = x

这就是自顶向下的样子：先写一句人话，再把这句人话拆成更具体的人话，直到每一句都能直接翻成代码。

🛠 随课练习（只给题不给答案，做完发我判，或自己对照教材）

本章的练习不用上机，用纸笔写，写完拍给我。

🔮 猜输出（基于第 5 节的 5! 程序，先猜再上机验证）

题 1：把 i = 2 改成 i = 3，其余不动，输出是多少？

题 2：把 while (i <= 5) 改成 while (i <= 6)，输出是多少？

题 3：把 while (i <= 5) 改成 while (i < 5)，输出是多少？

题 4：把循环体里两句的上下顺序对调（先 i = i + 1; 再 t = t * i;），输出是多少？

🛠 变式题（手写，写出完整步骤/图）

题 5（照猫画虎）：把 5! 改成求 1×3×5×7×9，写出伪代码。

题 6（改需求）：设计算法：输入 10 个数，输出其中最小的数。要求画传统流程图。

题 7（翻译）：把下面这段自然语言改成伪代码，并画 N-S 图：

输入一个学生的成绩 g（0~100）。如果 g ≥ 60，输出"及格"；否则输出"不及格"。然后输出"处理完毕"。

题 8（补全）：下面是"求 1+2+…+100"的流程图骨架，补上缺的两步：

开始 → sum=0, i=1 → [判断 i≤100?] ─N→ 输出 sum → 结束
                        ↓Y
                    【 ① 】
                        ↓
                    【 ② 】
                        ↓
                     （回到判断）

🐛 改错题（找出违反哪条特性 / 错在哪，并改正）

题 9：下面的算法有什么问题？

S1: 输入 n
S2: 让 i 从 2 开始
S3: 用 n 除以 i
S4: 如果除得尽，n 就不是素数，结束
S5: 如果除不尽，i 加 1，返回 S3

（提示：看"有穷性"和"确定性"哪条被违反了。）

题 10：下面的流程图错在哪？

开始 → 输入 a, b → c = a / b → 输出 c → 结束

（提示：想想 b=0 时会怎样，违反哪条特性。）

题 11：下面的算法描述有什么问题？

步骤 1：读入数据
步骤 2：对数据进行适当处理
步骤 3：输出结果

（提示：这条最典型，考"确定性"。）

题 12：下面这个"循环结构"违反三种基本结构的哪条共同特点？

开始 → i=1 → [i ≤ 5?] ─N→ 结束
                  ↓Y
              i = i + 1
                  ↓
              （回到判断）

（提示：想想循环体里到底有没有"干活"。）

📈 加练题（你随时喊，我随时追加到这里）

（暂无。想加练就说"再出几道 XX 题"，我出的题会标上日期追加在这块。）

💬 问答区（你问过的问题 + 我的解答）

（暂无。你问的问题和我的解答会按 Q/A 整理进这里。）

该带走的 5 句话

1. 算法 + 数据结构 = 程序：菜谱 + 原料，缺一不可。
2. 算法的 5 个特性：有穷、确定、零个或多个输入、一个或多个输出、有效——说不清 = 违反确定性，做不到 = 违反有效性。
3. 三块积木搭一切：顺序、选择、循环；循环里当型先判断（可能零次），直到型先执行（至少一次）。
4. 好的算法只有一个入口、一个出口，每部分都走得到，没有死循环——这就是"结构化"。
5. 写程序先写步骤，不是先敲键盘：先想清楚，再用流程图/N-S 图/伪代码记下来，最后才翻译成 C。

学完这一课，直接告诉我"下一课"，我们进入第 3 章《最简单的 C 程序设计——顺序程序设计》——从这一章开始，才真正动手写 C 代码，而第 3 章的第一件事就是：变量、数据类型、printf 和 scanf。