Homework 5: Generators

约 2204 字大约 7 分钟

CS61ABerkeleyPython

2024-12-08

Instructions

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

如果官方链接失效，你也可以通过我的 github 仓库 CS61A_Fall2024来获取我的代码。

重要

请注意，该代码包含答案，因此如果你想独立完成请务必提前将 hw05.py 中的答案删除！

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

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

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

第 4.2 节评分：作业根据正确性进行评分。每个错误的问题都会使总分减少一分。这项作业满分为 2 分。

Required Questions

Q1: Infinite Hailstone

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

以下是冰雹序列定义方法的快速回顾：

选择一个正整数 n 作为起始值。
如果 n 为偶数，则将其除以 2。
如果 n 为奇数，则将其乘以 3 并加 1。
继续此过程，直到 n 为 1。尝试以递归方式编写此生成器函数。如果您遇到困难，可以先尝试以迭代方式编写它，然后看看如何将该实现转换为递归实现。

提示

提示：由于 hailstone 返回生成器，因此您可以对 hailstone 调用 yield from 生成结果！

def hailstone(n):
    """
    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 来测试你的代码：

python ok -q hailstone

点击查看答案

def hailstone(n):
    """
    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 ***"
    yield n 
    while n == 1:
        yield 1
    if n % 2 == 0:
        yield from hailstone(n // 2)
    else:
        yield from hailstone(n * 3 + 1)

Q2: Merge

定义：无限迭代器是在调用 next 时永远不会停止提供值的迭代器。例如， ones() 计算为无限迭代器：

def ones():
    while True:
        yield 1

编写一个生成器函数 merge(a, b) ，以两个无限迭代器 a 和 b 作为输入。两个迭代器都严格按递增顺序生成元素，且不重复。生成器应按递增顺序从两个输入迭代器生成所有唯一元素，确保不重复。

提示

注意：输入迭代器本身不包含重复项，但它们之间可能有共同的元素。

def merge(a, b):
    """
    Return a generator that has all of the elements of generators a and b,
    in increasing order, without duplicates.

    >>> 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]
    """
    a_val, b_val = next(a), next(b)
    while True:
        if a_val == b_val:
            "*** YOUR CODE HERE ***"
        elif a_val < b_val:
            "*** YOUR CODE HERE ***"
        else:
            "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python ok -q merge

点击查看答案

def merge(a, b):
    """
    Return a generator that has all of the elements of generators a and b,
    in increasing order, without duplicates.

    >>> 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]
    """
    a_val, b_val = next(a), next(b)
    while True:
        if a_val == b_val:
            "*** YOUR CODE HERE ***"
            yield a_val 
            a_val = next(a)
            b_val = next(b)
        elif a_val < b_val:
            "*** YOUR CODE HERE ***"
            yield a_val 
            a_val = next(a)
        else:
            "*** YOUR CODE HERE ***"
            yield b_val 
            b_val = next(b)

Q3: Stair Ways

假设您要爬上一个有 n 个台阶的楼梯，其中 n 是正整数。每次移动时，您可以走一步或两步。

编写一个生成器函数 stair_ways ，生成爬楼梯的所有不同方式。

爬楼梯的每种“方式”都可以用 1 和 2 的列表表示，其中每个数字表示您是一次走一步还是两步。

例如，对于有 3 个台阶的楼梯，有三种爬楼梯方式：

您每次可以走一步：[1, 1, 1]。
您可以走两步然后走一步：[2, 1]。
您可以走一步然后走两步：[1, 2]。

因此， stair_ways(3) 应该生成 [1, 1, 1]、[2, 1] 和 [1, 2] 。这些可以按任何顺序生成。

def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python ok -q stair_ways

点击查看答案

def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    "*** YOUR CODE HERE ***"
    if n == 0:
        yield []
    if n >= 1:
        for way in stair_ways(n - 1):
            yield [1] + way 
    if n >= 2:
        for way in stair_ways(n - 2):
            yield [2] + way

Q4: Yield Paths

编写一个生成器函数 yield_paths ，该函数接受树 t 和 value 。它生成从 t 的根到具有标签 value 的任何节点的每条路径。

每条路径都应作为从根到匹配节点的标签列表返回。路径可以按任何顺序生成。

提示

如果您在开始时遇到困难，请考虑如果不是生成器函数，您将如何处理这个问题。递归步骤会是什么样子？

提示

请记住，您可以迭代生成器对象，因为它们是一种迭代器！

def yield_paths(t, value):
    """
    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 ____

使用 Ok 来测试你的代码：

python ok -q yield_paths

点击查看答案

def yield_paths(t, value):
    """
    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]]
    """
    t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    if label(t) == value:
        yield [value]
    for b in branches(t):
        for path in yield_paths(b, value):
            yield [label(t)] + path

Check Your Score Locally

您可以通过运行来在本地检查此作业的每个问题的分数：

python ok --score

我的得分：

PS D:\Github\CS61A_Fall2024\hw\hw05> python ok --score 
=====================================================================
Assignment: Homework 5
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Scoring tests

---------------------------------------------------------------------
Doctests for hailstone

>>> from hw05 import *
>>> 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
Score: 1.0/1

---------------------------------------------------------------------
Doctests for merge

>>> from hw05 import *
>>> 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]
Score: 1.0/1

---------------------------------------------------------------------
Doctests for stair_ways

>>> from hw05 import *
>>> list(stair_ways(0))
[[]]
>>> s_w = stair_ways(4)
>>> sorted([next(s_w) for _ in range(5)])
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
>>> list(s_w) # Ensure you're not yielding extra
[]
Score: 1.0/1

---------------------------------------------------------------------
Doctests for yield_paths

>>> from hw05 import *
>>> 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]]
Score: 1.0/1

---------------------------------------------------------------------
Point breakdown
    hailstone: 1.0/1
    merge: 1.0/1
    stair_ways: 1.0/1
    yield_paths: 1.0/1

Score:
    Total: 4.0

Backup... 100% complete
Backup past deadline by 51 days, 1 hour, 7 minutes, and 21 seconds
Backup successful for user: zhiyong947@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/hw05/backups/62oVKQ

OK is up to date

这不会提交作业！当您对分数满意时，请将作业提交给 Gradescope 以获得学分。