AJohn Blog

外观

Homework 4: Sequences, Data Abstraction, Trees

约 3571 字大约 12 分钟

CS61ABerkeleyPython

2024-11-28

Instructions

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

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

重要

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

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

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

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

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

Required Questions

Sequences

Q1: Shuffle

实现 shuffle ，它接受一个具有偶数个元素的序列 s （例如列表或范围）。它返回一个新列表，该列表将 s 的前半部分元素与后半部分元素交错。它不会修改 s 。

交错两个序列 s0 和 s1 就是创建一个新列表，其中包含 s0 的第一个元素、 s1 的第一个元素、 s0 的第二个元素、 s1 的第二个元素，依此类推。例如，如果 s0 = [1, 2, 3] 和 s1 = [4, 5, 6] ，则交错 s0 和 s1 将得到 [1, 4, 2, 5, 3, 6] 。

def shuffle(s):
    """Return a shuffled list that interleaves the two halves of s.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    >>> shuffle(letters)
    ['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
    >>> shuffle(shuffle(letters))
    ['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
    >>> letters  # Original list should not be modified
    ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    """
    assert len(s) % 2 == 0, 'len(seq) must be even'
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q shuffle
点击查看答案
def shuffle(s):
    """Return a shuffled list that interleaves the two halves of s.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    >>> shuffle(letters)
    ['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
    >>> shuffle(shuffle(letters))
    ['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
    >>> letters  # Original list should not be modified
    ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    """
    assert len(s) % 2 == 0, 'len(seq) must be even'
    "*** YOUR CODE HERE ***"
    res = []
    mid = len(s) // 2
    left_half = s[:mid]
    right_half = s[mid:]
    for i in range(mid):
        res.append(left_half[i])
        res.append(right_half[i])
    return res

Q2: Deep Map

**定义：**嵌套数字列表是包含数字和列表的列表。它可能只包含数字，只包含列表，或者两者兼而有之。列表也必须是嵌套的数字列表。例如：[1, [2, [3]], 4] , [1, 2, 3] 和 [[1, 2], [3, 4]] 都是嵌套的数字列表。

编写一个函数 deep_map ，它接受两个参数：一个嵌套的数字列表 s 和一个单参数函数 f 。它通过将 f 应用于 s 中的每个数字并用对该数字调用 f 的结果替换该数字来修改 s 。

deep_map 返回 None 并且不应创建任何新列表。

提示

提示：如果 a 是列表，则 type(a) == list 将计算为 True 。

def deep_map(f, s):
    """Replace all non-list elements x with f(x) in the nested list s.

    >>> six = [1, 2, [3, [4], 5], 6]
    >>> deep_map(lambda x: x * x, six)
    >>> six
    [1, 4, [9, [16], 25], 36]
    >>> # Check that you're not making new lists
    >>> s = [3, [1, [4, [1]]]]
    >>> s1 = s[1]
    >>> s2 = s1[1]
    >>> s3 = s2[1]
    >>> deep_map(lambda x: x + 1, s)
    >>> s
    [4, [2, [5, [2]]]]
    >>> s1 is s[1]
    True
    >>> s2 is s1[1]
    True
    >>> s3 is s2[1]
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q deep_map
点击查看答案
def deep_map(f, s):
    """Replace all non-list elements x with f(x) in the nested list s.

    >>> six = [1, 2, [3, [4], 5], 6]
    >>> deep_map(lambda x: x * x, six)
    >>> six
    [1, 4, [9, [16], 25], 36]
    >>> # Check that you're not making new lists
    >>> s = [3, [1, [4, [1]]]]
    >>> s1 = s[1]
    >>> s2 = s1[1]
    >>> s3 = s2[1]
    >>> deep_map(lambda x: x + 1, s)
    >>> s
    [4, [2, [5, [2]]]]
    >>> s1 is s[1]
    True
    >>> s2 is s1[1]
    True
    >>> s3 is s2[1]
    True
    """
    "*** YOUR CODE HERE ***"
    for i, x in enumerate(s):
        if type(x) == list:
            deep_map(f, s[i])
        else:
            s[i] = f(x)

Data Abstraction

移动设备 本问题基于《计算机程序结构与解释》第 2.2.2 节中的一题。

我们正在制作一个天文馆移动装置。移动装置是一种悬挂雕塑。双星移动装置由两个臂组成。每个臂都是一根一定长度的杆，上面悬挂着一个行星或另一个移动装置。例如，下图显示了移动装置 A 的左臂和右臂，以及每个臂末端悬挂的东西。

我们将使用下面的数据抽象来表示二进制移动装置。

  • mobile 必须有左臂和右臂。
  • arm 的长度为正数，并且必须在末端悬挂某物，可以是移动装置或行星。
  • planet 的质量为正数，并且没有悬挂任何物体。 以下是 mobile 和 arm 数据抽象的各种构造函数和选择器。它们已经为您实现了，但这里没有显示代码。与任何数据抽象一样，您应该关注函数的作用，而不是其具体实现。您可以在移动装置编码练习中自由使用它们的任何构造函数和选择器函数。

移动数据抽象（供您参考，这里无需执行任何操作）：

def mobile(left, right):
    """
    Construct a mobile from a left arm and a right arm.

    Arguments:
        left: An arm representing the left arm of the mobile.
        right: An arm representing the right arm of the mobile.

    Returns:
        A mobile constructed from the left and right arms.
    """
    pass

def is_mobile(m):
    """
    Return whether m is a mobile.

    Arguments:
        m: An object to be checked.

    Returns:
        True if m is a mobile, False otherwise.
    """
    pass

def left(m):
    """
    Select the left arm of a mobile.

    Arguments:
        m: A mobile.

    Returns:
        The left arm of the mobile.
    """
    pass

def right(m):
    """
    Select the right arm of a mobile.

    Arguments:
        m: A mobile.

    Returns:
        The right arm of the mobile.
    """
    pass

Arm 数据抽象（仅供参考，这里无需执行任何操作）：

def arm(length, mobile_or_planet):
    """
    Construct an arm: a length of rod with a mobile or planet at the end.

    Arguments:
        length: The length of the rod.
        mobile_or_planet: A mobile or a planet at the end of the arm.

    Returns:
        An arm constructed from the given length and mobile or planet.
    """
    pass

def is_arm(s):
    """
    Return whether s is an arm.

    Arguments:
        s: An object to be checked.

    Returns:
        True if s is an arm, False otherwise.
    """
    pass

def length(s):
    """
    Select the length of an arm.

    Arguments:
        s: An arm.

    Returns:
        The length of the arm.
    """
    pass

def end(s):
    """
    Select the mobile or planet hanging at the end of an arm.

    Arguments:
        s: An arm.

    Returns:
        The mobile or planet at the end of the arm.
    """
    pass

Q3: Mass

通过完成 planet 构造函数和 mass 选择器来实现 planet 数据抽象。行星应使用双元素列表表示，其中第一个元素是字符串 'planet' ，第二个元素是行星的质量。 mass 函数应返回作为参数传递的 planet 对象的质量。

def planet(mass):
    """Construct a planet of some mass."""
    assert mass > 0
    "*** YOUR CODE HERE ***"

def mass(p):
    """Select the mass of a planet."""
    assert is_planet(p), 'must call mass on a planet'
    "*** YOUR CODE HERE ***"

def is_planet(p):
    """Whether p is a planet."""
    return type(p) == list and len(p) == 2 and p[0] == 'planet'

total_mass 函数演示了移动、手臂和行星抽象的用法。它已为您实现。您可以在以下问题中使用 total_mass 函数。

def examples():
    t = mobile(arm(1, planet(2)),
               arm(2, planet(1)))
    u = mobile(arm(5, planet(1)),
               arm(1, mobile(arm(2, planet(3)),
                             arm(3, planet(2)))))
    v = mobile(arm(4, t), arm(2, u))
    return t, u, v

def total_mass(m):
    """Return the total mass of m, a planet or mobile.

    >>> t, u, v = examples()
    >>> total_mass(t)
    3
    >>> total_mass(u)
    6
    >>> total_mass(v)
    9
    """
    if is_planet(m):
        return mass(m)
    else:
        assert is_mobile(m), "must get total mass of a mobile or a planet"
        return total_mass(end(left(m))) + total_mass(end(right(m)))

运行 total_mass 的 ok 测试，以确保您的 planet 和 mass 函数正确实现。

使用 Ok 测试您的代码：

python3 ok -q total_mass
点击查看答案
def planet(mass):
    """Construct a planet of some mass."""
    assert mass > 0
    "*** YOUR CODE HERE ***"
    return ['planet', mass]

def mass(p):
    """Select the mass of a planet."""
    assert is_planet(p), 'must call mass on a planet'
    "*** YOUR CODE HERE ***"
    return p[1]

def is_planet(p):
    """Whether p is a planet."""
    return type(p) == list and len(p) == 2 and p[0] == 'planet'

def examples():
    t = mobile(arm(1, planet(2)),
               arm(2, planet(1)))
    u = mobile(arm(5, planet(1)),
               arm(1, mobile(arm(2, planet(3)),
                             arm(3, planet(2)))))
    v = mobile(arm(4, t), arm(2, u))
    return t, u, v

def total_mass(m):
    """Return the total mass of m, a planet or mobile.

    >>> t, u, v = examples()
    >>> total_mass(t)
    3
    >>> total_mass(u)
    6
    >>> total_mass(v)
    9
    """
    if is_planet(m):
        return mass(m)
    else:
        assert is_mobile(m), "must get total mass of a mobile or a planet"
        return total_mass(end(left(m))) + total_mass(end(right(m)))

Q4: Balanced

实现 balanced 函数，该函数返回 m 是否为平衡移动装置。如果满足以下两个条件，则移动装置是平衡的：

  • 其左臂施加的扭矩等于其右臂施加的扭矩。左臂的扭矩是左杆的长度乘以悬挂在该杆上的总质量。右臂也是如此。例如，如果左臂的长度为 5 ，并且左臂末端悬挂着一个总质量为 10 的移动装置，则移动装置左侧的扭矩为 50 。
  • 悬挂在其臂末端的每个移动装置本身都是平衡的。 行星本身是平衡的，因为它们上面没有任何东西悬挂。

提示

您可以使用上面的 total_mass 函数。不要违反抽象障碍。相反，请使用已定义的选择器函数。

def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> p = mobile(arm(3, t), arm(2, u))
    >>> balanced(p)
    False
    >>> balanced(mobile(arm(1, v), arm(1, p)))
    False
    >>> balanced(mobile(arm(1, p), arm(1, v)))
    False
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q balanced
点击查看答案
def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> p = mobile(arm(3, t), arm(2, u))
    >>> balanced(p)
    False
    >>> balanced(mobile(arm(1, v), arm(1, p)))
    False
    >>> balanced(mobile(arm(1, p), arm(1, v)))
    False
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"
    if is_mobile(m):
        left_arm = left(m)
        right_arm = right(m)
        left_torque = length(left_arm) * total_mass(end(left_arm))
        right_torque = length(right_arm) * total_mass(end(right_arm))
        return left_torque == right_torque and balanced(end(left_arm)) and balanced(end(right_arm))
    else:
        return True  # Planets are always balanced #

Trees

Q5: Finding Berries!

校园里的松鼠需要你的帮助！校园里有很多树，松鼠想知道哪些树上有浆果。定义函数 berry_finder ，该函数接收一棵树，如果树包含值为 'berry' 的节点，则返回 True ，否则返回 False 。

提示

提示：要遍历特定树的每个分支，您可以考虑使用 for 循环来获取每个分支。

def berry_finder(t):
    """Returns True if t contains a node with the value 'berry' and 
    False otherwise.

    >>> 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
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q berry_finder
点击查看答案
def berry_finder(t):
    """Returns True if t contains a node with the value 'berry' and 
    False otherwise.

    >>> 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
    """
    "*** YOUR CODE HERE ***"
    if label(t) == 'berry':
        return True
    for branch in branches(t):
        if berry_finder(branch):
            return True
    return False

Q6: Maximum Path Sum

编写一个函数，接收一棵树并返回树中任何从根到叶路径的值的最大和。从根到叶路径是从根开始并到达树的某个叶的一系列节点。您可以假设树的标签为正数。

def max_path_sum(t):
    """Return the maximum root-to-leaf path sum of a tree.
    >>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
    >>> max_path_sum(t) # 1, 10
    11
    >>> t2 = tree(5, [tree(4, [tree(1), tree(3)]), tree(2, [tree(10), tree(3)])])
    >>> max_path_sum(t2) # 5, 2, 10
    17
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q max_path_sum
点击查看答案
def max_path_sum(t):
    """Return the maximum root-to-leaf path sum of a tree.
    >>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
    >>> max_path_sum(t) # 1, 10
    11
    >>> t2 = tree(5, [tree(4, [tree(1), tree(3)]), tree(2, [tree(10), tree(3)])])
    >>> max_path_sum(t2) # 5, 2, 10
    17
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return label(t)
    max_branch = 0
    for branch in branches(t):
        max_branch = max(max_path_sum(branch), max_branch)
    return max_branch + label(t)

Check Your Score Locally

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

python ok --score
我的得分：
PS D:\Github\CS61A_Fall2024\hw\hw04> python ok -q balanced
=====================================================================
Assignment: Homework 4
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---------------------------------------------------------------------
Test summary
    1 test cases passed! No cases failed.

Backup... 100% complete
Backup past deadline by 158 days, 19 hours, 44 minutes, and 26 seconds
Backup successful for user: zhiyong947@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/hw04/backups/7O9v1B

OK is up to date
PS D:\Github\CS61A_Fall2024\hw\hw04> python ok --score    
=====================================================================
Assignment: Homework 4
OK, version v1.18.1
=====================================================================

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

---------------------------------------------------------------------
Doctests for shuffle

>>> from hw04 import *
>>> shuffle(range(6))
[0, 3, 1, 4, 2, 5]
>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> shuffle(letters)
['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
>>> shuffle(shuffle(letters))
['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
>>> letters  # Original list should not be modified
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
Score: 1.0/1

---------------------------------------------------------------------
Doctests for deep_map

>>> from hw04 import *
>>> six = [1, 2, [3, [4], 5], 6]
>>> deep_map(lambda x: x * x, six)
>>> six
[1, 4, [9, [16], 25], 36]
>>> # Check that you're not making new lists
>>> s = [3, [1, [4, [1]]]]
>>> s1 = s[1]
>>> s2 = s1[1]
>>> s3 = s2[1]
>>> deep_map(lambda x: x + 1, s)
>>> s
[4, [2, [5, [2]]]]
>>> s1 is s[1]
True
>>> s2 is s1[1]
True
>>> s3 is s2[1]
True
Score: 1.0/1

---------------------------------------------------------------------
Doctests for total_mass

>>> from hw04 import *
>>> t, u, v = examples()
>>> total_mass(t)
3
>>> total_mass(u)
6
>>> total_mass(v)
9
Score: 1.0/1

---------------------------------------------------------------------
Doctests for balanced

>>> from hw04 import *
>>> t, u, v = examples()
>>> balanced(t)
True
>>> balanced(v)
True
>>> p = mobile(arm(3, t), arm(2, u))
>>> balanced(p)
False
>>> balanced(mobile(arm(1, v), arm(1, p)))
False
>>> balanced(mobile(arm(1, p), arm(1, v)))
False
>>> from construct_check import check
>>> # checking for abstraction barrier violations by banning indexing
>>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
True
Score: 1.0/1

---------------------------------------------------------------------
Doctests for berry_finder

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

---------------------------------------------------------------------
Doctests for max_path_sum

>>> from hw04 import *
>>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
>>> max_path_sum(t) # 1, 10
11
>>> t2 = tree(5, [tree(4, [tree(1), tree(3)]), tree(2, [tree(10), tree(3)])])
---------------------------------------------------------------------
Point breakdown
    shuffle: 1.0/1
    deep_map: 1.0/1
    total_mass: 1.0/1
    balanced: 1.0/1
    berry_finder: 1.0/1
    max_path_sum: 1.0/1

Score:
    Total: 6.0

Backup... 100% complete
Backup past deadline by 158 days, 19 hours, 45 minutes, and 11 seconds
Backup successful for user: zhiyong947@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/hw04/backups/jLYGZy

OK is up to date
PS D:\Github\CS61A_Fall2024\hw\hw03>

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