作业4: 非局部, 迭代器
Homework 4: Nonlocal, Iterators

Due by 11:59pm on Thursday, October 15

查看英文原文

说明

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

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

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

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

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

必答题

提示视频

观看此视频来获取一些解决本作业问题的提示。

非局部 (Nonlocal)

Q1: 创建银行

在讲座中,我们学习了如何使用函数来创建可变对象。例如,下面的函数 make_withdraw,可以生成一个从账户中取款的函数:

def make_withdraw(balance):
    """Return a withdraw function with BALANCE as its starting balance.
    >>> withdraw = make_withdraw(1000)
    >>> withdraw(100)
    900
    >>> withdraw(100)
    800
    >>> withdraw(900)
    'Insufficient funds'
    """
    def withdraw(amount):
        nonlocal balance
        if amount > balance:
            return 'Insufficient funds'
        balance = balance - amount
        return balance
    return withdraw

编写一个新的函数 make_bank,它可以创建一个初始余额为 balance 的银行账户,并返回另一个函数。这个新函数能够进行取款和存款操作。新函数接受两个参数:messageamount。当传入的 message 是 'deposit' 时,银行会将 amount 存入账户。当传入的 message 是 'withdraw' 时,银行会尝试从账户中取出 amount。如果账户中没有足够的资金进行取款,函数将返回字符串 'Insufficient funds'。如果传入的 message 不是这两个命令之一,函数应返回 'Invalid message'。示例可以在 doctests 中查看。

def make_bank(balance):
    """Returns a bank function with a starting balance. Supports
    withdrawals and deposits.

    >>> bank = make_bank(100)
    >>> bank('withdraw', 40)    # 100 - 40
    60
    >>> bank('hello', 500)      # Invalid message passed in
    'Invalid message'
    >>> bank('deposit', 20)     # 60 + 20
    80
    >>> bank('withdraw', 90)    # 80 - 90; not enough money
    'Insufficient funds'
    >>> bank('deposit', 100)    # 80 + 100
    180
    >>> bank('goodbye', 0)      # Invalid message passed in
    'Invalid message'
    >>> bank('withdraw', 60)    # 180 - 60
    120
    """
    def bank(message, amount):
        "*** YOUR CODE HERE ***"
    return bank

使用 Ok 来测试你的代码:

python3 ok -q make_bank --local

Q2: 密码保护

编写一个基于上一题中 make_withdraw 函数的新版本,该版本返回受密码保护的取款函数。也就是说,make_withdraw 除了接受初始余额外,还应接受一个密码参数(字符串)。返回的函数应接受两个参数:取款金额和密码。

受密码保护的 withdraw 函数应仅在密码正确时进行取款操作。当收到错误密码时,函数应:

  1. 将该错误密码存储在一个列表中,并且
  2. 返回字符串 'Incorrect password'

如果取款函数被调用了三次并提供了错误的密码 <p1><p2><p3>,则该账户将被冻结。之后所有对该函数的调用都应返回:

"Frozen account. Attempts: [<p1>, <p2>, <p3>]"

提示: 你可以使用 str 函数将列表转换为字符串。例如,对于列表 s = [1, 2, 3],表达式 "The list s is: " + str(s) 会转换为 "The list s is: [1, 2, 3]"

错误的密码可以相同或不同:

def make_withdraw(balance, password):
    """Return a password-protected withdraw function.

    >>> w = make_withdraw(100, 'hax0r')
    >>> w(25, 'hax0r')
    75
    >>> error = w(90, 'hax0r')
    >>> error
    'Insufficient funds'
    >>> error = w(25, 'hwat')
    >>> error
    'Incorrect password'
    >>> new_bal = w(25, 'hax0r')
    >>> new_bal
    50
    >>> w(75, 'a')
    'Incorrect password'
    >>> w(10, 'hax0r')
    40
    >>> w(20, 'n00b')
    'Incorrect password'
    >>> w(10, 'hax0r')
    "Frozen account. Attempts: ['hwat', 'a', 'n00b']"
    >>> w(10, 'l33t')
    "Frozen account. Attempts: ['hwat', 'a', 'n00b']"
    >>> type(w(10, 'l33t')) == str
    True
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码:

python3 ok -q make_withdraw --local

迭代器和生成器

Q3: 重复值

实现一个函数(不是生成器函数),该函数返回迭代器 t 中第一个连续出现 k 次的值。正如讲座中提到的,迭代器可以通过 next(t) 函数或 for 循环来获取值。测试数据保证在迭代完成前有符合条件的结果。如果你遇到迭代器已完成并报错的情况,说明程序未能正确识别目标值。遍历这些项时,如果同一个迭代器被传入 repeated 函数两次,第二次调用应从第一次调用结束的位置继续。doctests 中有该行为的一个示例。

def repeated(t, k):
    """Return the first value in iterator T that appears K times in a row. Iterate through the items such that
    if the same iterator is passed into repeated twice, it continues in the second call at the point it left off
    in the first.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s2, 3)
    8
    >>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(s, 3)
    2
    >>> repeated(s, 3)
    5
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(s2, 3)
    2
    """
    assert k > 1
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码:

python3 ok -q repeated --local

Q4: 生成排列

给定一个由互异元素组成的序列,序列的排列是指将序列中的元素以任意顺序排成一列组成的列表。例如,[2, 1, 3][1, 3, 2][3, 2, 1] 都是序列 [1, 2, 3] 的一些排列。

实现 permutations 函数,这是一个生成器函数,它接受一个序列 seq 并返回一个生成器,该生成器会通过yield返回 seq 的所有排列。

排列可以按任何顺序生成。请注意,doctests 测试的是你是否生成了所有可能的排列,而不用考虑特定的顺序。内置的 sorted 函数接受一个可迭代对象,并返回一个包含该可迭代对象中元素的非递减顺序列表。

提示: 如果你已经有了不包含第一个元素的 seq 的所有排列,你如何利用这些排列来生成 seq 所有的排列?

提示: 如果你遇到困难,可以观看本问题的提示视频,了解如何解决这个问题。

def permutations(seq):
    """Generates all permutations of the given sequence. Each permutation is a
    list of the elements in SEQ in a different order. The permutations may be
    yielded in any order.

    >>> perms = permutations([100])
    >>> type(perms)
    <class 'generator'>
    >>> next(perms)
    [100]
    >>> try: #this piece of code prints "No more permutations!" if calling next would cause an error
    ...     next(perms)
    ... except StopIteration:
    ...     print('No more permutations!')
    No more permutations!
    >>> sorted(permutations([1, 2, 3])) # Returns a sorted list containing elements of the generator
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> sorted(permutations((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(permutations("ab"))
    [['a', 'b'], ['b', 'a']]
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码:

python3 ok -q permutations --local

Submit

Make sure to submit this assignment by running:

python3 ok --submit

附加题

Q5: 联合账户

假设我们的银行系统需要支持创建联合账户。定义一个函数 make_joint,它接受三个参数:

  1. 一个受密码保护的 withdraw 函数,
  2. 定义该 withdraw 函数时使用的原始密码,
  3. 一个也可以访问原始账户的新密码。

如果密码错误或由于底层账户被锁定而无法验证,make_joint 应错误。否则,它返回一个 withdraw 函数,该函数可以使用新密码或旧密码提供对原始账户的额外访问。这两个函数从同一余额中取款。提供给任一函数的不正确密码将被存储,并在三次错误尝试后导致函数被锁定。

提示:解决方案很短(少于 10 行),并且不包含任何字符串字面量(直接写的字符串)!关键是用正确的密码和金额调用 withdraw,然后解析返回结果。你可以假设所有取款失败的情况(如密码错误、账户被锁定或余额不足)都会返回一个字符串,而成功的取款操作将返回一个数字。

使用 type(value) == str 来测试某个 value 是否为字符串:

def make_joint(withdraw, old_pass, new_pass):
    """Return a password-protected withdraw function that has joint access to
    the balance of withdraw.

    >>> w = make_withdraw(100, 'hax0r')
    >>> w(25, 'hax0r')
    75
    >>> make_joint(w, 'my', 'secret')
    'Incorrect password'
    >>> j = make_joint(w, 'hax0r', 'secret')
    >>> w(25, 'secret')
    'Incorrect password'
    >>> j(25, 'secret')
    50
    >>> j(25, 'hax0r')
    25
    >>> j(100, 'secret')
    'Insufficient funds'

    >>> j2 = make_joint(j, 'secret', 'code')
    >>> j2(5, 'code')
    20
    >>> j2(5, 'secret')
    15
    >>> j2(5, 'hax0r')
    10

    >>> j2(25, 'password')
    'Incorrect password'
    >>> j2(5, 'secret')
    "Frozen account. Attempts: ['my', 'secret', 'password']"
    >>> j(5, 'secret')
    "Frozen account. Attempts: ['my', 'secret', 'password']"
    >>> w(5, 'hax0r')
    "Frozen account. Attempts: ['my', 'secret', 'password']"
    >>> make_joint(w, 'hax0r', 'hello')
    "Frozen account. Attempts: ['my', 'secret', 'password']"
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试你的代码:

python3 ok -q make_joint --local

Q6: 余数生成器

与函数类似,生成器也可以是高阶的。对于这个问题,我们将编写 remainders_generator 函数,它会生成一系列生成器对象。

remainders_generator 函数接受一个整数 m,并生成 m 个不同的生成器。第一个生成器会生成 m 的倍数(即除以 m 余数为 0 的数)。第二个生成器会生成除以 m 余数为 1 的自然数。最后一个生成器会生成除以 m 余数为 m - 1 的自然数。

提示: 你可以调用 naturals 函数来创建无限自然数的生成器。

提示: 考虑定义一个内部生成器函数(在函数内部定义的生成器)。生成的不同生成器之间的唯一区别在于:不同的生成器的元素在除以 m 时具有特定的余数。这告诉你内部函数应该接受哪些参数呢?

def remainders_generator(m):
    """
    Yields m generators. The ith yielded generator yields natural numbers whose
    remainder is i when divided by m.

    >>> import types
    >>> [isinstance(gen, types.GeneratorType) for gen in remainders_generator(5)]
    [True, True, True, True, True]
    >>> remainders_four = remainders_generator(4)
    >>> for i in range(4):
    ...     print("First 3 natural numbers with remainder {0} when divided by 4:".format(i))
    ...     gen = next(remainders_four)
    ...     for _ in range(3):
    ...         print(next(gen))
    First 3 natural numbers with remainder 0 when divided by 4:
    4
    8
    12
    First 3 natural numbers with remainder 1 when divided by 4:
    1
    5
    9
    First 3 natural numbers with remainder 2 when divided by 4:
    2
    6
    10
    First 3 natural numbers with remainder 3 when divided by 4:
    3
    7
    11
    """
    "*** YOUR CODE HERE ***"

注意:如果你的实现是正确的,那么 remainder_generator 生成的每个 生成器 都是 无限的 —— 你可以无限次调用 next,而不会遇到 StopIteration 异常。

使用 Ok 来测试你的代码:

python3 ok -q remainders_generator --local