Skip to main content

CS 61A 2024 春季学期 | 家庭作业 4

家庭作业 4:序列、ADT 树

截止日期:2 月 29 日周四晚 11:59

须知

下载 hw04.zip。压缩包内含 [hw04.py] 文件以及 ok 自动评分器。

提交: 完成作业后,请将所有已编辑的代码文件上传至 Gradescope。截止日期前可多次提交,最终提交版本将被评分。请务必检查在 Gradescope 上是否成功提交。更多提交说明请参考 Lab 0

使用 Ok: 如有关于 Ok 使用的问题,请参考本指南

阅读材料: 以下参考资料可能对您有所帮助:

评分标准: 作业根据正确性评分,每错一题扣一分。本次作业总分 2 分。

必做题

入门视频

入门视频:这些视频将帮助你解决本次作业中的编程问题。

观看视频需登录 berkeley.edu 邮箱。

YouTube 链接

序列

Q1:深度映射

编写一个函数 deep_map,它接受一个列表 s 和一个单参数函数 fs 可能是一个嵌套列表,即包含其他列表的列表。deep_map 通过将 s 或其包含的任何列表中的每个元素替换为对该元素调用 f 的结果来修改 s

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

提示: type(a) == lista 为列表时返回 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

数据抽象

鸣谢

此问题基于计算机程序的构造与解释 第 2.2.2 节 中的一个问题。

Mobile example

我们正在制作一个天文馆吊饰。一个 吊饰 是一种悬挂式雕塑。一个二元吊饰由两个臂组成。每个臂是一定长度的杆,杆上悬挂着一颗行星或另一个吊饰。例如,下图显示了吊饰 A 的左臂和右臂,以及悬挂在每个臂末端的物体。

Labeled Mobile example

我们将使用以下数据抽象来表示二元吊饰。

  • 一个 mobile 必须同时具有左 arm 和右 arm
  • 一个 arm 具有正长度,并且必须在末端悬挂一些东西,即 mobileplanet
  • 一个 planet 具有正质量,并且没有任何东西悬挂在它上面。

以下是用于吊饰的各种数据抽象的实现。mobilearm 数据抽象已为您完成。

Mobile 数据抽象实现(仅供参考,无需修改):

def mobile(left, right):
"""Construct a mobile from a left arm and a right arm."""
assert is_arm(left), "left must be an arm"
assert is_arm(right), "right must be an arm"
return ['mobile', left, right]
def is_mobile(m):
"""Return whether m is a mobile."""
return type(m) == list and len(m) == 3 and m[0] == 'mobile'

def left(m):
"""Select the left arm of a mobile."""
assert is_mobile(m), "must call left on a mobile"
return m[1]

def right(m):
"""Select the right arm of a mobile."""
assert is_mobile(m), "must call right on a mobile"
return m[2]

臂膀数据抽象的实现 ((仅供参考,无需修改)):

def arm(length, mobile_or_planet):
"""Construct an arm: a length of rod with a mobile or planet at the end."""
assert is_mobile(mobile_or_planet) or is_planet(mobile_or_planet)
return ['arm', length, mobile_or_planet]

def is_arm(s):
"""Return whether s is an arm."""
return type(s) == list and len(s) == 3 and s[0] == 'arm'

def length(s):
"""Select the length of an arm."""
assert is_arm(s), "must call length on an arm"
return s[1]

def end(s):
"""Select the mobile or planet hanging at the end of an arm."""
assert is_arm(s), "must call end on an arm"
return s[2]

Q2: 质量 (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 函数演示了 mobile、arm 和 planet 抽象的用法。 你不需要在这里实现任何东西。你可以在以下问题中使用 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)))

运行 ok 测试 total_mass,确保 planetmass 函数已正确实现。

用 Ok 测试你的代码:

python3 ok -q total_mass

Q3: 平衡

实现 balanced 函数,判断 m 是否为平衡的 mobile。 平衡需要满足以下两个条件:

  1. 左臂和右臂的扭矩相等。 扭矩的计算方式是:杆的长度乘以悬挂在其上的总质量。 例如,左臂长为 5,悬挂的总质量为 10mobile,则左侧扭矩为 50
  2. 每个手臂末端悬挂的 mobile 本身也必须是平衡的。

行星本身即为平衡。

你可以使用上面的 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

Q4: 最大路径和

编写一个函数,输入一棵树,返回从根节点到叶节点的所有路径中,节点值之和的最大值。 假设树的所有节点值均为正数。

def max_path_sum(t):
"""返回这棵树从根节点到叶节点的最大路径和。
>>> 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