数据结构与算法 / 系统课时
伪代码阅读规范
伪代码阅读规范
伪代码描述如何从输入得到输出。读之前先找出本段的变量、下标起点、区间端点和终止条件,再翻译为实际语言的语法。同一本资料也可能为不同过程采用特定约定,应以该过程的定义为准。
学习目标
- 读出赋值、判断、循环与返回的含义。
- 逐次记录变量状态,核对下标、比较符号和退出条件。
- 将同一算法写成 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 实验目录和测试入口。
按自己的节奏,确认真正理解。