Problem 1: Integration (100pts)

Problem

Calculus might be the hardest course you'll meet in college. In a calculus class, it is common to calculate the definite integral of a continuous function over a closed interval. Simply put, definite integral can be interpreted as the area under the curve of a function over a closed interval. Finding the closed form of integrals of polynomial functions such as \(f(x) = x^2\) might seem simple, but the general idea of definite integral calculation is in fact hard (If you are good at this, you must be one of the 积佬s).

Luckily, we are major in computer science. A prevalent way of doing definite integration via computers is to approximate the result. To be specific, if we want to know the definite integral of function \(f\) over a closed interval \([l, r]\), then we can divide the interval into two smaller intervals, \([l, \frac{l + r}{2}]\) and \([\frac{l + r}{2}, r]\), compute the definite integrals of \(f\) over these two smaller intervals using recursion, and sum them up to obtain the result over \([l, r]\).

When the length of the interval \([l, r]\) is less than a given parameter min_interval, we no longer divide the interval into smaller parts and return immediately the approximation value of the definite integral over \([l, r]\) using a trapezoidal area, \(\frac{f(l) + f(r)}{2} \times (r - l)\).

微积分可能是你在大学里会遇到的最难的课程。 在微积分课上，计算连续函数在一个闭区间上的定积分是很常见的。 简单来说，定积分可以解释为函数在闭区间内曲线下的面积。 找到多项式函数（例如 \(f(x) = x^2\)）积分的闭合形式可能看起来很简单，但定积分计算的一般思路实际上很难（如果你擅长这个，你一定是“积佬”之一）。

幸运的是，我们主修计算机科学。 通过计算机进行定积分计算的一种普遍方法是近似结果。 具体来说，如果想知道函数 \(f\) 在闭区间 \([l, r]\) 上的定积分， 我们可以将区间分成两个更小的区间：\([l, \frac{l + r}{2}]\) 和 \([\frac{l + r}{2}, r]\)，使用递归计算 \(f\) 在这两个更小的区间上的定积分，然后将它们相加得到 \([l, r]\) 上的结果。

当区间 \([l, r]\) 的长度小于给定的参数 min_interval 时，我们不再将区间分成更小的部分，而是立即返回 \([l, r]\) 上定积分的近似值，使用梯形面积公式 \(\frac{f(l) + f(r)}{2} \times (r - l)\)。

Write a recursive function integrate that takes in a function f, a closed interval l, r, and an interval length limit min_interval. integrate returns the definite integral of function f over interval \([l, r]\), with interval limit min_interval. For example, integrate(lambda x: x * x, 1, 3, 0.1) returns the result of integrating the quadratic function \(f(x)=x^2\) over interval \([1, 3]\), with interval length limit 0.1.

编写一个递归函数 integrate，它接受一个函数 f，一个闭区间 l, r，以及一个区间长度限制 min_interval。 integrate 返回函数 f 在区间 \([l, r]\) 上的定积分，以 min_interval 为区间限制。 例如，integrate(lambda x: x * x, 1, 3, 0.1) 返回二次函数 \(f(x)=x^2\) 在区间 \([1, 3]\) 上、区间长度限制为 0.1 的积分结果。

def integrate(f, l, r, min_interval):
    """Return the definite integration of function f over interval
    [l,r], with interval length limit min_interval.

    >>> abs(integrate(lambda x: x * x, 1, 2, 0.01) - (7 / 3)) < 0.001
    True
    >>> abs(integrate(lambda x: x, 1, 2, 0.01) - 1.5) < 0.0001
    True
    >>> from construct_check import check
    >>> # ban while or for loops
    >>> check(HW_SOURCE_FILE, 'integrate', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Hints

Note: Since we are approximating a calculation, the result need not be exactly the same as the closed-form. Instead, a relative-error is introduced to judge how precisely your answer approximates the real result. An implementation is considered correct as long as it differs not much from the actual result.

• Hint1: Use recursion - the tests will fail if you use any loop statements.
• Hint2: There might be multiple ways to do the recursive step, be careful how deep your recursion tree will be!
• Hint3: The video above might help you better understand the problem.

• 由于我们是近似计算，结果不一定需要与闭合形式完全相同。相反，我们引入一个相对误差来判断你的答案对真实结果的近似程度。只要你的实现与实际结果相差不大，就被认为是正确的。

• 使用递归——如果你使用任何循环语句，测试将失败。

• 递归步骤可能有多种方法，请注意你的递归树会有多深！

• 上面的视频可能有助于你更好地理解问题。

Solutions

当 r - l <= min_interval 时，我们达到了区间限制，这可以作为 base case。

根据题意，当区间很大的时候，我们可以将图像从中间切开，分别算左右两部分的面积，开始递归。

def integrate(f, l, r, min_interval):
    if r - l <= min_interval:
        # Base Case: Interval is small enough, use Trapezoidal Rule
        return (r - l) / 2 * (f(l) + f(r))
    else:
        # Recursive Step: Split the interval and sum the results
        m = (l + r) / 2
        return integrate(f, l, m, min_interval) + integrate(f, m, r, min_interval)

---

神秘混淆 by sprite

def integrate(f, l, r, min_interval):
    global a, b
    p = [r, r]
    try:
        a = 1 / int((b := r - l) / min_interval)
    except: 
        a = (a := 1) // (int(b / min_interval).__add__(a))
        return b * (sum([f(i) for i in (p.__setitem__(slice(None, a), [l]) or p)], 0.0)) / (a := a.__lshift__(a))
    return (i := lambda *a: integrate(f, *a, min_interval = min_interval))(l, m := l + b / 2) + i(m, r)