介绍

下载 hw02.zip。在存档中,您会找到一个名为 hw02.py 的文件,以及自动评分器 ok 的副本 。

提交:完成后,使用命令python3 ok --submit提交。您可以在截止日期前多次提交,只有最后的提交才会被评分。检查您是否已在 okpy.org 上成功提交代码。有关提交作业的更多说明,请参阅实验 0

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

阅读资料:您可能会发现以下参考资料很有用:第 1.6 节

评分:家庭作业根据正确性评分。每个不正确的问题都会使总分减少一分。教学大纲中规定了家庭作业修复政策。这个作业满分 2 分。

必答问题

几个 doctests 引用了这些函数:

from operator import add, mul

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1

高阶函数

问题1:乘积

高阶函数讲座中的summation(n, term)函数把term(1) + ... + term(n)这些项相加。编写一个名为product的类似函数,返回值为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 one argument to produce the 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

问题2:累计

让我们看一下summationproduct是如何作为我们想要实现的更通用的函数accumulate的实例的:

def accumulate(merger, base, n, term):
    """Return the result of merging the first n terms in a sequence and base.
    The terms to be merged are term(1), term(2), ..., term(n). merger is a
    two-argument commutative 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
    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
    >>> # ((2 * 1^2 * 2) * 2^2 * 2) * 3^2 * 2
    >>> accumulate(lambda x, y: 2 * x * y, 2, 3, square)
    576
    >>> accumulate(lambda x, y: (x + y) % 17, 19, 20, square)
    16
    """
    "*** YOUR CODE HERE ***"

accumulate具有以下参数:

  • termn: 与summationproduct中的参数相同
  • merger:一个有两个参数的函数,指定当前项如何与先前累计的项合并。
  • base:开始累计的值。
    例如,accumulate(add, 11, 3, square)的结果是
11 + square(1) + square(2) + square(3) = 25

注意: 您可以假设merger具有交换性。也就是说,merger(a, b) == merger(b, a)对于所有abc成立。但是,您不能假设merger从固定函数集中选择并硬编码答案。

在实现accumulate后,展示summation以及product是如何定义为对accumulate的函数调用的.

重要提示: 你应该在summation_using_accumulateproduct_using_accumulate的实现中都只有一行代码(应该是一个return语句) ,语法检查将检查这个。

def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square)
    55
    >>> summation_using_accumulate(5, triple)
    45
    """
    "*** YOUR CODE HERE ***"

def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square)
    576
    >>> product_using_accumulate(6, triple)
    524880
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试您的代码:

python3 ok -q accumulate
python3 ok -q summation_using_accumulate
python3 ok -q product_using_accumulate

提交作业时会自动运行语法检查,但您也可以通过运行以下命令直接运行检查。

使用 Ok 来测试您的代码:

python3 ok -q accumulate_syntax_check

提交

确保通过运行以下命令提交此作业:

python3 ok --submit

图一乐的问题

这个问题超出了 61A 的范围。如果您想要一个额外的挑战,您可以尝试它,但这只是一个完全不要求或不推荐的问题。几乎所有的学生都会跳过它,这很好。

如果您有兴趣了解更多相关信息,请随时参加额外话题讲座。

问题3:教堂数字

逻辑学家 Alonzo Church 发明了一种完全使用函数来表示非负整数的系统。目的是表明函数足以描述所有的数论:如果我们有函数,我们不需要假设数字存在,而是我们可以发明它们。

你在这个问题中的目标是重新发现这种称为 Church numerals 的表示。以下是 0 的定义,以及返回比其参数大 1 的函数:

def zero(f):
    return lambda x: x

def successor(n):
    return lambda f: lambda x: f(n(f)(x))

首先,定义函数onetwo,使它们分别具有与successor(zero)successsor(successor(zero))相同的行为,但不要在您的实现中调用successor

接下来,实现一个church_to_int函数将教堂数字自变量转换为常规 Python 整数。

最后,实现对教堂数字执行加法、乘法和求幂的函数:add_churchmul_churchpow_church

def one(f):
    """Church numeral 1: same as successor(zero)"""
    "*** YOUR CODE HERE ***"

def two(f):
    """Church numeral 2: same as successor(successor(zero))"""
    "*** YOUR CODE HERE ***"

three = successor(two)

def church_to_int(n):
    """Convert the Church numeral n to a Python integer.

    >>> church_to_int(zero)
    0
    >>> church_to_int(one)
    1
    >>> church_to_int(two)
    2
    >>> church_to_int(three)
    3
    """
    "*** YOUR CODE HERE ***"

def add_church(m, n):
    """Return the Church numeral for m + n, for Church numerals m and n.

    >>> church_to_int(add_church(two, three))
    5
    """
    "*** YOUR CODE HERE ***"

def mul_church(m, n):
    """Return the Church numeral for m * n, for Church numerals m and n.

    >>> four = successor(three)
    >>> church_to_int(mul_church(two, three))
    6
    >>> church_to_int(mul_church(three, four))
    12
    """
    "*** YOUR CODE HERE ***"

def pow_church(m, n):
    """Return the Church numeral m ** n, for Church numerals m and n.

    >>> church_to_int(pow_church(two, three))
    8
    >>> church_to_int(pow_church(three, two))
    9
    """
    "*** YOUR CODE HERE ***"

使用 Ok 来测试您的代码:

python3 ok -q church_to_int
python3 ok -q add_church
python3 ok -q mul_church
python3 ok -q pow_church
最后修改日期: 2022年6月7日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。