Skip to main content

CS 61A 2024 春季学期 | 第六次作业

家庭作业 6：面向对象编程 (OOP)，链表​

截止时间：3 月 14 日周四晚 11:59

作业须知​

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

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

使用 Ok： 如有关于 Ok 的疑问，请查阅指南。

评分： 本次作业根据正确率评分，每错一题扣一分，总分 2 分。

作业题目​

视频辅导​

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

观看视频请使用您的 berkeley.edu 邮箱登录。

YouTube 链接

期中调查​

Q1：期中反馈​

作为本次作业的一部分，请填写 期中反馈 表格。

保密性： 您的回复将被保密，只有授课老师可以看到未匿名的数据。更多细节请参考调查问卷本身。

完成调查后，您将看到一个密码（如果您错过了，它也应该在您收到的确认电子邮件的底部）。将此密码作为字符串放在 Python 文件中写有 passphrase = '*** PASSPHRASE HERE ***' 的行上。

使用 Ok 测试您的代码：

python3 ok -q midsem_survey

面向对象编程 (OOP)​

Q2：自动贩卖机​

在本题中，您将创建一个 自动贩卖机，该售货机销售单一产品并在需要时提供找零。

创建一个名为 VendingMachine 的类，该类表示某种产品的自动贩卖机。VendingMachine 对象返回描述其交互的字符串。请确保输出结果与 doctest 中的字符串完全一致，包括标点和空格！

您可能会发现 Python 的格式化字符串文字或 f-strings 很有用。一个简单的例子：

>>> feeling = 'love'
>>> course = '61A!'
>>> f'I {feeling} {course}'
'I love 61A!'

填写 VendingMachine 类，请酌情添加属性和方法，使其行为与以下 doctest 匹配：

class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Nothing left to vend. Please restock.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'
    >>> v.restock(2)
    'Current candy stock: 2'
    >>> v.vend()
    'Please add $10 more funds.'
    >>> v.add_funds(7)
    'Current balance: $7'
    >>> v.vend()
    'Please add $3 more funds.'
    >>> v.add_funds(5)
    'Current balance: $12'
    >>> v.vend()
    'Here is your candy and $2 change.'
    >>> v.add_funds(10)
    'Current balance: $10'
    >>> v.vend()
    'Here is your candy.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'
```>>> w = VendingMachine('汽水', 2)
    >>> w.restock(3)
    'Current soda stock: 3'
    >>> w.restock(3)
    'Current soda stock: 6'
    >>> w.add_funds(2)
    'Current balance: $2'
    >>> w.vend()
    'Here is your soda.'
    """
    "*** 请在此处填写你的代码 ***"

用 Ok 测试你的代码:

python3 ok -q VendingMachine

在本地查看你的分数​

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

python3 ok --score

这不会提交你的作业！ 当你对分数满意时，将作业提交到 Gradescope 以获得学分。

提交​

提交作业：上传你编辑过的文件到 Gradescope 对应的作业。Lab 00 包含详细的说明。

此外，所有不在大型实验课的学生必须填写此考勤表。 每周提交此表格，无论你是否参加了实验课，或者因为正当理由错过了实验课。 大型实验课的学生无需填写考勤表。

可选问题​

Q3: 存储数字​

编写函数 store_digits，接收整数 n，返回一个链表，链表的每个元素都是 n 的一位数字。

重要提示：不要使用任何字符串操作函数，如 str 和 reversed。

def store_digits(n):
    """将正数 n 的数字存储在链表中。

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    >>> store_digits(2450)
    Link(2, Link(4, Link(5, Link(0))))
    >>> # 检查是否使用了禁用函数
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
    >>> print("请勿使用 str 或 reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
    """
    "*** 请在此处填写你的代码 ***"

用 Ok 测试你的代码:

python3 ok -q store_digits

Q4: 可变映射​

实现 deep_map_mut(func, link)，将函数 func 应用于链表 lnk 的所有元素。 如果元素本身是链表，则递归应用 func。

你的实现应修改原始链表，不要创建新的链表.

提示：可以使用内置函数 isinstance.

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False

构造检查：此问题的最后一个 doctest 确保你没有创建新链表. 如果 doctest 未通过，请检查是否通过构造函数创建了链表.

s = Link(1)
def deep_map_mut(func, lnk):
    """通过将每个元素替换为 `func(元素)` 的结果来修改深度链接 `lnk`. 不创建新的链接（因此不使用 Link 的构造函数）。

    不返回修改后的 Link 对象。

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> print(link1)
    <3 <4> 5 6>
    >>> # 禁止在调用 `deep_map_mut` 之前创建新链接
    >>> Link.__init__, hold = lambda *args: print("不要创建任何新链接。"), Link.__init__
    >>> try:
    ...     deep_map_mut(lambda x: x * x, link1)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    <9 <16> 25 36>
    """
    "*** 请在此处填写你的代码 ***"

使用 Ok 来测试你的代码:

python3 ok -q deep_map_mut

Q5: 双列表​

实现一个名为 two_list 的函数，该函数接受两个列表作为输入，并返回一个链表。第一个列表包含要放入链表的值，第二个列表包含对应值的数量。两个列表大小相同，且长度均大于等于1。第二个列表中的元素均大于0。

def two_list(vals, counts):
    """
    根据输入的两个列表返回一个链表。假设 vals 和 counts 的大小相同。vals 中的元素表示值，而 counts 中对应元素表示该值在链表中出现的次数。假设两个列表都至少有一个元素。
    >>> a = [1, 3]
    >>> b = [1, 1]
    >>> c = two_list(a, b)
    >>> c
    Link(1, Link(3))
    >>> a = [1, 3, 2]
    >>> b = [2, 2, 1]
    >>> c = two_list(a, b)
    >>> c
    Link(1, Link(1, Link(3, Link(3, Link(2)))))
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q two_list

考试练习​

本次作业还包含一些往年考题，供大家练习。这些题目无需提交，欢迎练习！

面向对象编程

  1. 2022 年春季 MT2 Q8：CS61A 呈现 Hoop 游戏。
  2. 2020 年秋季 MT2 Q3：稀疏列表
  3. 2019 年秋季 MT2 Q7：版本 2.0

链表

  1. 2020 年秋季期末 Q3：大学派对
  2. 2018 年秋季 MT2 Q6：弗兰肯链
  3. 2017 年春季 MT1 Q5：插入