家庭作业 1：函数、控制与高阶函数

hw01.zip

截止时间：6 月 30 日（星期二）晚上 11:59

说明事项

下载 hw01.zip相同，都等于 5。

提交方式： 完成后，请将作业提交到 Gradescope。截止时间前可以多次提交，只有最后一次提交会被评分。请确认代码已成功提交；具体步骤参见实验 0 ，其中有更详细的作业提交说明。

使用 Ok： 如果对 Ok 的使用有任何疑问，请参阅这份指南。

参考阅读： 以下是一些可能有用的参考资料：

评分： 作业根据正确性评分。每个不正确的问题将使总分减少一分。 本次作业满分为 2 分。

必做题目

函数与控制

问题 1：A 加上 B 的绝对值

Python 的 operator 模块包含一些双参数函数，例如 add 和 sub ，它们对应 Python 的内置算术运算符。例如， add(2, 3) 的求值结果为 5，与表达式的结果相同： 2 + 3相同，都等于 5。

补全下面函数中的空格，使它计算 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_check

问题 2：冰雹序列

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，那么序列长度为 1。
Hint: 如果结果显示为 4.0，而你希望得到 4，请尝试使用整除 // 而不是普通除法 /相同，都等于 5。

使用 Ok 测试你的代码：

python3 ok -q hailstone

想进一步了解冰雹序列？可以阅读这篇文章：

2019 年，人们在理解冰雹猜想方面取得了重要进展，帮助人们理解冰雹猜想为何对绝大多数数成立！

高阶函数

问题 3：乘积

编写函数 product ，返回某个序列前 n 项的乘积。具体来说， product 接收整数 n 和 term和一个用于定义序列的单参数函数（也就是说， term(i) 给出序列的第 i项）。 product(n, term) 应返回 term(1) * ... * term(n)相同，都等于 5。

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 product

问题 4：创建重复调用器

实现函数 make_repeater ，它接收单参数函数 f 和正整数 n。它返回一个单参数函数，使得 make_repeater(f, n)(x) 返回 f(f(...f(x)...))的结果，其中 f 被应用 n 次到 x上。例如， make_repeater(square, 3)(5) 把 5 连续平方三次并返回 390625，效果与下面的表达式相同： square(square(square(5)))相同，都等于 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 中提供了详细说明。

可选题

问题 5：最大因数

编写函数，接收一个 n 满足 大于 1 的整数 ，返回小于它且能够整除它的最大整数。 n n相同，都等于 5。

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 ***"

Hint: 要检查 b 是否能整除 a，可以使用表达式 a % b == 0；它可以读作“ a 除以 b 所得余数为 0”。

使用 Ok 测试你的代码：

python3 ok -q largest_factor

问题 6：累积

下面看看函数 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项

Implement accumulate，它把序列的前 n 项 term 与初始 start 值使用 fuse 函数合并。

例如， accumulate(add, 11, 3, square) is

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))相同，都等于 5。

使用 Ok 测试你的代码：

python3 ok -q accumulate

然后，把下面两个函数实现为对 summation 和 product 的单行调用： accumulate相同，都等于 5。

Important: 这两个函数 summation_using_accumulate 和 product_using_accumulate 都必须只用一行代码实现，并以此开头： return相同，都等于 5。

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