作业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
的银行账户,并返回另一个函数。这个新函数能够进行取款和存款操作。新函数接受两个参数:message
和 amount
。当传入的 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
函数应仅在密码正确时进行取款操作。当收到错误密码时,函数应:
- 将该错误密码存储在一个列表中,并且
- 返回字符串
'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
,它接受三个参数:
- 一个受密码保护的
withdraw
函数, - 定义该
withdraw
函数时使用的原始密码, - 一个也可以访问原始账户的新密码。
如果密码错误或由于底层账户被锁定而无法验证,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