通过反向迭代法求解 T(n)=T(n-1)+2n

Question

谁能帮我解决这个问题。 T(1)=5, T(n)=T(n-1)+2n 如果有步骤说明就好了。

Answer 1

要计算 T 的每个下一个值，您必须知道前一个值。这就是 "iterative" 的意思。您必须经历一个循环，在计算 T(n) 的每个步骤中，从 T(2)、T(3) 等开始，直到到达某个目标元素。变量 T 应该是一个数组。

Answer 2

迭代方法

你可以通过简单的迭代来解决这个问题 (Java):

public static int T (int n) {
    if(n <= 0) {
        throw new IllegalArgumentException("n must be larger or equal to one.");
    }
    int result = 5;
    for(int i = 2; i <= n; i++) {
        result = result + 2*i;
    }
    return result;
}

jDoodle

程序的工作原理如下：首先我们执行边界检查：如果n小于或等于零，则结果未定义。接下来我们将 5 分配给 result。现在在我们进入for循环之前，result等于T(n)，接下来对于for循环中的每一次迭代，我们计算T(i) 基于 T(i-1)（等于当时的 result）。由于 for 循环执行迭代直到（包括）n，在迭代结束时 result 等于 T(n ).

恒定时间方法

基于迭代的情况，我们可以简化这个somation using WolframAlpha:

因此我们可以简化我们的程序，使其在恒定时间内运行：

public static int T (int n) {
    if(n <= 0) {
        throw new IllegalArgumentException("n must be larger or equal to one.");
    }
    return n*n+n+3;
}