Due by 11:59pm on Thursday, October 8

查看英文原文

说明

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

提交：完成后使用python3 ok --submit来提交代码。你可以在截止日期前多次提交；只有最后一次提交会被评分。请检查你是否成功提交了代码到okpy.org。更多提交作业的说明请参见Lab0。

使用Ok:如果你对使用Ok有任何疑问，请参考本指南。

阅读材料：以下阅读材料可能对你有帮助

• Section 1.7
• Section 2.3

评分：作业评分基于正确性。每个错误的问题将使总分减少一分。课程大纲中有作业恢复政策。 本次作业满分为2分。

必答题

观看下面的提示视频来获得一些初步的指导:

抽象 (Abstraction)

悬挂模型

致谢。 这个悬挂模型示例来自 MIT 经典教材《计算机程序的构造和解释》中的一个经典问题，详见 第 2.2.2 节。

我们正在制作一个天文馆的悬挂模型。一个悬挂模型是一种悬挂式雕塑。二叉悬挂模型由两条悬臂组成。每条悬臂是一根具有特定长度的杆子，其末端悬挂着一个行星或另一个悬挂模型。例如，下图展示了悬挂模型 A 的左臂和右臂，以及它们各自末端所悬挂的内容。

我们将使用以下数据抽象来表示二叉悬挂模型：

• 一个 mobile（悬挂模型）必须具有左 arm（悬臂）和右 arm（悬臂）。
• 一个 arm（悬臂）具有正长度，并且必须在末端悬挂某物，可以是另一个 mobile（悬挂模型）或 planet（行星）。
• 一个 planet（行星）具有正大小，并且没有任何其他物体悬挂在其上。

悬臂长度递归（附注）

在开始之前，先对树形数据结构的递归做一个简要说明。请考虑以下函数。

def min_depth(t):
    """A simple function to return the distance between t's root and its closest leaf"""
    if is_leaf(t):
        return 0 # Base case---the distance between a node and itself is zero
    h = float('inf') # Python's version of infinity
    for b in branches(t):
        if is_leaf(b): return 1 # !!!
        h = min(h, 1 + min_depth(b))
    return h

标注有 !!! 的那一行违反了“悬臂长度”递归原则。虽然这段代码在存在该行时仍然能够正确运行，但实际上，我们在这里执行的检查应该由递归的下一级来完成。我们已经在 min_depth 函数中使用了 if 语句来处理叶子节点的输入，因此不应该再包含这行代码，以避免代码的冗余。

def min_depth(t):
    """A simple function to return the distance between t's root and its closest leaf"""
    if is_leaf(t):
        return 0
    h = float('inf')
    for b in branches(t):
        # Still works fine!
        h = min(h, 1 + min_depth(b))
    return h

“悬臂长度”递归不仅会导致代码冗余，还会使代码更加复杂，并掩盖递归函数的实际功能，从而增加编写递归函数的难度。我们希望递归情况仅处理一个递归层级，而不是进行额外的检查。我们可能会在某些情况下检查你的代码是否存在类似问题。

Q1: 重量

通过完成 planet 构造函数和 size 选择器来实现 planet 数据抽象，使得一个行星可以用一个包含两个元素的列表表示，其中第一个元素是字符串 'planet'，第二个元素是它的大小。 total_weight 示例展示了如何使用悬挂模型、悬臂和行星的抽象。

def mobile(left, right):
    """Construct a mobile from a left arm and a right arm."""
    assert is_arm(left), "left must be a arm"
    assert is_arm(right), "right must be a 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 a 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 a arm."""
    return type(s) == list and len(s) == 3 and s[0] == 'arm'

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

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

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

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

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

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

    >>> t, u, v = examples()
    >>> total_weight(t)
    3
    >>> total_weight(u)
    6
    >>> total_weight(v)
    9
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'total_weight', ['Index'])
    True
    """
    if is_planet(m):
        return size(m)
    else:
        assert is_mobile(m), "must get total weight of a mobile or a planet"
        return total_weight(end(left(m))) + total_weight(end(right(m)))

使用 Ok 来测试你的代码：

python3 ok -q total_weight --local

Q2: 平衡性

实现 balanced 函数，该函数用于判断 m 是否是一个平衡的 mobile（悬挂结构）。一个 mobile 在以下两种条件都满足时被认为是平衡的：

1. 其左侧支臂施加的力矩应等于右侧支臂施加的力矩。 左侧支臂的力矩等于左侧杆的长度乘以该杆上悬挂物体的总重量，右侧同理。 例如，如果左侧支臂的长度为 5，且左侧悬挂着一个重量为 10 的 mobile， 则左侧的力矩为 50。
2. 悬挂在支臂末端的所有 mobile 也必须是平衡的。

行星（planets）本身是平衡的，因为它们没有任何悬挂物。

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

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> w = mobile(arm(3, t), arm(2, u))
    >>> balanced(w)
    False
    >>> balanced(mobile(arm(1, v), arm(1, w)))
    False
    >>> balanced(mobile(arm(1, w), 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 --local

Q3: 总重量

实现 totals_tree 函数，该函数接受一个 mobile（或 planet）， 并返回一个 tree，其根节点的值为输入对象的总重量。 对于 planet，totals_tree 应返回一个叶子节点。 对于 mobile，totals_tree 应返回一个以该 mobile 的总重量为标签的树， 其分支为该 mobile 的两个支臂末端对应的 totals_tree。

def totals_tree(m):
    """Return a tree representing the mobile with its total weight at the root.

    >>> t, u, v = examples()
    >>> print_tree(totals_tree(t))
    3
      2
      1
    >>> print_tree(totals_tree(u))
    6
      1
      5
        3
        2
    >>> print_tree(totals_tree(v))
    9
      3
        2
        1
      6
        1
        5
          3
          2
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'totals_tree', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q totals_tree --local

树 (Trees)

Q4: 替换叶子 (Replace Leaf)

定义 replace_leaf 函数，该函数接受一棵树 t、一个待查找的值 find_value，以及一个替换值 replace_value。 replace_leaf 返回一棵新树，该树与 t 相同，但所有等于 find_value 的叶子标签都被替换为 replace_value。

def replace_leaf(t, find_value, replace_value):
    """Returns a new tree where every leaf value equal to find_value has
    been replaced with replace_value.

    >>> yggdrasil = tree('odin',
    ...                  [tree('balder',
    ...                        [tree('thor'),
    ...                         tree('freya')]),
    ...                   tree('frigg',
    ...                        [tree('thor')]),
    ...                   tree('thor',
    ...                        [tree('sif'),
    ...                         tree('thor')]),
    ...                   tree('thor')])
    >>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
    >>> print_tree(replace_leaf(yggdrasil, 'thor', 'freya'))
    odin
      balder
        freya
        freya
      frigg
        freya
      thor
        sif
        freya
      freya
    >>> laerad == yggdrasil # Make sure original tree is unmodified
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q replace_leaf --local

Q5: 前序遍历 (Preorder)

定义函数 preorder，该函数以一棵树作为参数，并返回一个列表， 其中包含树中所有节点的值，排列顺序与 print_tree 打印它们的顺序相同。

下图展示了节点的打印顺序，箭头表示函数调用的顺序。

注意：这种遍历树的顺序称为前序遍历（preorder traversal）。

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q preorder --local

Q6: 路径匹配 (Has Path)

编写函数 has_path，该函数接受一棵树 t 和一个字符串 word。 如果存在一条从根节点开始的路径，使得路径上的节点标签依次拼出 word，则返回 True，否则返回 False。 （这种数据结构被称为 字典树（trie），它有很多有趣的应用，比如自动补全）。 你可以假设树中每个节点的 label 恰好是一个字符。

def has_path(t, word):
    """Return whether there is a path in a tree where the entries along the path
    spell out a particular word.

    >>> greetings = tree('h', [tree('i'),
    ...                        tree('e', [tree('l', [tree('l', [tree('o')])]),
    ...                                   tree('y')])])
    >>> print_tree(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    """
    assert len(word) > 0, 'no path for empty word.'
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q has_path --local

Submit

Make sure to submit this assignment by running:

python3 ok --submit

附加题

Q7: 区间抽象 (Interval Abstraction)

Alyssa 的程序尚未完成，因为她尚未指定区间抽象的实现。 她已经为你实现了构造函数；请补全选择器（selectors）的实现。

def interval(a, b):
    """Construct an interval from a to b."""
    return [a, b]

def lower_bound(x):
    """Return the lower bound of interval x."""
    "*** YOUR CODE HERE ***"

def upper_bound(x):
    """Return the upper bound of interval x."""
    "*** YOUR CODE HERE ***"

使用 Ok 来解锁并测试你的代码：

python3 ok -q interval -u --local
python3 ok -q interval --local

Louis Reasoner 还提供了一个区间乘法的实现。但要注意：他的代码存在一些数据抽象违规问题， 请在问题变成一场“火龙卷”之前帮他修复： https://www.bilibili.com/video/BV18x411i7dj/

def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    p1 = x[0] * y[0]
    p2 = x[0] * y[1]
    p3 = x[1] * y[0]
    p4 = x[1] * y[1]
    return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]

使用 Ok 来解锁并测试你的代码：

python3 ok -q mul_interval -u
python3 ok -q mul_interval

Q8: 区间减法 (Sub Interval)

参考 Alyssa 的推理方式，实现一个用于区间的减法函数。 如果发现自己在重复代码，尽量复用已有的函数。

def sub_interval(x, y):
    """Return the interval that contains the difference between any value in x
    and any value in y."""
    "*** YOUR CODE HERE ***"

使用 Ok 来解锁并测试你的代码：

python3 ok -q sub_interval -u --local
python3 ok -q sub_interval --local

Q9: 区间除法 (Div Interval)

Alyssa 通过乘以 y 的倒数来实现了区间除法。 但是，专家级系统程序员 Ben Bitdiddle 看了一眼后指出， 如果除数区间跨越零，除法的意义就变得不清楚了。 请在 Alyssa 的代码中添加一个 assert 语句，以确保不会使用包含零的区间作为除数：

def div_interval(x, y):
    """Return the interval that contains the quotient of any value in x divided by
    any value in y. Division is implemented as the multiplication of x by the
    reciprocal of y."""
    "*** YOUR CODE HERE ***"
    reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y))
    return mul_interval(x, reciprocal_y)

使用 Ok 来解锁并测试你的代码：

python3 ok -q div_interval -u --local
python3 ok -q div_interval --local

Q10: 并联电阻计算差异 (Par Diff)

经过大量努力，Alyssa P. Hacker 终于完成了她的系统。 数年后，当她早已将其忘得一干二净时，突然接到了用户 Lem E. Tweakit 的狂怒电话。 原来，Lem 发现 并联电阻的计算公式 可以用两种代数等价的方式表示：

par1(r1, r2) = (r1 * r2) / (r1 + r2)

或者

par2(r1, r2) = 1 / (1/r1 + 1/r2)

他编写了以下两个程序，它们分别使用不同的方法计算 并联电阻 公式：

def par1(r1, r2):
    return div_interval(mul_interval(r1, r2), add_interval(r1, r2))

def par2(r1, r2):
    one = interval(1, 1)
    rep_r1 = div_interval(one, r1)
    rep_r2 = div_interval(one, r2)
    return div_interval(one, add_interval(rep_r1, rep_r2))

Lem 抱怨说，Alyssa 的程序在这两种计算方式下得到了不同的结果， 这可是个严重的问题。

请证明 Lem 是对的。尝试在不同的算术表达式上测试系统的行为， 创建一些区间 r1 和 r2，并展示 par1 和 par2 确实可能产生不同的结果。

def check_par():
    """Return two intervals that give different results for parallel resistors.

    >>> r1, r2 = check_par()
    >>> x = par1(r1, r2)
    >>> y = par2(r1, r2)
    >>> lower_bound(x) != lower_bound(y) or upper_bound(x) != upper_bound(y)
    True
    """
    r1 = interval(1, 1) # Replace this line!
    r2 = interval(1, 1) # Replace this line!
    return r1, r2

使用 Ok 来测试你的代码：

python3 ok -q check_par --local

Q11: 多重引用问题 (Multiple References)

另一位用户 Eva Lu Ator 也注意到，不同但代数等价的表达式计算出来的区间不同。 她说问题出在对同一个区间的多重引用上。

多重引用问题：使用 Alyssa 系统进行区间计算的公式，如果能够写成一种形式， 使得没有任何表示不确定数字的变量被重复引用，那么它的误差将更小。

因此，她认为 par2 比 par1 更适合用于并联电阻的计算（参见 Q10：Par Diff 了解这两个函数！）。 她是对的吗？为什么？请写一个函数返回一个包含你答案的字符串：

提示：要创建一个多行字符串，必须使用三引号 """ like this """.

def multiple_references_explanation():
    return """The multiple reference problem..."""

Q12: 二次函数 (Quadratic)

编写一个函数 quadratic，返回一个 二次函数 f(t) 在区间 x 上的值域：

f(t) = a*t*t + b*t + c

确保你的实现返回的区间最小， 一个不会有多重引用问题的区间。

提示：二次函数的导数 f'(t) = 2*a*t + b，因此二次函数的极值点为 -b/(2*a)：

def quadratic(x, a, b, c):
    """Return the interval that is the range of the quadratic defined by
    coefficients a, b, and c, for domain interval x.

    >>> str_interval(quadratic(interval(0, 2), -2, 3, -1))
    '-3 to 0.125'
    >>> str_interval(quadratic(interval(1, 3), 2, -3, 1))
    '0 to 10'
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码：

python3 ok -q quadratic --local