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

编写第一个算法实验

编写第一个算法实验

上一课建立了独立的 Python 实验环境。本课完成数组求和,并把输入契约、正确性理由和可运行测试放进同一目录。

学习目标

  • 用函数契约写清求和的输入、输出及空数组行为。
  • 用循环不变式解释累加器为什么得到正确结果。
  • 验证正常、边界、大整数和输入不被修改的情况。

契约和循环状态

函数接收整数列表,返回全部元素的和,不改变原列表。空列表的和为 0。示例 [3, 5, -2, 8] 的和是 14。类型标注说明约定的输入,本例不逐个校验外部传入的类型。

处理完前 k 个元素后,total 等于这 k 个元素的和。循环开始前,k=0,累加器为 0,符合约定;每轮加上下一个数,使结论对新前缀继续成立;处理完整个列表时,这个前缀就是原列表。这是循环不变式的初始化、保持、终止三个检查点,下一章会详细展开。

循环访问每个元素一次。将整数读取和加法视为单位操作时,访问与加法次数是 n,故时间随输入长度线性增长,另用固定数量的变量。Python 整数可增长到任意精度,极大整数的加法和累加器字节数仍受位数影响。这里的常数额外空间按变量数量和单位字长模型理解。 Python 整数类型

实现与运行

在 algorithm-lab 根目录创建 sum_array.py。

python
def sum_array(numbers: list[int]) -> int:
    total = 0
    for value in numbers:
        total += value
    return total


if __name__ == "__main__":
    values = [3, 5, -2, 8]
    print(f"输入数组: {values}")
    print(f"求和结果: {sum_array(values)}")

Linux 或 macOS 使用 ./.venv/bin/python sum_array.py,Windows PowerShell 使用 & .\.venv\Scripts\python.exe sum_array.py。

text
输入数组: [3, 5, -2, 8]
求和结果: 14

用自动化测试复核边界

在同一项目的 tests/test_sum_array.py 写入以下代码。从项目根目录用上一课的 -m unittest discover -s tests -v 运行。若保留环境测试,应通过 7 项,其中 4 项针对求和。只运行求和测试文件时,可在发现命令中追加 -p test_sum_array.py。 Python unittest 发现与过滤

python
import unittest

from sum_array import sum_array


class ArraySumTest(unittest.TestCase):
    def test_empty(self):
        self.assertEqual(sum_array([]), 0)

    def test_mixed_and_unchanged(self):
        values = [3, 5, -2, 8, 0]
        original = values.copy()
        self.assertEqual(sum_array(values), 14)
        self.assertEqual(values, original)

    def test_single(self):
        self.assertEqual(sum_array([-7]), -7)

    def test_big_integers(self):
        self.assertEqual(sum_array([2**80, -2**80, 7]), 7)

如果混合样例只返回第一个数,检查 return 是否缩进在循环内部。如果只剩最后一个数,检查是否误用 total = value。如果空列表抛出下标错误,检查是否用首元素初始化。单元测试验证覆盖到的输入,不替代对任意合法输入的正确性推理。

本课练习

写出只累加偶数的循环不变式,核对 [1, 2, 3, 4, 5] 的结果为 6,并加上空列表测试。再将 list(range(1, 10001)) 与公式结果 50005000 比较。下一章从集合与序列开始,继续学习求和、证明和循环不变式。

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

目录与阅读设置

阅读设置

17

记录一个想法

编写第一个算法实验

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

登录哪都通