数据结构与算法 / 系统课时

伪代码阅读规范

伪代码阅读规范

伪代码描述如何从输入得到输出。读之前先找出本段的变量、下标起点、区间端点和终止条件,再翻译为实际语言的语法。同一本资料也可能为不同过程采用特定约定,应以该过程的定义为准。

学习目标

  • 读出赋值、判断、循环与返回的含义。
  • 逐次记录变量状态,核对下标、比较符号和退出条件。
  • 将同一算法写成 Python,并用边界样例核对行为。

常用约定

写法 含义 阅读时核对
x ← value 用右侧结果更新左侧变量 如 count ← count + 1,先读取旧值再写入新值
if … then … else 根据条件选择分支 检查是严格比较还是含等号,及分支的缩进范围
for i ← 0 to n - 1 本课约定遍历闭区间的整数 若 n=0,区间为空,不执行循环体
while condition 每轮前判断是否继续 若要证明终止,找出能向结束条件推进的状态,或明确提前退出条件
result ← f(x) 调用函数并保存返回值 核对输入、返回值、是否修改传入对象和可能的错误
A[i] 访问编号为 i 的元素 本课数组从 0 开始,合法位置为 0 到 n-1

Python 的 range(n) 在 n≥0 时从 0 开始,到 n 之前停止,正好覆盖本课的数组下标。Python 序列还允许负下标从末尾访问,翻译伪代码时别依赖这个行为掩盖下标算错。 Python enumerate 与 range Python 序列下标

逐步跟踪计数

以下过程接收整数序列 A 与目标 target,返回严格大于目标的元素个数。length(A) 由序列本身得到,避免调用时把长度传错。

text
COUNT-GREATER(A, target)
    count ← 0
    n ← length(A)
    for i ← 0 to n - 1
        if A[i] > target
            count ← count + 1
    return count

以 A = [4, 7, 2, 9]、target = 5 为例。

i A[i] 是否大于 5 本轮后 count
0 4 否 0
1 7 是 1
2 2 否 1
3 9 是 2

检查每一轮结束时,count 都等于已访问前缀中大于目标的元素个数。数组含有恰好等于目标的值时,它不计入。数组为空时,返回初始值 0。固定宽度或单位成本模型下,访问次数随长度线性增长,核心算法只用固定数量的变量。

翻译为可运行 Python

将下面代码保存为 pseudocode_reading_demo.py。函数使用 enumerate 按序得到下标与元素。默认只返回结果;演示用 trace=True 打印手工表对应的状态。调试输出会增加额外时间,测量算法时关闭它。 Python enumerate

python
def count_greater(values: list[int], target: int, *, trace: bool = False) -> int:
    count = 0
    for index, value in enumerate(values):
        if value > target:
            count += 1
        if trace:
            print(f"index={index}, value={value}, count={count}")
    return count


if __name__ == "__main__":
    result = count_greater([4, 7, 2, 9], 5, trace=True)
    print(f"result={result}")
    assert count_greater([], 5) == 0
    assert count_greater([5, 6, 5], 5) == 1

用 Python 3.11 或以上运行 python pseudocode_reading_demo.py,或者用下一课对应系统的解释器命令。

text
index=0, value=4, count=0
index=1, value=7, count=1
index=2, value=2, count=1
index=3, value=9, count=2
result=2

本课练习

把比较改为“大于等于”,先手算 [5, 6, 5] 的结果,再修改代码与断言。下一课准备独立的 Python 实验目录和测试入口。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

伪代码阅读规范

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通