Skip to content

Problem 3: Elementary Functions (200pts)

Problem

In this problem, you will construct some complex functions using elementary functions as basic building blocks.

Specifically, the following elementary functions are provided for you:

在这个问题中，您将使用基本函数作为构建块来构造一些复杂函数。

具体来说，为您提供了以下基本函数：

def sum(n, f):
    """
    Return the sum of the first n terms in the sequence defined by f.
    The terms to be summed are f(0), f(1), f(2), ..., f(n).

    >>> sum(5, lambda x: x * x)
    55
    >>> sum(3, lambda x: x + 1)
    10
    >>> sum(5, lambda x: 2**x)
    63
    """
    result = 0
    while n >= 0:
        result += f(n)
        n -= 1
    return result


def product(n, f):
    """
    Return the product of the first n terms in the sequence defined by f.
    The terms to be multiplied are f(0), f(1), f(2), ..., f(n).

    >>> product(4, lambda x: x)
    0
    >>> product(3, lambda x: x + 2)
    120
    >>> product(3, lambda x: x * x + 1)
    100
    """
    result = 1
    while n >= 0:
        result *= f(n)
        n -= 1
    return result


def trigger(n):
    """
    Return 0 if n is 0, and 1 otherwise.

    >>> trigger(0)
    0
    >>> trigger(4)
    1
    """
    if n == 0:
        return 0
    else:
        return 1

By composing these elementary functions, we can define more complex functions.

Let's start with product_of_trigger.

The function computes the product trigger(f(0)) * trigger(f(1)) * ... * trigger(f(n)), which could be constructed from the two function product and trigger.

通过组合这些基本函数，我们可以定义更复杂的函数。

让我们从 product_of_trigger 开始。

该函数计算 product trigger(f(0)) * trigger(f(1)) * ... * trigger(f(n))，它可以由两个函数 product 和 trigger 构造出来。

def product_of_trigger(n, f):
    """
    Return the product of trigger(f(0)), trigger(f(1)), trigger(f(2)), ..., trigger(f(n)).

    >>> product_of_trigger(0, lambda x: x * x - 9)
    1
    >>> product_of_trigger(1, lambda x: x * x - 9)
    1
    >>> product_of_trigger(2, lambda x: x * x - 9)
    1
    >>> product_of_trigger(3, lambda x: x * x - 9)
    0
    """
    return _____

We can further utilize product_of_trigger to define a more complex function minimal_root. minimal_root(n, f) returns the smallest integer k such that 0 <= k <= n and f(k) == 0. If no such k exists, return n + 1.

我们可以进一步利用 product_of_trigger 来定义一个更复杂的函数 minimal_root。minimal_root(n, f) 返回满足条件 0 <= k <= n 且 f(k) == 0 的最小整数 k。如果不存在这样的 k，则返回 n + 1。

def minimal_root(n, f):
    """
    Return the smallest k such that k is a root of f with 0 <= k <= n.
    If no such k exists, return n + 1

    >>> minimal_root(6, lambda x: x) # f(0) = 0
    0
    >>> minimal_root(6, lambda x: x * x - 5 * x + 6) # f(2) = 0, f(3) = 0
    2
    >>> minimal_root(6, lambda x: x * x + 1) # no roots
    7
    """
    return _____

Your solutions to the aboving problems should be a one-line function call expression

您对上述问题的解决方案应该是一个单行函数调用表达式

Hints

In this problem, all input n are non-negative integers.

Hint: In your solutions, you shall only use lambda expressions and function calls of sum, product, and trigger. Specifically, you can use function call of product_of_trigger in your implementation of minimal_root.

  • 在本问题中，所有输入 \(n\) 都是非负整数。

  • 在您的解决方案中，您只能使用 lambda 表达式以及对 sum、product 和 trigger 的函数调用。具体来说，在 minimal_root 的实现中，您可以使用 product_of_trigger 的函数调用。

  • product_of_trigger 函数应该调用 product 和 trigger 函数

  • 可以思考一下，在 minimal_root 函数中，有关的 product_of_trigger 会有什么变化，什么时候会变成0

  • minimal_root 函数应该调用 product_of_trigger 和 sum 函数

Solutions

product 函数中的 f(x) 在 product_of_trigger 中应该为 trigger(f(x))，可以用 lambda 表示：

def product_of_trigger(n, f):
    return product(n, lambda x: trigger(f(x)))

我们假设 f(k) == 0，当 x < k 时有 trigger(f(x)) == 1，因此 product_of_trigger(x, f) == 1

当 x >= k 时，由于 trigger(f(k)) == 0，此时 product_of_trigger(x, f) == 0

此时我们可以发现，存在 k 个 x 使得 product_of_trigger(x, f) == 1，剩余的 product_of_trigger(x, f) == 0。

可以猜测 k 等于所有 product_of_trigger(x, f) 的和。编写函数并验证，我们发现没有根时输出正好为 n + 1。

def minimal_root(n, f):
    return sum(n, lambda x: product_of_trigger(x, f))

注意 product_of_trigger 的第二个参数为一个函数，不要把 f(x) 传进去啦