HW 3：可变性、树、迭代器与生成器ok 6 题通过1 题需课程私有口令

0. 这份作业在练什么

HW 3 一共七题，官方把它们分成三组：Mutability（可变性）一题、Trees（树）三题、Iterators / Generators（迭代器与生成器）两题，最后加一道课程问卷。这三组看似互不相干，其实是同一条主线上的三个台阶。

前两周你写的每个函数都遵守同一个契约：拿到参数，算出一个新值，返回它。函数外面的世界一点没变。这种函数叫「纯函数（pure function）」，它最大的好处是你只要盯着 return 那一行就能知道它干了什么。

从 Lecture 8 起，这个契约被打破了。列表（list）是可变对象（mutable object）：lst.append(3) 不返回任何有用的东西，它改变了列表本身。于是「谁指向这个列表」这件事第一次变得要命——如果两个名字指向同一个列表，改一个另一个也变了。Q1 inventory_pickup 就是专门为这件事设计的陷阱题：题面故意让 items 和 inventory 是同一个列表对象，逼你想清楚「一边遍历一边删」会发生什么。

第二组三道树题，练的是另一件事：数据抽象（data abstraction）加树递归。树在 61A 里不是 Python 内置类型，而是用列表拼出来的一套约定：tree(label, branches) 造树，label(t) 取根标签，branches(t) 取分支列表。课程反复强调：只准用这三个函数加 is_leaf，不许写 t[0]、t == x、len(t)。这道纪律不是形式主义——它保证了你写的代码在树的底层实现换掉之后仍然能跑，而这正是「抽象屏障（abstraction barrier）」的全部意义。

第三组两道生成器题，练的是把「一个函数」变成「一个可以暂停的过程」。yield 让函数在中途交出一个值、冻结全部局部状态、等下一次 next 再从原地醒来。有了它，你才能写出处理无限序列的程序——Q5 merge 的 doctest 里真的传了两个死循环生成器进去。

做之前应该会什么

Point breakdown
    inventory_pickup: 1.0/1
    berry_finder: 1.0/1
    size_of_tree: 1.0/1
    make_path: 1.0/1
    merge: 1.0/1
    yield_paths: 1.0/1
    midsem_survey: 0.0/1

Score:
    Total: 6.0

def midsem_survey(p):
    """
    You do not need to understand this code.
    >>> midsem_survey(passphrase)
    '2bf925d47c03503d3ebe5a6fc12d479b8d12f14c0494b43deba963a0'
    """
    import hashlib
    return hashlib.sha224(p.encode('utf-8')).hexdigest()

1. Q1 inventory_pickup：一边遍历一边改的陷阱

题目要什么

函数签名是 inventory_pickup(inventory, items, capacity)。想象一个游戏背包：inventory 是当前背包里的东西（一个列表，从左到右按「最早捡到的在最前面」排序），items 是这一轮要捡起来的东西，capacity 是背包容量。

规则拆成两段，题面用 Timing 一节特意强调了两段的先后顺序：

另外两条硬性约束，比规则本身更容易踩：

• 必须就地修改（in place）：不许 inventory = [...] 重新绑定，不许返回一个新列表。函数返回的必须是那个原来的列表对象本身。doctest 里 check_mutation is inv3_test 要求为 True，用的是 is（对象标识）而不是 ==，专门卡这一点。
• items 可能就是 inventory 本身。题面的 Hint 直接点破了：items may be the SAME list object as inventory。doctest 第二、三例正是 inventory_pickup(inv2, inv2, 7) 和 inventory_pickup(inv3, inv3, 3)。

把六个 doctest 摆在一起看，每个都在测一件不同的事：

怎么想到的

先写一个「显然正确」的版本，看它在哪儿崩——这是本题最好的学法。

第一版（天真版）：

for item in items:
    if item in inventory:
        inventory.remove(item)
    inventory.append(item)

拿用例 1 试：inventory = [1,2,1,3,1]，items = [1,4]。处理 item = 1：1 in inventory 为真，remove(1) 只删掉第一个 1，得到 [2,1,3,1]，然后 append 1 得 [2,1,3,1,1]。处理 4 得 [2,1,3,1,1,4]。期望是 [2,3,1,4]。崩了。

原因很具体：list.remove(x) 的文档说得清清楚楚——Remove the first occurrence。而题面说的是「Remove all existing copies of the item (0, 1, 2+)」。所以 if 得换成 while：

while item in inventory:
    inventory.remove(item)

这个 while 循环读起来像绕口令，但它是对的：每转一圈删掉一个，直到 item in inventory 为假为止。（也可以倒着遍历索引删，但代码更长更容易错。）

for i in range(len(inventory)):
    if inventory[i] == item:
        inventory.pop(i)

第二版（改成 while 之后），再拿用例 3 试，这里 items 就是 inventory 自己：

for item in items:          # items 和 inventory 是同一个列表！
    while item in inventory:
        inventory.remove(item)
    inventory.append(item)

Python 的 for x in lst 底层是「取一个索引 0、1、2…，每次问列表要那个位置的元素，越界就停」。它不会预先复制列表。所以我们在循环体里疯狂地删元素、加元素，循环自己的游标却仍在按 0、1、2… 往前爬。结果是：读到的元素跟原始的 [1,2,1,3,1] 完全对不上，什么时候停也说不准。

pickup_order = list(items)

最后是容量修剪。天真的写法会把它塞进 for 循环里，每 append 一个就检查一次。题面的 Timing 一节专门警告了不能这样：必须全部处理完再统一修剪。为什么这个区别有影响？看用例 3：inv3 = [1,2,1,3,1]，capacity = 3。如果边处理边修剪，处理第一个 item 时长度就已经超了 3，会提前删掉本该保留的元素，后面全乱。统一到最后修剪，逻辑才和题面一致。

修剪本身用 while 而不是 if，因为可能超出不止一个（用例 5 超出 2 个）。删「最老的」= 删索引 0 的 = inventory.pop(0)。

代码

def inventory_pickup(inventory: list, items: list, capacity: int) -> list:
    # items may be the same list object as inventory, and we are about to
    # mutate inventory. Snapshot the pickup order first so that the loop
    # is not affected by the mutations we make below.
    pickup_order = list(items)
    for item in pickup_order:
        # Remove every existing copy of item, then add one fresh copy
        # at the end (so it counts as the most recently picked up).
        while item in inventory:
            inventory.remove(item)
        inventory.append(item)
    # Only after all items are processed do we enforce the capacity,
    # dropping the oldest entries (at the front) first.
    while len(inventory) > capacity:
        inventory.pop(0)
    return inventory

逐行说为什么：

验证

手动追踪用例 3，它同时踩中了三个陷阱（自引用、多重复、超容量）：

>>> inv3 = [1, 2, 1, 3, 1]
>>> check_mutation = inv3
>>> inv3_test = inventory_pickup(inv3, inv3, 3)

先看谁指向谁。调用发生时，有四个名字指向同一个列表对象（记它为 L）：

全局帧 Global
    inv3 ──────────┐
    check_mutation ─┼──→ L = [1, 2, 1, 3, 1]
                    │
inventory_pickup 帧 │
    inventory ──────┤
    items ──────────┘
    capacity = 3

    pickup_order ──→ S = [1, 2, 1, 3, 1]   （独立对象，与 L 无关）

注意这里有个容易被忽略的精妙之处：如果没有第 0 步的快照，for item in items 遍历的就是 L 本身。第 1 轮读 L[0] = 1，循环体把 L 改成了 [2, 3, 1]；第 2 轮 for 去读 L[1]，那是 3，而不是原始清单里的 2。整条捡拾顺序被篡改，结果必错。

再验一下用例 5，它检验修剪要删多次：inventory = [1,2,3,4]，items = [5,6,7,8]，capacity = 6。四个 item 都不在背包里，所以 while 一次都不进，直接 append 四次，得 [1,2,3,4,5,6,7,8]，长度 8。修剪：8 > 6 → pop(0) → [2,...,8] 长 7；7 > 6 → pop(0) → [3,4,5,6,7,8] 长 6；6 > 6 假，停。输出 [3, 4, 5, 6, 7, 8]，正确。若这里写的是 if 而不是 while，只会删一次，得到长度 7 的列表，直接挂。

最后验用例 6，元素是字符串：['hello','world'] 捡 ['hi','hello']。'hi' 不在里面，直接 append → ['hello','world','hi']；'hello' 在里面，删掉 → ['world','hi']，再 append → ['world','hi','hello']。长度 3 不超 4。输出 ['world', 'hi', 'hello']。这个例子说明「删了再加」不是白折腾——它把老物品挪到了队尾，改变了后续被修剪的优先级。

2. Q2 berry_finder：树里有没有浆果

题目要什么

校园里的松鼠想知道哪棵树上有浆果。写 berry_finder(t)：如果树 t 里存在任意一个节点的标签是字符串 'berry'，返回 True，否则返回 False。

四个 doctest：

>>> scrat = tree('berry')
>>> berry_finder(scrat)
True
>>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('berry')]), tree('branch2')])
>>> berry_finder(sproul)
True
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> berry_finder(numbers)
False
>>> t = tree(1, [tree('berry',[tree('not berry')])])
>>> berry_finder(t)
True

要点在于这四个例子覆盖的边界：

• scrat 是一棵只有根、没有分支的树（叶子），而根就是 'berry'。所以「根本身是不是 berry」必须单独检查，不能只往分支里找。
• sproul 的 berry 藏在第二层的第二个分支里。说明要深入，而且要横向找完所有分支。
• numbers 全是数字，一个 berry 都没有 → 必须能返回 False，而不是掉进 None。
• 第四个例子里 berry 节点底下还有东西（'not berry'），说明命中不一定发生在叶子上；同时 'not berry' != 'berry'，比较必须是整体相等，不是子串包含。

怎么想到的

树递归题的第一个动作永远一样：问自己「如果我已经有一个能解决更小的树的函数，我怎么用它解决当前这棵树？」

对本题：假设我已经会判断「某棵子树里有没有 berry」。那么整棵树 t 里有 berry，当且仅当下面两件事至少成立一件：

1. t 自己的根标签就是 'berry'；
2. t 的某一个分支里有 berry。

这句话直接就是代码。第 1 条写成 label(t) == 'berry'；第 2 条写成「对每个分支 b 递归问一遍 berry_finder(b)，只要有一个说 True 就 True」。

还有一处需要想清楚：为什么不能写成

for b in branches(t):
    return berry_finder(b)     # 错！

这个写法在第一个分支上就 return 了，后面的分支永远看不到。对 sproul 来说，第一个分支 branch1 里确实有 berry，碰巧对；但如果 berry 在 branch2 里，就会漏掉。

正确的模式是「找到才提前返回，找不到继续」：

for b in branches(t):
    if berry_finder(b):
        return True
# 所有分支都问过了，都没有
return False

这个 if 递归调用: return True ... 循环外 return False 的骨架，是所有「存在性」搜索题的通用形状。记住它。

代码

def berry_finder(t):
    if label(t) == 'berry':
        return True
    for b in branches(t):
        if berry_finder(b):
            return True
    return False

验证

把 sproul 的调用栈真的展开一遍。这棵树是：

roots
  branch1
    leaf
    berry
  branch2

berry_finder(roots)
│ label = 'roots' ≠ 'berry'
│ branches = [branch1树, branch2树]
│ 第 1 个分支 b = branch1树 →
│ ┌ berry_finder(branch1)
│ │ label = 'branch1' ≠ 'berry'
│ │ branches = [leaf树, berry树]
│ │ 第 1 个分支 b = leaf树 →
│ │ ┌ berry_finder(leaf)
│ │ │ label = 'leaf' ≠ 'berry'
│ │ │ branches = []  → for 循环零次
│ │ └ return False
│ │ if False:  不返回，继续下一个分支
│ │ 第 2 个分支 b = berry树 →
│ │ ┌ berry_finder(berry)
│ │ │ label = 'berry' == 'berry'
│ │ └ return True            ← 命中
│ │ if True: → return True
│ └ return True
│ if True: → return True
└ return True

再看 numbers（全是数字，答案应为 False）：berry_finder(1) 的根不是 berry，依次递归 2、3、6。berry_finder(2) 是叶子 → False；berry_finder(3) 递归 4、5 都 False，自己也 False；berry_finder(6) 递归 7 得 False，自己 False。三个分支全 False，for 循环正常走完，落到最后一行 return False。这里 7 个节点全部被访问了一遍——找不到的时候必须穷举，没有捷径。

第四个用例 tree(1, [tree('berry', [tree('not berry')])])：根是 1，唯一分支的根是 'berry'，递归第一行就命中返回 True，'not berry' 那层压根不会被检查。这个用例是在防「必须递归到叶子才判断」的错误写法。

3. Q3 size_of_tree：数一数有几个节点

题目要什么

写 size_of_tree(t)，返回树 t 里节点（entry）的总数——包括根、所有中间节点、所有叶子。

>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
  2
  3
    4
    5
  6
    7
>>> size_of_tree(numbers)
7

数一下 print_tree 打出来的行数：1、2、3、4、5、6、7 一共 7 行，答案就是 7。「节点数」等于 print_tree 的输出行数，这个对应关系很好记——因为 print_tree 正是对每个节点打印一行。

虽然只给了一个 doctest，边界情况仍要想清楚：单节点树 tree(5) 的答案应该是 1，不是 0。这决定了 base case 该返回什么。

怎么想到的

和 Q2 用完全一样的套路：假设我已经会数子树的节点数，怎么数当前这棵？

一棵树的节点 = 根这一个 + 各个分支里的节点。而「各个分支里的节点」正好是 size_of_tree(b) 对每个分支 b 的和。写成公式：

这就是全部。注意和 Q2 的结构差异：

「聚合型」递归有个固定的写法：先设一个累加器（accumulator），循环里更新它，循环结束后返回它。累加器的初值就是「根自己的贡献」，这里是 1。

顺带一提，这题也可以写成一行：

return 1 + sum([size_of_tree(b) for b in branches(t)])

意思完全一样（sum([]) 是 0，叶子仍得 1）。本仓库用的是显式循环版，因为它更直白地展示了「累加器」这个模式，而且当你以后要在循环里做更复杂的事时不用重写。

代码

def size_of_tree(t):
    # The root counts as one entry; add the sizes of all the branches.
    total = 1
    for b in branches(t):
        total += size_of_tree(b)
    return total

验证

展开 numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])：

size_of_tree(1)                       total = 1
├─ size_of_tree(2)                    total = 1, branches=[] → return 1
│                                     外层 total = 1 + 1 = 2
├─ size_of_tree(3)                    total = 1
│  ├─ size_of_tree(4) → return 1      total = 2
│  └─ size_of_tree(5) → return 1      total = 3
│                            return 3
│                                     外层 total = 2 + 3 = 5
└─ size_of_tree(6)                    total = 1
   └─ size_of_tree(7) → return 1      total = 2
                                return 2
                                      外层 total = 5 + 2 = 7
                                      return 7

size(1) = 1 + size(2) + size(3) + size(6)
        = 1 +    1    + size(3) + size(6)
size(3) = 1 + size(4) + size(5) = 1 + 1 + 1 = 3
size(6) = 1 + size(7)           = 1 + 1     = 2
size(1) = 1 + 1 + 3 + 2 = 7  ✓

递归调用的总次数正好等于节点数 7——每个节点被访问且仅被访问一次。这也说明这个算法是 $\Theta(n)$ 的，$n$ 为节点数，不可能更快，因为你必须看过每个节点才能数清楚。

4. Q4 make_path：往树里"补"出一条路径

这是 HW 3 里最难的一题。前两题只是读树，这题要造一棵新树，而且要求「加的节点尽可能少」。

题目要什么

先把题面那段绕口的定义翻译成人话。

什么是路径（path）：题面开头说 A path is a sequence of trees in which each is the parent of the next. 也就是从某个节点出发，一路往下走（每步走到自己的某个分支），走过的节点标签依次排列，就是一条路径的标签序列。has_path(t, p) 的意思是「从 t 的根出发，能不能沿着 p 里的标签一步步走下去」。

要求：make_path(t, p) 返回一棵新树 u，满足：

1. u 里有一条标签为 p 的路径（从根开始）；
2. t 原有的每一条路径在 u 里都还在（也就是不能删东西）；
3. 在满足前两条的前提下，u 的节点数最少。

加上两条格式约定：新加的节点要放在其父节点分支列表的最后；t 的标签保证互不相同（unique）。还有一条 assert p[0] == label(t)，保证路径的第一个标签就是根标签，否则根本无从谈起。

「节点数最少」这条是整题的关键。它的实际含义是：能复用现成的分支就复用，实在没有才新建。看第三个 doctest 就明白了：

>>> t2 = tree(5, [tree(6), tree(7)])
>>> t1 = tree(3, [tree(4), t2])
>>> print_tree(make_path(t1, [3, 4, 8, 9]))
3
  4
    8
      9
  5
    6
    7

原树 t1 是：根 3，分支 4（叶子）和 5（下挂 6、7）。要补的路径是 3 → 4 → 8 → 9。根 3 有了；4 这个分支已经存在，所以不新建，直接在它下面继续补 8 → 9。最后加了两个节点（8 和 9）。如果不复用而是新建一个 4，就要加三个节点，不是最少。

四个 doctest 分别测什么：

用例 4 最能说明「新节点放最后」这条规则：

>>> print_tree(make_path(tree(2, [tree(1), t1]), [2, 3, 5, 6, 8]))
2
  1
  3
    4
    5
      6
        8
      7

注意 5 下面的顺序是 6（下挂新加的 8）然后 7——6 还在原来的位置上，没被挪到末尾。「放最后」只针对新造出来的节点；被复用的原有分支要留在原位。这一条极容易写错。

怎么想到的

题面给了骨架（skeleton），填空即可，但为了真正理解，先假装没有骨架，自己推一遍。

第一步：确定递归的"变小"方向。 树递归的参数变小方式是「从 t 降到某个 b in branches(t)」。而 p 是一个列表，它变小的方式是切片 p[1:]。这两个必须同步变小：既然 p[0] 已经被 assert 确认等于 label(t)，那么剩下要处理的就是「在某个分支里补出 p[1:] 这条路径」。所以递归调用长这样：

make_path(某个分支, p[1:])

而根据 assert 的要求，这个「某个分支」的标签必须等于 p[1:][0]，也就是 p[1]。这一条约束直接决定了整题的结构：我们只能对标签等于 p[1] 的那个分支递归。

第二步：base case。 什么时候不用再递归？当 len(p) == 1 时。因为 assert 已经保证 p[0] == label(t)，len(p) == 1 就意味着 p == [label(t)]——这条「路径」只有根一个节点，而 t 的根本来就在那儿，什么都不用加。所以 return t。题面的 Hint 里也是这么说的：if p has length 1 then t contains a path with labels p, so you can just return t。

第三步：递归情形。 现在 len(p) >= 2。我们要为返回的树重新组装一个分支列表 new_branches。遍历原有的每个分支 b：

• 如果 label(b) == p[1]：这就是那个能被复用并延长的分支。把它换成 make_path(b, p[1:])——递归会在 b 内部继续补路径，同时保留 b 原有的一切。
• 否则：这个分支和要补的路径无关，原样保留，new_branches.append(b)。

遍历完，可能一个匹配的分支都没找到。这时就得凭空造一条新分支出来，挂在最后。新分支的根标签必须是 p[1]，它底下还要继续有 p[2], p[3], ...。骨架给的写法是 make_path(____, ____)，填进去就是：

make_path(tree(p[1]), p[1:])

读作：「先造一个只有根 p[1] 的光杆树，然后让 make_path 自己去把 p[1:] 这条路径补进这棵光杆树里」。这一步很妙——不用写循环去手工串起 p[1] → p[2] → ... ，直接把活儿交给递归。传进去的树的根是 p[1]，路径的头也是 p[1]，assert 自然满足。

第四步：把结果包起来。 return tree(label(t), new_branches)。根标签不变（它就是 p[0]），分支换成新组装的列表。

代码

def make_path(t, p):
    assert p[0] == label(t), 'It is not possible to make this path'
    if len(p) == 1:
        # p is just [label(t)], so t already contains the path.
        return t
    new_branches = []
    found_p1 = False
    for b in branches(t):
        if label(b) == p[1]:
            # Extend this existing branch instead of creating a new one.
            found_p1 = True
            new_branches.append(make_path(b, p[1:]))
        else:
            new_branches.append(b)
    if not found_p1:
        # No branch to extend, so build a brand new one at the end.
        new_branches.append(make_path(tree(p[1]), p[1:]))
    return tree(label(t), new_branches)

验证

把最复杂的用例 4 完整展开。原树是 tree(2, [tree(1), t1])，其中 t1 = tree(3, [tree(4), t2])，t2 = tree(5, [tree(6), tree(7)])。画出来：

2
  1
  3
    4
    5
      6
      7

要补的路径 p = [2, 3, 5, 6, 8]。

第 5 层 → tree(8)

第 4 层：new_branches = [tree(8)]
        返回 tree(6, [tree(8)])         即   6
                                              8

第 3 层：new_branches = [tree(6,[tree(8)]), 节点7]
        返回 tree(5, [tree(6,[tree(8)]), tree(7)])
             即   5
                    6
                      8
                    7

第 2 层：new_branches = [节点4, 上面那棵5]
        返回 tree(3, [tree(4), 上面那棵5])
             即   3
                    4
                    5
                      6
                        8
                      7

第 1 层：new_branches = [节点1, 上面那棵3]
        返回 tree(2, [tree(1), 上面那棵3])

2
  1
  3
    4
    5
      6
        8
      7

特别看第 3 层：新节点 8 是挂在 6 下面的，而 6 本身在 5 的分支列表里还是第一位，7 还在第二位。这就是「被复用的分支保持原位、只有新建的分支才追加到末尾」的直接体现。如果错误地写成「先 append 所有不匹配的，再 append 匹配后的递归结果」，输出会变成 7 在前 6 在后，doctest 挂掉。

再快速验用例 1：make_path(t1, [3, 5, 7])。第 1 层 p[1]=5，分支 4 不匹配保留，分支 5 匹配 → 递归 make_path(节点5, [5,7])。第 2 层 p[1]=7，分支 6 不匹配保留，分支 7 匹配 → 递归 make_path(节点7, [7])。第 3 层 len(p)==1 → 返回 节点7 原物。回代：tree(5, [节点6, 节点7])、tree(3, [节点4, 那棵5])。结构和标签与 t1 一模一样，所以 == t1 为 True（列表的 == 是逐元素递归比较值，不要求是同一个对象）。一个节点都没加，符合「最少」。

再验用例 2：make_path(t1, [3, 8, 9, 1])。第 1 层 p[1]=8，分支 4 和 5 都不匹配，全部原样保留，found_p1 保持 False。于是走 if not found_p1，append make_path(tree(8), [8,9,1])。这一支里 tree(8) 没有分支，又是 found_p1 = False，继续 make_path(tree(9), [9,1])，再 make_path(tree(1), [1]) → base case 返回 tree(1)。回代得 tree(9,[tree(1)])、tree(8,[tree(9,[tree(1)])])。最终 tree(3, [tree(4), t2, 那棵8])，打印为：

3
  4
  5
    6
    7
  8
    9
      1

新造的 8 果然在最后。

5. Q5 merge：归并两个（可能无限的）有序序列

题目要什么

merge(incr_a, incr_b) 接收两个严格递增的可迭代对象，按从小到大的顺序 yield 它们的元素，去掉重复。

题面给的假设要一条条读清楚，它们决定了算法能有多简单：

两个 doctest：

>>> m = merge([0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15])
>>> type(m)
<class 'generator'>
>>> list(m)
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
>>> def big(n):
...    k = 0
...    while True: yield k; k += n
>>> m = merge(big(2), big(3))
>>> [next(m) for _ in range(11)]
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]

type(m) 是 <class 'generator'>——这行 doctest 在强制你必须用 yield 写，返回一个列表是过不了的。

第二个例子里 big(2) 是 0,2,4,6,... 无限，big(3) 是 0,3,6,9,... 无限。取前 11 个，结果和第一个例子一模一样。这个设计很巧：同样的答案，一次来自有限列表，一次来自无限流，说明你的代码必须既能处理耗尽、又能处理永不耗尽。

怎么想到的

先想「如果两个都是有限列表，我会怎么合并」。答案是归并排序里的经典 merge：两根手指分别指着两个列表的当前位置，比一比谁小就输出谁、那根手指前进一格；相等就输出一次、两根手指都前进（这就是去重）。某一边走完了，把另一边剩下的全倒出来。

难点在于「手指」怎么表示。 如果是列表，用下标 i、j 就行。但题目说可能无限——无限序列没有下标可言，也不能 len。这时唯一的接口是迭代器协议：iter() 拿到迭代器，next() 一次要一个。

骨架前两行已经替你写好了：

iter_a, iter_b = iter(incr_a), iter(incr_b)
next_a, next_b = next(iter_a, None), next(iter_b, None)

读懂这两行，这题就解决一半了。

核心循环。 只要两边都还有货（next_a is not None and next_b is not None），就三选一：

收尾。 循环退出说明至少有一边空了。这时另一边可能还有剩余（有限情形），要全部倒出来。写成两个 while：

while next_a is not None:
    yield next_a
    next_a = next(iter_a, None)
while next_b is not None:
    yield next_b
    next_b = next(iter_b, None)

这两个循环最多只有一个会真正执行（另一个的哨兵已经是 None），所以不用写 if/else 去判断是哪边空了——空的那个 while 条件直接为假，零次迭代。这是个很省事的写法。

代码

def merge(incr_a, incr_b):
    iter_a, iter_b = iter(incr_a), iter(incr_b)
    next_a, next_b = next(iter_a, None), next(iter_b, None)
    while next_a is not None and next_b is not None:
        if next_a == next_b:
            # Same value in both: yield it once and advance both iterators.
            yield next_a
            next_a, next_b = next(iter_a, None), next(iter_b, None)
        elif next_a < next_b:
            yield next_a
            next_a = next(iter_a, None)
        else:
            yield next_b
            next_b = next(iter_b, None)
    # One iterator is exhausted; yield whatever is left of the other.
    while next_a is not None:
        yield next_a
        next_a = next(iter_a, None)
    while next_b is not None:
        yield next_b
        next_b = next(iter_b, None)

验证

追踪第一个 doctest：merge([0,2,4,6,8,10,12,14], [0,3,6,9,12,15])，然后 list(m)。

轮  next_a  next_b   比较        yield   之后 next_a  next_b
 1     0       0    相等          0          2         3
 2     2       3    a<b           2          4         3
 3     4       3    b<a           3          4         6
 4     4       6    a<b           4          6         6
 5     6       6    相等          6          8         9
 6     8       9    a<b           8         10         9
 7    10       9    b<a           9         10        12
 8    10      12    a<b          10         12        12
 9    12      12    相等         12         14        15
10    14      15    a<b          14        None       15
                                         ↑ a 耗尽

数一下：a 有 8 个元素，b 有 6 个，共 14 个，输出 11 个。差的 3 个正是两边共有的 0、6、12 各被合并掉一次。

再看无限版 merge(big(2), big(3))。big(2) 产生 0,2,4,6,8,10,12,14,16,...；big(3) 产生 0,3,6,9,12,15,18,...。前 11 个的推演和上表逐行相同，因为前 14 个元素完全一样。区别只在第 10 轮之后：这里 next_a 不是 None 而是 16，主循环继续跑第 11 轮（16 vs 15 → yield 15）。但 [next(m) for _ in range(11)] 只要 11 个，拿到 15 之后就不再问了，merge 停在那个 yield 上永久冻结。输出同样是 [0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]。

6. Q6 yield_paths：递归的生成器

这题把树递归和生成器捏在一起，是 HW 3 的收官题，也是最能体现「生成器为什么好用」的一题。

题目要什么

yield_paths(t, target)：yield 出每一条从 t 的根到某个标签为 target 的节点的路径。每条路径表示成一个标签列表，从根标签开始，到 target 结束。顺序任意（doctest 里用 sorted 消除顺序影响）。

>>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
>>> print_tree(t1)
1
  2
    3
    4
      6
    5
  5
>>> next(yield_paths(t1, 6))
[1, 2, 4, 6]
>>> path_to_5 = yield_paths(t1, 5)
>>> sorted(list(path_to_5))
[[1, 2, 5], [1, 5]]

关键观察：

• 可能有多条路径。t1 里有两个标签为 5 的节点（一个在 2 底下，一个是根的直接分支），所以有两条路径。这题和 Q4 不同，标签不保证 unique。
• 命中之后还要继续往下找。看第二个树：

>>> t2 = tree(0, [tree(2, [t1])])
>>> path_to_2 = yield_paths(t2, 2)
>>> sorted(list(path_to_2))
[[0, 2], [0, 2, 1, 2]]

t2 是 0 → 2 → 1 → (2 → ...)。找 target = 2，有两条答案：[0, 2]（那个直接分支）和 [0, 2, 1, 2]（更深处的那个 2）。第一个 2 被命中之后，不能停下来，还得继续搜它的子树——这一点让代码不能写成「命中就 return」的形状。

• next(yield_paths(t1, 6)) 只取第一条，说明返回的必须是生成器（能被 next），而且是惰性的：只要一条时不该把整棵树搜完。

题面给的骨架已经框死了结构：

if label(t) == target:
    yield ____
for b in branches(t):
    for ____ in ____:
        yield ____

怎么想到的

题面 Hint 说得对：先假装它不是生成器函数，想清楚递归怎么写。

问：从 t 的根到 target 的所有路径长什么样？分两类。

1. 根自己就是 target：那么 [label(t)] 就是一条（长度为 1 的）路径。
2. target 在某个分支 b 里面：设 P 是「从 b 的根到 target 的某条路径」。那么在 b 前面接上 t 的根，[label(t)] + P 就是一条从 t 到 target 的路径。

而「从 b 的根到 target 的所有路径」，正是 yield_paths(b, target) 的定义。递归结构就出来了。

result = []
if label(t) == target:
    result.append([label(t)])
for b in branches(t):
    for path in yield_paths_list(b, target):
        result.append([label(t)] + path)
return result

if label(t) == target:
    yield [label(t)]
for b in branches(t):
    for path in yield_paths(b, target):
        yield [label(t)] + path

为什么内层是 for 而不是别的？ 因为 yield_paths(b, target) 返回的是一个生成器对象，不是列表。生成器是迭代器，迭代器是可迭代的，所以可以直接 for path in 它。每转一圈，内层生成器就往前跑到它的下一个 yield，把一条路径交给我们；我们在前面拼上 label(t)，再 yield 出去。一条一条地转发，而不是先收集完。 这正是 next(yield_paths(t1, 6)) 能只搜一部分就返回的原因。

为什么是 [label(t)] + path 而不是 path.append(label(t))？ 两个理由：一是位置——根标签要放在最前面，append 是放最后；二是可变性——path 是下层生成器交上来的列表对象，就地改它会污染下层（虽然本题下层每次都新建列表，但依赖这一点很危险）。[label(t)] + path 创建一个新列表，干净。这也解释了为什么这个算法在深度为 $d$ 的树上每条路径要 $\Theta(d^2)$ 的拼接开销——每层都复制一次。对本题的规模无所谓。

base case 在哪？ 又是隐含的。叶子节点的 branches(t) 是空的，for 循环零次；如果它的标签也不是 target，函数体直接跑完 → 这个生成器不产出任何值就 StopIteration。「产出零条路径」是完全合法的结果。

代码

def yield_paths(t, target):
    if label(t) == target:
        yield [label(t)]
    for b in branches(t):
        # Every path from b to target becomes a path from t once we
        # put label(t) at the front.
        for path in yield_paths(b, target):
            yield [label(t)] + path

验证

追踪 sorted(list(yield_paths(t2, 2)))。t2 的结构：

0
  2
    1
      2
        3
        4
          6
        5
      5

yield_paths(节点0, 2)
│ label=0 ≠ 2 → 不 yield
│ 分支：[节点2]
│ ┌ yield_paths(节点2, 2)
│ │ label=2 == 2 → ★ yield [2]
│ │ 分支：[节点1]
│ │ ┌ yield_paths(节点1, 2)
│ │ │ label=1 ≠ 2
│ │ │ 分支：[节点2', 节点5]        （节点2' 是 t1 里的那个 2）
│ │ │ ┌ yield_paths(节点2', 2)
│ │ │ │ label=2 == 2 → ★ yield [2]
│ │ │ │ 分支：[节点3, 节点4, 节点5]
│ │ │ │   yield_paths(节点3,2): 3≠2, 无分支 → 零条
│ │ │ │   yield_paths(节点4,2): 4≠2 → 递归 节点6: 6≠2 无分支 → 零条 → 零条
│ │ │ │   yield_paths(节点5,2): 5≠2, 无分支 → 零条
│ │ │ └ 总产出：[2]
│ │ │ 转发：yield [1] + [2] = ★ [1, 2]
│ │ │ ┌ yield_paths(节点5, 2): 5≠2, 无分支 → 零条
│ │ └ 总产出：[1, 2]
│ │ 转发：yield [2] + [1,2] = ★ [2, 1, 2]
│ └ 总产出：[2]、[2, 1, 2]
│ 转发：yield [0] + [2]       = ★ [0, 2]
│      yield [0] + [2,1,2]    = ★ [0, 2, 1, 2]
└ 总产出：[0, 2]、[0, 2, 1, 2]

注意 yield_paths(节点2, 2) 那一层：它先 yield 了 [2]，然后继续进入 for 循环搜 节点1，从而挖出了第二条。如果写成 if ...: return [label(t)]，深处那个 2 就永远找不到，结果只有 [[0, 2]]。

再验 next(yield_paths(t1, 6))，重点看惰性：

最后验 sorted(list(yield_paths(t1, 5)))。t1 里两个 5：一个在 2 的第三个分支，一个是根的第二个分支。产出顺序是先深后浅（因为 2 这个分支排在前面）：先得 [1, 2, 5]，再得 [1, 5]。list 收集为 [[1,2,5], [1,5]]，sorted 之后：比较 [1,2,5] 和 [1,5]，首元素都是 1，第二元素 2 < 5，所以 [1,2,5] 在前。结果 [[1, 2, 5], [1, 5]]，与 doctest 一致。doctest 特意用 sorted 就是因为题面说了「顺序任意」。

7. Q7 midsem_survey：本仓库无法通过的那一题

这题不考编程。题面要求：填写课程的 Mid-Semester Feedback 问卷，提交后页面会显示一串口令（passphrase），把它填进 hw03.py 里：

passphrase = 'REPLACE_THIS_WITH_PASSPHRASE'

ok 的检查方式是对你填的字符串做 SHA-224 哈希，和一个写死在 docstring 里的目标值比对：

def midsem_survey(p):
    """
    You do not need to understand this code.
    >>> midsem_survey(passphrase)
    '2bf925d47c03503d3ebe5a6fc12d479b8d12f14c0494b43deba963a0'
    """
    import hashlib
    return hashlib.sha224(p.encode('utf-8')).hexdigest()

本仓库跑 python3 ok --local -q midsem_survey 的实际输出：

>>> midsem_survey(passphrase)
'f65fb8fdaeda6d85eb3089dcdf7784836dde30e260c0ad31b9b2e533'

# Error: expected
#     '2bf925d47c03503d3ebe5a6fc12d479b8d12f14c0494b43deba963a0'
# but got
#     'f65fb8fdaeda6d85eb3089dcdf7784836dde30e260c0ad31b9b2e533'
Score: 0.0/1

f65fb8... 正是占位字符串 'REPLACE_THIS_WITH_PASSPHRASE' 的 SHA-224。

整份作业回顾

HW 3 表面上是三个互不相干的话题，实际上它在教你三种不同的「函数与世界的关系」：

真正值得带走的几件事

题目速查

自己再练一遍

下面几道是基于本次手法的变式，答案折叠在里面。建议先自己写再看。

def height(t):
    if is_leaf(t):
        return 0
    return 1 + max([height(b) for b in branches(t)])

索引 0：读 L[0] = 11 → remove(11) 得 [12,13] → append(11) 得 [12,13,11]
索引 1：读 L[1] = 13 → remove(13) 得 [12,11] → append(13) 得 [12,11,13]
索引 2：读 L[2] = 13 → remove(13) 得 [12,11] → append(13) 得 [12,11,13]
索引 3：越界，for 结束