C 语言第 3 章：算法基础——三种描述方式与流程图规范
这一章不写多少代码，但它决定后面四章能不能写对。算法是"解决问题的步骤"，而步骤一旦含糊，翻译成 C 就必然出错。教材举的三个例子——连乘、闰年判断、素数判定——看似简单，实际分别对应三种典型思维：循环累乘、逻辑条件组合、用数学性质缩小搜索范围。本章还要练一种能力：把脑子里的步骤用流程图或伪代码外部化，让自己能"看见"分支走向和循环边界。写程序时 90% 的逻辑错误，都能在一张画对的流程图上提前发现。
一、算法的概念与五个特性
算法是为解决某个问题而采取的方法与步骤。判断一段描述是不是算法，看它是否同时满足五条：
| 特性 | 含义 | 反例 |
|---|---|---|
| 有穷性 | 执行有限步后结束 | "不断加 1 直到找到答案"却没说明何时停 |
| 确定性 | 每一步含义唯一，无歧义 | "取一个较大的数" |
| 可行性 | 每步都能用基本运算实现 | "求出所有素数并求和"（无穷） |
| 输入 | 有 0 个或多个输入 | 求 1+2+…+100 可以没有输入 |
| 输出 | 至少有 1 个输出 | 算完不输出，等于没做 |
"输入可以是 0 个"和"输出至少 1 个"这两条不对称，常被忽略：没有输入的程序（如打印固定图案）仍是算法，没有输出的计算过程不是。
评价一个算法还要看四个维度：正确性（能得出正确结果）、可读性（别人看得懂）、健壮性（对非法输入有反应而不是崩溃）、效率（时间与空间开销）。Wirth 那句"程序 = 数据结构 + 算法"说的就是：先决定数据怎么组织，再决定步骤怎么走。
二、三个引例的算法步骤
连乘 1×2×…×100。 需要两个变量：累乘器 p（初值 1，不能是 0）和计数器 i（初值 1）。步骤是：p ← 1，i ← 1；当 i ≤ 100 时反复做 p ← p × i、i ← i + 1；最后输出 p。这里的关键是初值的选择由运算决定：累加初值取 0，累乘初值取 1。取错了结果恒为 0。
闰年判断。 判据是：
能被 4 整除且不能被 100 整除，或者能被 400 整除。
写成 C 表达式是 (y % 4 == 0 && y % 100 != 0) || y % 400 == 0。注意括号里的两个条件必须同时成立，"能被 4 整除"单独并不够——1900 能被 4 整除但不是闰年，2000 能被 400 整除是闰年。这条规则的实质是格里高利历对回归年长度的修正：4 年一闰多算了，所以整百年不闰；400 年又少算了，所以整 400 年补回来。
素数判定。 若 n 只能被 1 和自身整除，则 n 为素数。朴素做法是从 2 试除到 n−1，但只需试到 √n。理由是一个初等结论：若 n = a × b 且 a ≤ b，则必有 a ≤ √n——只要有一个因子，较小的那个一定不超过 √n。所以循环条件写成 i * i <= n（用乘法避免浮点开方误差），循环里一旦 n % i == 0 就立即判定非素数并跳出。
这个"用数学性质砍掉一半以上的搜索空间"的思路，在本章末尾的韩信点兵里会再出现一次。
三、三种描述方式
| 方式 | 优点 | 缺点 | 适用 |
|---|---|---|---|
| 自然语言 | 无需学习，人人能懂 | 有歧义、难检查边界 | 思路草稿、口头交流 |
| 流程图 | 直观，分支与循环一目了然 | 算法一复杂图就巨大，难修改 | 教学演示、中小规模算法 |
| 伪代码 | 紧凑，易转成代码 | 没有统一语法标准 | 算法设计与论文交流 |
三者的关系不是替代而是逐级细化：先用自然语言把想法讲清楚，再用流程图确认分支与循环没有漏掉出口，最后用伪代码把每一步变成可执行的操作。跳过中间任何一步，都会在编码时把错误放大。
还有一种常被教材补充的形式叫 N-S 图（盒图），它用嵌套的矩形代替带箭头的流程线，从结构上禁止了随意跳转，画出来更紧凑。
四、结构化流程图的画法
先认符号：
| 符号 | 形状 | 用途 |
|---|---|---|
| 起止框 | 圆角矩形或椭圆 | 开始、结束，每个图各一个 |
| 处理框 | 矩形 | 赋值、计算 |
| 判断框 | 菱形 | 条件判断，一进两出 |
| 输入输出框 | 平行四边形 | scanf、printf |
| 连接点 | 小圆圈 | 跨页或跨段连接 |
| 流程线 | 带箭头实线 | 执行方向 |
画法有五条规范：
- 单入口、单出口。整张图只有一个"开始"和一个"结束"。
- 除判断框外一进一出；判断框必须有两个出口，并且标注"是/否"（或 Y/N），不标就等于没画。
- 不允许孤立框和无出口的死循环。循环必须有能退出的路径。
- 自上而下、从左到右，尽量不交叉流程线；交叉时用连接点而不是画一条穿过别的框的箭头。
- 只用三种基本结构：顺序、选择、循环。这是结构化程序设计的核心结论——任何算法都可以仅用这三种结构组合表达，所以不需要 goto。
第 5 条最值得强调。教材里那些用箭头乱飞的"传统流程图"，在现代工程实践里是被明确反对的：箭头一多，程序的执行路径就无法静态推理，正确性也没法分段证明。能不能只画三种结构，是判断一张流程图是否合格的第一标准。
五、阶乘与数列的伪代码
阶乘用计数型循环，注意 0! = 1 这个边界：
输入 n
fac ← 1
i ← 1
while i <= n do
fac ← fac × i
i ← i + 1
end while
输出 fac
n = 0 时循环体一次都不执行，fac 保持 1，正好是 0! 的值——这说明循环条件写 i <= n 而不是 i < n，恰好把边界情形包含进来了。这是"循环边界"最典型的一道题。
斐波那契数列用三个变量滚动，避免递归的重复计算：
a ← 1, b ← 1
for i ← 3 to n do
c ← a + b
a ← b
b ← c
end for
输出 b
赋值顺序不能颠倒：先算 c，再让 a 取 b 的旧值、b 取 c。如果先写 a ← b 再写 b ← a + b，a 的旧值已经丢了，结果全错。"用临时变量保存中间结果"是交换与滚动类算法的通用技巧。
调和级数 1 + 1/2 + … + 1/n 则埋着另一个坑：1/i 在 C 里是整数除法，i ≥ 2 时恒为 0，累加结果是 1。必须写成 1.0 / i，把运算提升到浮点。
易错点
- 累加器初值写 0 是对的，累乘器初值写 0 就全错。初值由运算的单位元决定。
1/i整数除法。凡是分数累加，先检查分子分母的类型。- 闰年判据漏掉"整百年"与"整 400 年"两个条件。
- 判断框画成三出口，或不标"是/否"，读者无法确定分支去向。
- 素数判定循环到 n 而不是 √n，虽然结果对，但复杂度从 O(√n) 退化到 O(n)。
- 伪代码里用
←赋值却忘了区分"赋值"与"相等"，转成 C 时把=写成==或反之。
这一章在整门课里的位置
本章上承第 2 章的数据类型（每个变量都要先定类型才能参与运算），下启第 4、5、6 章。流程图里的矩形框对应第 4 章的顺序结构，菱形框对应第 5 章的选择结构，回路对应第 6 章的循环结构——本章画出的每一张图，后面都能一比一翻译成代码。反过来，后面写不出循环时，回到本章画一张流程图，问题通常立刻显形。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- C 语言程序设计 15 讲