作业 1：函数、控制、高阶函数
截止时间：6月30日（周二）23:59
说明
下载 hw01.zip。
提交：完成后，将作业提交到 Gradescope。你可以在截止日期前多次提交；只有最终提交会被评分。请确认你已在 Gradescope 上成功提交代码。 有关提交作业的更多说明，请参见实验 0。
使用 Ok：如果你对使用 Ok 有任何疑问，请参阅此指南。
阅读材料：你可能会发现以下参考资料有用：
评分：作业根据正确性评分。每道错题将使总分减少一分。 本次作业满分为 2 分。
必做题
函数与控制
Q1：A Plus Abs B
Python 的 operator 模块包含双参数函数，如 add 和 sub，对应 Python 的内置算术运算符。例如，add(2, 3) 的结果为 5，就像表达式 2 + 3 一样。
填写以下函数中的空白处，将 a 加上 b 的绝对值，但不调用 abs 函数。除了两个空白处外，你不得修改任何已提供的代码。
def a_plus_abs_b(a, b):
"""Return a+abs(b), but without calling abs.
>>> a_plus_abs_b(2, 3)
5
>>> a_plus_abs_b(2, -3)
5
>>> a_plus_abs_b(-1, 4)
3
>>> a_plus_abs_b(-1, -4)
3
"""
if b < 0:
f = _____
else:
f = _____
return f(a, b)使用 Ok 测试你的代码：
python3 ok -q a_plus_abs_b使用 Ok 运行本地语法检查器（检查你是否修改了两个空白处以外的已提供代码）：
python3 ok -q a_plus_abs_b_syntax_checkQ2：Hailstone
Douglas Hofstadter 的普利策奖获奖著作《哥德尔、艾舍尔、巴赫》提出了以下数学谜题。
- 选取一个正整数
n作为起点。 - 如果
n是偶数，将其除以 2。 - 如果
n是奇数，将其乘以 3 再加 1。 - 重复此过程直到
n为 1。
数字 n 会上下波动，但最终会到达 1（至少对于所有尝试过的数字来说是这样——没有人证明过该序列一定会终止）。类似地，冰雹在大气中上下运动，最终落到地面上。
这个 n 的值序列通常称为冰雹序列。编写一个函数，接受一个参数，形式参数名为 n，打印从 n 开始的冰雹序列，并返回序列的步数：
def hailstone(n):
"""Print the hailstone sequence starting at n and return its
length.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
>>> b = hailstone(1)
1
>>> b
1
"""
"*** YOUR CODE HERE ***"
冰雹序列可能会很长！试试 27。你能找到最长的序列吗？
注意：如果
n == 1初始时就是 1，则序列长度为一步。
提示：如果你看到 4.0 但只想要 4，尝试使用向下取整除法//而不是普通除法/。
使用 Ok 测试你的代码：
python3 ok -q hailstone对冰雹序列感到好奇？看看这篇文章：
- 2019年，在理解冰雹猜想对大多数数字的适用性方面取得了重大进展！
高阶函数
Q3：Product
编写一个名为 product 的函数，返回一个序列前 n 项的乘积。具体来说，product 接受一个整数 n 和 term，term 是一个单参数函数，用于确定一个序列（即 term(i) 给出序列的第 i 项）。
product(n, term) 应返回 term(1) * ... * term(n)。
def product(n, term):
"""Return the product of the first n terms in a sequence.
n: a positive integer
term: a function that takes an index as input and produces a term
>>> product(3, identity) # 1 * 2 * 3
6
>>> product(5, identity) # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square) # 1^2 * 2^2 * 3^2
36
>>> product(5, square) # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple) # 1*3 * 2*3 * 3*3
162
"""
"*** YOUR CODE HERE ***"
使用 Ok 测试你的代码：
python3 ok -q productQ4：Make Repeater
实现函数 make_repeater，它接受一个单参数函数 f 和一个正整数 n。它返回一个单参数函数，使得 make_repeater(f, n)(x) 返回 f(f(...f(x)...)) 的值，其中 f 对 x 应用了 n 次。例如，make_repeater(square, 3)(5) 对 5 平方三次并返回 390625，就像 square(square(square(5))) 一样。
def make_repeater(f, n):
"""Returns the function that computes the nth application of f.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 3)(5) # square(square(square(5)))
390625
"""
"*** YOUR CODE HERE ***"
使用 Ok 测试你的代码：
python3 ok -q make_repeater本地检查你的分数
你可以通过运行以下命令在本地检查本作业每道题的分数：
python3 ok --score这不会提交作业！当你对分数满意后，将作业提交到 Gradescope 以获得分数。
提交作业
通过上传你编辑过的文件到相应的 Gradescope 作业来提交本作业。实验 00有详细说明。
选做题
Q5：Largest Factor
编写一个函数，接受一个大于 1的整数 n，返回小于 n 且能整除 n 的最大整数。
def largest_factor(n):
"""Return the largest factor of n that is smaller than n.
>>> largest_factor(15) # factors are 1, 3, 5
5
>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
40
>>> largest_factor(13) # factors are 1, 13
1
"""
"*** YOUR CODE HERE ***"
提示：要检查
b是否能整除a，使用表达式a % b == 0，可以理解为"a除以b的余数为 0。"
使用 Ok 测试你的代码：
python3 ok -q largest_factorQ6：Accumulate
让我们来看看 product 如何作为一个更通用的函数 accumulate 的实例，我们想要实现这个函数：
def accumulate(fuse, start, n, term):
"""Return the result of fusing together the first n terms in a sequence
and start. The terms to be fused are term(1), term(2), ..., term(n).
The function fuse is a two-argument commutative & associative function.
>>> accumulate(add, 0, 5, identity) # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11 (fuse is never used)
11
>>> accumulate(add, 11, 3, square) # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square) # 2 * 1^2 * 2^2 * 3^2
72
>>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19
"""
"*** YOUR CODE HERE ***"
accumulate 有以下参数：
fuse：一个双参数函数，指定当前项如何与之前累积的项合并start：开始累积的值n：一个非负整数，表示要合并的项数term：一个单参数函数；term(i)是序列的第i项
实现 accumulate，使用 fuse 函数将 term 定义的序列的前 n 项与 start 值合并。
例如，accumulate(add, 11, 3, square) 的结果是
add(11, add(square(1), add(square(2), square(3)))) =
11 + square(1) + square(2) + square(3) =
11 + 1 + 4 + 9 = 25假设
fuse是可交换的，fuse(a, b) == fuse(b, a)，且可结合的，fuse(fuse(a, b), c) == fuse(a, fuse(b, c))。
使用 Ok 测试你的代码：
python3 ok -q accumulate然后，将 summation 和 product 实现为对 accumulate 的单行调用。
重要：
summation_using_accumulate和product_using_accumulate都应该用一行以return开头的代码实现。
def summation_using_accumulate(n, term):
"""Returns the sum: term(1) + ... + term(n), using accumulate.
>>> summation_using_accumulate(5, square) # square(1) + square(2) + ... + square(4) + square(5)
55
>>> summation_using_accumulate(5, triple) # triple(1) + triple(2) + ... + triple(4) + triple(5)
45
>>> # This test checks that the body of the function is just a return statement.
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
['Expr', 'Return']
"""
return ____
def product_using_accumulate(n, term):
"""Returns the product: term(1) * ... * term(n), using accumulate.
>>> product_using_accumulate(4, square) # square(1) * square(2) * square(3) * square()
576
>>> product_using_accumulate(6, triple) # triple(1) * triple(2) * ... * triple(5) * triple(6)
524880
>>> # This test checks that the body of the function is just a return statement.
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
['Expr', 'Return']
"""
return ____
使用 Ok 测试你的代码：
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate