# 算法跟踪

> CIE A-Level 计算机科学 · 第9单元：算法设计与问题求解
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-tracing/

算法跟踪（又称干运行）是CIE 9618试卷2的核心技能，需要你逐行遍历伪代码，记录变量变化并预测最终输出。本指南涵盖迭代、嵌套和递归算法的跟踪方法，以及针对考试的最佳实践。

**先修:** [CIE 9618 伪代码表示法](https://www.owlsprep.com/zh/study/cie-9618-u9-pseudocode-notation/); [控制结构：循环、条件语句和递归](https://www.owlsprep.com/zh/study/cie-9618-u9-control-structures/)

## 学习目标

- 逐步跟踪迭代、嵌套和递归算法的执行过程
- 在每个执行阶段正确记录变量值和输出
- 避开常见考试陷阱，在跟踪题中获得最高分

## 跟踪迭代算法

**算法跟踪（干运行）** — 逐步手动模拟算法执行的过程，在每个阶段记录每个变量的值和产生的所有输出。

> **tip**
>
> 适合考试的标准整理方法是制作表格：每个变量占一列，每个执行步骤占一行。这样能让阅卷人清晰看到你的解题过程。

**例题:** 跟踪下面计算前4个正偶数和的伪代码，找出最终输出：
```
sum ← 0
FOR count ← 1 TO 4
    number ← 2 × count
    sum ← sum + number
NEXT count
OUTPUT sum
```

1. 1. 进入循环前，初始化已声明的变量：
2. sum = 0，count和number未赋值
3. 2. 第一次循环迭代：count被设为1
4. number = $2 \times 1 = 2$，sum = $0 + 2 = 2$
5. 3. 第二次循环迭代：count自增到2
6. number = $2 \times 2 = 4$，sum = $2 + 4 = 6$
7. 4. 第三次循环迭代：count自增到3
8. number = $2 \times 3 = 6$，sum = $6 + 6 = 12$
9. 5. 第四次循环迭代：count自增到4
10. number = $2 \times 4 = 8$，sum = $12 + 8 = 20$
11. 6. count自增超过4后循环退出，最终输出为：
12. $$20$$

> **考试提示:** 一定要在任何循环或条件块运行前，先在跟踪表中填入变量初始值。正确的初始化几乎总能拿到1分。

## 跟踪嵌套控制结构

嵌套控制结构（循环内的if语句、循环嵌套）需要格外注意，要清楚你当前处于哪一级执行，哪些变量正在被更新。

**嵌套迭代** — 循环体内部包含另一个循环（内层循环）的循环结构。外层循环的每一次迭代都会完整运行一遍内层循环从开头到结束。

**例题:** 跟踪下面的嵌套伪代码，写出所有产生的输出：
```
FOR outer ← 2 TO 2
    OUTPUT "2 x: "
    FOR inner ← 1 TO 3
        product ← outer × inner
        OUTPUT product
    NEXT inner
NEXT outer
```

1. 1. 外层循环开始：outer = 2，输出字符串 `2 x: `
2. 2. 第一次内层循环迭代：inner = 1
3. product = $2 \times 1 = 2$，输出 `2`
4. 3. 第二次内层循环迭代：inner = 2
5. product = $2 \times 2 = 4$，输出 `4`
6. 4. 第三次内层循环迭代：inner = 3
7. product = $2 \times 3 = 6$，输出 `6`
8. 5. 内层循环退出，外层循环退出。完整输出为：
9. `2 x: 2 4 6`

> **warning**
>
> 不要忘记记录每一步产生的所有输出，而不只是最终输出。很多考题要求写出所有产生的输出，遗漏中间输出会失分。

> **考试提示:** 跟踪嵌套循环时，为外层和内层循环索引分别设列，避免在不同迭代间混淆。

## 跟踪递归算法

递归算法（用更小输入调用自身的函数）需要分别跟踪每一个调用栈帧，才能跟踪返回值，正确识别基线条件。

**调用栈帧** — 调用栈中为每个活跃递归调用单独分配的条目，存储该次调用的输入参数和返回地址。

**例题:** 跟踪下面定义的阶乘函数 $fact(n)$，输入为 $n=3$，找出最终返回值：
```
FUNCTION fact(n)
    IF n == 0 THEN
        RETURN 1
    ELSE
        RETURN n * fact(n - 1)
    ENDIF
ENDFUNCTION
```

1. 1. 初始调用：$fact(3)$，$n=3 \neq 0$ 因此需要计算 $3 \times fact(2)$
2. 2. 新调用：$fact(2)$，$n=2 \neq 0$ 因此需要计算 $2 \times fact(1)$
3. 3. 新调用：$fact(1)$，$n=1 \neq 0$ 因此需要计算 $1 \times fact(0)$
4. 4. 新调用：$fact(0)$，触发基线条件，返回 1
5. 5. 回退栈：$fact(1)$ 返回 $1 \times 1 = 1$
6. 6. 回退栈：$fact(2)$ 返回 $2 \times 1 = 2$
7. 7. 回退栈：$fact(3)$ 返回 $3 \times 2 = 6$
8. 最终返回值为：
9. $$6$$

> **考试提示:** 一定要清晰画出调用栈，用输入参数值标记每一次调用。阅卷人需要看到你理解执行和回退的顺序。

## 常见错误

- **错误做法:** 只写出每个变量的最终值，不在每一步后更新
  - 原因: 阅卷人70%-80%的分数都给中间步骤，因此哪怕最终输出正确，你也会丢失大部分分数
  - 正确做法: 每次变量值改变时，都在跟踪表中更新，不管变化看起来多么微不足道
- **错误做法:** FOR循环中的差一错误，提前一个迭代停止
  - 原因: CIE伪代码中的FOR循环包含起始和结束边界，因此当计数器等于结束值时也必须运行
  - 正确做法: 用（结束值 - 起始值 + 1）计算迭代次数，确认你步骤数正确
- **错误做法:** 嵌套循环中，忘记在外层循环每一次迭代时重置内层循环计数器
  - 原因: 这会导致内层循环执行错误，后续所有步骤的变量值都出错
  - 正确做法: 为外层和内层计数器分别设列，每次外层迭代时显式重置内层计数器
- **错误做法:** 递归中还没到基线条件就计算最终返回值
  - 原因: 递归调用依赖更深层调用的返回值，因此提前计算会导致结果错误
  - 正确做法: 先画出从初始输入到基线条件的所有调用，再向上回退计算返回值

## 速查表

| 算法类型 | 核心操作 | 考试得分提示 |
| --- | --- | --- |
| 迭代 | 先初始化变量，每一步都更新 | 正确初始化得1分 |
| 嵌套循环 | 内外层计数器分开放列 | 迭代次数 = 结束值 - 起始值 + 1 |
| 递归 | 画栈直到基线条件，再向上回退 | 每个正确栈帧都得分 |
| 任意跟踪 | 记录所有输出，不只是最终结果 | 遗漏输出 = 失分 |

## 下一步

算法跟踪是CIE 9618所有算法问题的基础技能，从排序、搜索到递归问题求解都需要它。掌握逐步跟踪不仅能帮你正确回答专门的跟踪题，还能让你在写开放性问题的原创算法时调试自己的伪代码，而开放性问题占了试卷2的大部分分数。持续的跟踪练习能提升速度，帮你避开考试中那些丢掉轻松得分机会的常见错误。

- [数据类型与结构](https://www.owlsprep.com/zh/study/cie-9618-u10-overview/)
- [原始数据类型](https://www.owlsprep.com/zh/study/cie-9618-u10-primitive-data-types/)
- [数组](https://www.owlsprep.com/zh/study/cie-9618-u10-arrays/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-tracing/