hw整理
hw 整理
建议刚开始做的时候看一下文章:CS 61A Summary,熟悉一些知识点。
hw01
这里比较有趣的是a_plus_abs_b
,这里使用的是引入函数名作为参数。
from operator import add, sub |
hw02
挺有趣的,对高级函数有了更深的理解。
from operator import add, mul |
总结
这里强调一下最后一道题目:
为什么最后是这样写:简单总结就是先处理n-1
次的结果,最后再进行第n
次处理。
在这段代码中,
lambda x: f(make_repeater(f, n-1)(x))
是一个匿名函数,用来递归地将函数f
应用n
次。我们逐步解释这个
lambda
表达式和它的作用:
基本概念:
lambda x: ...
定义了一个匿名函数,它接受一个参数x
。f
是你传入的函数,n
是要应用f
的次数。递归调用:
make_repeater(f, n-1)
表示递归调用make_repeater
函数,生成一个新的函数,这个新的函数会将f
应用n-1
次。(x)
则是对这个递归得到的函数进行调用,传入参数x
。核心逻辑:
lambda x: f(make_repeater(f, n-1)(x))
可以理解为:
- 先递归调用
make_repeater(f, n-1)
,获取一个函数,该函数会将f
应用n-1
次。- 然后将参数
x
传入这个递归函数,得到f
应用n-1
次后的结果。- 最后,再把这个结果作为输入传递给
f
,从而实现f
的第n
次应用。举个例子:
假设
f = square
,n = 3
,x = 5
:
首次调用
make_repeater(square, 3)
:
- 返回的
lambda
表达式会调用square(make_repeater(square, 2)(x))
。
make_repeater(square, 2)
:
- 返回
lambda x: square(make_repeater(square, 1)(x))
。
make_repeater(square, 1)
:
- 返回
lambda x: square(make_repeater(square, 0)(x))
。
make_repeater(square, 0)
:
- 直接返回
identity
函数,即返回输入的值。这样,最终调用
lambda x: square(square(square(5)))
,即计算square(square(square(5)))
,最终结果为390625
。总结一下,这个
lambda
表达式通过递归的方式,逐步将函数f
应用多次,直到n
次为止。
hw03
开始难起来了,但是收获还是不错的。
HW_SOURCE_FILE = __file__ |
总结
count_dollars
和count_dollars_upwards
需要参考一下implementation ofcount_partitions
,分为两种情况讨论:- 可以
n
减去m
,继续拆分。 - 不能,则
n
不变,m
减小,尝试继续拆分。 - 这里主要考虑的是所给的货币类型,所以需要使用
next_smaller_dollar
和next_larger_dollar
函数。
- 可以
汉诺塔问题分析:
我们需要的是将上面的盘子移动其他柱子,然后最大盘(相对于位于其上面的盘子来说)移动到理想的柱子,最后再将其他盘移动到最大的柱子上面。
按照这种思路进行编码即可。
make_anonymous_factorial
:这道是关于lambda
表达式和递归函数的使用,建议看看下面的注解:这两个
lambda
表达式一起实现了一个匿名递归函数,用于计算阶乘。让我们逐步解析它们。完整的代码:
(lambda f: lambda k: f(f, k)) (lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))
这个表达式实际上有两个主要的
lambda
函数,它们是如何互相配合的呢?第一部分:外部
lambda f: lambda k: f(f, k)
lambda f: lambda k: f(f, k)
- 这个表达式定义了一个函数,它接收一个参数
f
,并返回一个新的函数。 - 这个新的函数是
lambda k: f(f, k)
,它接收一个参数k
,然后调用f(f, k)
。 - 作用:这个
lambda
表达式实际上是将传入的函数f
传递给自身,以实现递归调用。它通过f(f, k)
这种形式,使f
能够递归调用自身。
作用机制:
- 当我们将一个匿名函数(稍后解释)传递给这个
lambda f: ...
时,它会生成一个新的函数,这个新函数接收一个参数k
,并在内部递归调用f(f, k)
。 f
是下一层的递归函数,而f(f, k)
表示调用f
并传递自身f
,从而实现递归调用。
第二部分:内部
lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1)))
lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1)))
- 这是用于计算阶乘的核心递归函数。
- 它有两个参数:
f
:用于递归调用的函数(即自身)。k
:当前要计算的阶乘数字。
递归逻辑:
k if k == 1 else mul(k, f(f, sub(k, 1)))
是阶乘计算的递归过程:- 如果
k == 1
,直接返回k
,即递归基线:1! = 1
。 - 否则,调用
mul(k, f(f, sub(k, 1)))
,递归计算k-1
的阶乘:sub(k, 1)
计算k - 1
。f(f, sub(k, 1))
递归调用自身来计算k-1
的阶乘。- 然后用
mul(k, ...)
乘以当前的k
值,实现k * (k-1)!
。
- 如果
组合效果:
现在让我们看看这两个
lambda
是如何配合的。- 外层
lambda
接受内部的递归函数,并通过f(f, k)
方式将自身传递给自己,实现递归调用。 - 内层
lambda
执行阶乘的递归逻辑,并通过递归调用f(f, k)
来计算阶乘。
整体计算过程:
假设我们调用
make_anonymous_factorial()(5)
,整个过程如下:外部
lambda
立即调用,并传递了内部lambda
。调用
(lambda f: lambda k: f(f, k))(...)
,将内部lambda
传递进去:- 这返回了一个新的函数
lambda k: f(f, k)
,这个函数接收k
,并开始计算阶乘。
- 这返回了一个新的函数
当我们调用
make_anonymous_factorial()(5)
时,k = 5
,于是递归开始:- 首先调用
mul(5, f(f, 4))
。 - 再递归调用
f(f, 4)
,进入下一个阶段的计算,依次递归直到k == 1
。
- 首先调用
最终,整个递归结果为
5 * 4 * 3 * 2 * 1 = 120
。
总结:
- 外层
lambda f: lambda k: f(f, k)
:这是一个生成递归函数的机制,通过f(f, k)
实现递归调用。 - 内层
lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1)))
:这是阶乘的递归逻辑,用来计算阶乘。
这个设计通过匿名递归的方式,使用函数自身来执行递归操作,实现了阶乘计算。
- 这个表达式定义了一个函数,它接收一个参数
hw04
def shuffle(s): |
总结
主要要balanced
和max_sum
比较困难一些,因为需要看懂一些函数的定义。
max_sum
比较简单,如果接触过树形dp
的话不难,我们只需要进行计算子树的最大值即可,再加上根节点的值。berry_finder
注意一下可能berry
不是作为叶子节点,而是其中一部分。这里使用'berry' in str(label(t))
,可以将label(t)
转化为字符串,然后进行判断是否合法即可。其中一些函数的定义如下:
主要是定义了移动星系统(
mobile
)和树结构(tree
)的构造与操作,分别处理移动星与树的各种属性和操作。移动星系统(Mobile System)
mobile(left, right)
:- 构造一个由左臂和右臂组成的移动星。左臂和右臂分别通过
arm
构造。 - 函数会检查左臂和右臂是否为合法的臂结构。
- 构造一个由左臂和右臂组成的移动星。左臂和右臂分别通过
is_mobile(m)
:- 检查输入的
m
是否为一个移动星,移动星用列表表示,包含 3 个元素,第一个元素是字符串'mobile'
,第二和第三个元素分别是左臂和右臂。
- 检查输入的
left(m)
:- 返回移动星
m
的左臂,前提是输入的m
必须是合法的移动星。
- 返回移动星
right(m)
:- 返回移动星
m
的右臂,输入的m
也必须是合法的移动星。
- 返回移动星
arm(length, mobile_or_planet)
:- 构造一个臂(力臂),包含臂的长度和末端的移动星或行星。力臂是一个列表,包含
'arm'
标签、长度和末端物体(行星或移动星)。
- 构造一个臂(力臂),包含臂的长度和末端的移动星或行星。力臂是一个列表,包含
is_arm(s)
:- 检查输入的
s
是否是一个臂结构。臂是一个列表,包含 3 个元素,第一个元素为'arm'
,第二个元素为臂的长度,第三个元素为挂在臂末端的物体。
- 检查输入的
length(s)
:- 返回臂
s
的长度,要求输入的s
是一个合法的臂。
- 返回臂
end(s)
:- 返回臂
s
末端挂着的移动星或行星,要求输入的s
是一个合法的臂。
- 返回臂
树结构(Tree Data Abstraction)
tree(label, branches=[])
:- 构造一个树,
label
是树的根节点的值,branches
是树的子树。每个子树必须是一个合法的树结构。
- 构造一个树,
label(tree)
:- 返回树的根节点的标签(值)。
branches(tree)
:- 返回树的子树列表。
is_tree(tree)
:- 检查输入是否是一个合法的树结构。树是一个列表,至少有一个元素,且所有的子树都必须是合法的树。
is_leaf(tree)
:- 判断树是否为叶子节点。叶子节点的特征是没有子树(即
branches(tree)
为空)。
- 判断树是否为叶子节点。叶子节点的特征是没有子树(即
print_tree(t, indent=0)
:打印树的结构,按照树的深度进行缩进,每个节点缩进的空格数量等于该节点的深度乘以 2。
例如:
print_tree(tree(1, [tree(2), tree(3, [tree(4), tree(5)])]))
会打印如下结构:1
2
3
4
5
copy_tree(t)
:- 返回树
t
的一个拷贝。对t
及其所有子树进行递归拷贝。
- 返回树
balanced
就比较好理解了:- 对于一个行星:只需要返回
True
即可。因为它没有围绕它旋转的星球,没有力臂。 - 对于一个
mobile
,我们需要判断它的左右两端和悬挂物是否平衡,所以需要计算力矩。看看两者是否平衡。 - 此外还需要注意它的左右
mobile
是否平衡。
- 对于一个行星:只需要返回
hw05
def hailstone(n): |
总结
得先介绍下yield
关键字的用法和yield from
的语法:
在 Python 中,
yield
是用于生成器函数的关键字。它允许函数在运行时暂停并返回一个值,而保留函数的状态,以便在后续调用时继续执行。这样,yield
可以让函数一次返回一个值,而不是一次性返回所有结果。与返回列表的方式相比,它能够节省内存,因为它只会按需生成值。
yield
用法示例以下是一个简单的例子:
def count_up_to(n):
count = 1
while count <= n:
yield count
count += 1
# 使用生成器
for number in count_up_to(5):
print(number)在上面的例子中,每次调用
yield
时,count_up_to
会暂停,并返回当前的count
值。下一次循环时,函数会从暂停的地方继续执行。
yield
的特性
- 惰性求值:生成器在调用时不会立即计算所有值,而是按需生成值,这有助于节省内存。
- 保留状态:函数调用暂停时会保存局部变量的状态,下次调用时可以继续计算。
- 生成无限序列:利用生成器,可以生成无限序列,比如无限斐波那契数列或无穷循环等。
生成器与返回列表的比较
如果需要返回大量数据,可以用
yield
替代列表返回,从而避免内存消耗问题。例如:
def big_range(n):
for i in range(n):
yield i相比于
return [i for i in range(n)]
,它不会一次性占用大量内存。总结
yield
是 Python 中实现生成器的重要工具,能在内存和性能上带来很大的优化。
yield from
是 Python 3 中引入的一个语法,主要用于简化生成器的嵌套调用。当一个生成器要调用另一个子生成器并直接生成其值时,可以使用yield from
,这样可以减少代码量并提高可读性。yield from
会将子生成器中的值逐个返回给外部调用方。示例:对比
yield
和yield from
假设我们有两个生成器,一个生成数值序列,另一个生成字符序列。我们希望在一个父生成器中使用这两个生成器的值。
使用
yield
def numbers():
yield 1
yield 2
def letters():
yield 'a'
yield 'b'
def combined():
for n in numbers():
yield n
for l in letters():
yield l
# 输出: 1 2 a b
for item in combined():
print(item)这里,
combined
生成器必须使用两个for
循环来分别遍历numbers
和letters
生成的值。使用
yield from
使用
yield from
可以简化嵌套生成器的代码:
def numbers():
yield 1
yield 2
def letters():
yield 'a'
yield 'b'
def combined():
yield from numbers()
yield from letters()
# 输出: 1 2 a b
for item in combined():
print(item)
yield from
语句会直接将numbers
和letters
中的值生成给调用方,因此combined
函数的代码更加简洁。
yield from
的其他功能除了简化生成器嵌套,
yield from
还可以:
- 转发返回值:如果子生成器有返回值(例如在 Python 3.3+ 中,生成器可以使用
return
返回值),yield from
会捕获这个返回值。- 异常传播:
yield from
可以将生成器的异常传播到子生成器,并在适当的时候捕获异常。- 双向通信:
yield from
可以支持生成器之间的双向数据传输,使得子生成器可以接收并返回数据。总结
yield from
是一种将生成器的值和控制权委派给子生成器的简洁方式,能够使嵌套生成器代码更加简明,提高代码可读性。
其实可以简单理解为yield
是一种特殊的return
,但是有一些区别:
可以把
yield
理解为一种特殊的return
。但它们有几个重要的区别:
暂停与恢复:
yield
会暂停函数的执行,将一个值返回给调用者,但保留函数的执行状态(包括局部变量的值和当前执行位置)。下一次调用生成器时,函数会从上次暂停的位置继续执行。而return
则是直接终止函数的执行,不保留任何状态,下次调用时会从头开始。生成器特性:使用
yield
的函数是一个生成器函数,而不是普通的函数。生成器函数会返回一个生成器对象,生成器对象可以被迭代多次(每次获取一个值),直到生成器终止。而普通函数只会返回一个单一的值。多次返回:
yield
可以在函数中使用多次,每次产生一个值,生成器函数可以在整个生命周期中不断地生成新值。return
只能返回一次,返回后函数就彻底结束了。示例对比
yield
的生成器函数:
def count_up_to(n):
count = 1
while count <= n:
yield count
count += 1
# 输出: 1, 2, 3
for number in count_up_to(3):
print(number)在这个例子中,每次调用
yield
都会暂停函数并返回当前的count
,直到循环结束。
return
的普通函数:
def count_up_to(n):
count = 1
while count <= n:
return count # 只会返回1,然后函数结束
count += 1
print(count_up_to(3)) # 输出: 1这里,
return
会立即返回1
并终止函数,不会有机会返回其他的值。总结
虽然
yield
类似于return
,都可以将一个值返回给调用方,但yield
是生成器函数独有的,提供了暂停与恢复的特性,使得生成器能够按需生成多个值。这也是yield
与return
的核心区别。
那前两道题就很好理解了,就不解释了,解释后面两题:
- 观察第一个样例可以发现:
- 如果
n==0
,那么yield []
。 - 否则对多种情况进行分析:可能是
yield 1
,也可能是yield 2
,并且需要对子情况进行递归处理,注意需要将两者拼接起来。
- 如果
def stair_ways(n): |
- 这道题需要注意是打印所有的路径:
- 当遇到目标时,打印目标。
- 对分支进行递归处理,最后还是留意得将他们拼接起来(注意是列表)。
def yield_paths(t, value): |
hw06
passphrase = 'REPLACE_THIS_WITH_PASSPHRASE' |
总结
第一题得补充一下题意。
首先可以学到的是
f-strings
,此外需要留意各个属性的作用:product
:产品名称stock
:数量price
:单价balance
:余额,可以理解为顾客当前购买中已经投了多少钱(售货机在目前这一次买卖中已经收到了多少钱),每次买卖完后需要清 0。
理清头绪后,代码实现就很容易了,这里不解释。
In this question you'll create a vending machine that sells a single product and provides change when needed. 在本题中,您将创建一台自动售货机,用于销售单一产品并在需要时提供零钱。
Implement the
VendingMachine
class, which models a vending machine for one specific product. The methods of aVendingMachine
object return strings to describe the machine’s status and operations. Ensure that your output matches exactly with the strings provided in the doctests, including punctuation and spacing. 实现VendingMachine
类,该类为一种特定产品建模自动售货机。VendingMachine
对象的方法返回描述机器状态和操作的字符串。确保您的输出与文档测试中提供的字符串完全匹配,包括标点符号和空格。You may find Python's formatted string literals, or f-strings useful. A quick example: 您可能会发现 Python 的格式化字符串文字或f 字符串很有用。一个简单的例子:
>>> feeling = 'love'
>>> course = '61A!'
>>> combined_string = f'I {feeling} {course}'
>>> combined_string
'I love 61A!'
class VendingMachine: |
- 适合采取头插法,最初为空,不断从右到左计算,插入新值。
def store_digits(n): |
需要注意下题目要求:
Implement
deep_map_mut(func, s)
, which applies the functionfunc
to each element in the linked lists
. If an element is itself a linked list, recursively applyfunc
to its elements as well. 实现deep_map_mut(func, s)
,它将函数func
应用于链表s
中的每个元素。如果一个元素本身就是一个链表,则也递归地将func
应用于它的元素。Your implementation should mutate the original linked list. Do not create any new linked lists. The function returns
None
. 您的实现应该改变原始链表。不要创建任何新的链接列表。该函数返回None
。- 当列表为空时,直接返回。
- 由于元素可能为链表,所以进行递归处理。
- 当元素不是链表时,先处理元素,后递归处理后面的链表。
def deep_map_mut(func, s): |