Skip to main content

CS 61A 2024春季学期 Homework 5

Homework 5: 生成器​

截止日期：3月7日，星期四，晚上11:59

操作指南​

下载 hw05.zip。在压缩包中，您会找到一个名为 hw05.py 的文件，以及 ok 自动评分器的副本。

提交方式： 完成作业后，请将您编辑的所有代码文件上传到 Gradescope 以提交作业。您可以在截止日期前多次提交；只有最终提交会被评分。请检查您是否已在 Gradescope 上成功提交您的代码。有关提交作业的更多说明，请参阅 Lab 0。

使用 Ok： 如果您对使用 Ok 有任何疑问，请参阅 此指南。

阅读材料： 您可能会发现以下参考资料很有用：

评分： 作业根据正确率评分。每个不正确的问题将使总分减少一分。此家庭作业满分为 2 分。

必答题​

新手入门视频​

这些视频可能会为解决此作业中的编码问题提供一些有用的指导。

要观看这些视频，您应该登录您的 berkeley.edu 电子邮件。

YouTube 链接

Q1: 无穷冰雹序列​

编写一个生成器函数，该函数产生以数字 n 开头的冰雹序列的元素。到达冰雹序列的末尾后，生成器应无限期地产生值 1。

以下是冰雹序列的定义：

  1. 选择一个正整数 n 作为开始。
  2. 如果 n 是偶数，则将其除以 2。
  3. 如果 n 是奇数，则将其乘以 3 并加 1。
  4. 继续此过程，直到 n 为 1。

尝试以递归方式编写此生成器函数。如果遇到困难，可以先尝试用迭代法编写，再考虑如何将其转化为递归实现。

提示： 因为 hailstone 返回一个生成器，所以你可以使用 yield from 语句来简化代码，直接从 hailstone 生成器中产生值！

def hailstone(n):
    """Q1: Yields the elements of the hailstone sequence starting at n.
       At the end of the sequence, yield 1 infinitely.

    >>> hail_gen = hailstone(10)
    >>> [next(hail_gen) for _ in range(10)]
    [10, 5, 16, 8, 4, 2, 1, 1, 1, 1]
    >>> next(hail_gen)
    1
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试您的代码：

python3 ok -q hailstone

Q2: 合并生成器​

编写一个生成器函数 merge，它接受两个无限生成器 a 和 b，它们按递增顺序排列且没有重复项，并返回一个生成器，该生成器具有两个生成器的所有元素，按递增顺序排列，且没有重复项。

def merge(a, b):
    """Q2:
    >>> def sequence(start, step):
    ...     while True:
    ...         yield start
    ...         start += step
    >>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
    >>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
    >>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
    >>> [next(result) for _ in range(10)]
    [2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
    """
    "*** YOUR CODE HERE ***"

使用 Ok 测试您的代码：

python3 ok -q merge

Q3: yield_paths：生成树的路径​

定义一个生成器函数 yield_paths(t, value)，该函数接收一棵树 t 和一个值 value，并生成从树根到所有标签为 value 的节点的路径。

每条路径应该是一个列表，包含从树根到目标节点路径上的所有标签。生成路径的顺序没有要求。

def yield_paths(t, value):
    """Q4: Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> 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]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == value:
        yield ____
    for b in branches(t):
        for ____ in ____:
            yield ____

提示：如果你不知道该如何开始，想想如果这不是一个生成器函数，你会如何解决这个问题。你会如何进行递归调用？对于生成器函数，如果在函数体内进行“递归调用”，会发生什么？

提示：尝试自己想出几个简单的例子！当 t 是一个叶节点时，这个函数应该如何工作？

提示：记住，可以循环遍历生成器对象，因为生成器是迭代器！

注意：记住这个问题应该产生路径——不要返回路径列表！

使用 Ok 测试你的代码：

python3 ok -q yield_paths

在本地检查你的分数​

你可以通过运行以下命令在本地检查此作业中每个问题的分数

python3 ok --score

这不会提交作业！ 当你对分数满意时，请将你编辑过的文件上传到 Gradescope 上对应的作业以提交作业。 Lab 00 包含详细说明。

考试练习​

本次作业还包含了一些往年考试题，供你练习。这些问题没有提交部分；欢迎尝试这些题目，作为练习！

  1. 2018 年夏季期末考试 Q7a,b：流和生成器
  2. 2019 年春季期末考试 Q1：迭代器是不可避免的
  3. 2021 年春季 MT2 Q8：L-I-F-E 之树
  4. 2016 年夏季期末考试 Q8：Zhen-erators 产生力量
  5. 2018 年春季期末考试 Q4a：运用你自己