迭代 n * F(n - 1)+((n - 1) * F(n - 2))

Question

我坚持这个：n * F(n - 1)+((n - 1) * F(n - 2))，我知道如何递归地写这个。但是不知道迭代。

我将其用于递归：

long F_r(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    else if (n > 2)
    {
        return n * F_r(n - 1) + ((n - 1) * F_r(n - 2));
    }
}

有人可以帮我吗？

Answer 1

要理解迭代，只需模拟 n = 3 或其他一些值（大于 3 会更好）。让我们从 n = 0, 1, 2, 3, 4, ... 开始，看看如何计算 F 的值：

F(0) = 1;
F(1) = 1;
F(2) = 1;
F(3) = 3* F(2) + (2* F(1));
     = 3*1 + (2*1);
     = 3 + 2;
     = 5;

F(4) = 4* F(3) + (3* F(2));
     = 4*5 + (3*1);
     = 20 + 3;
     = 23;

以此类推

Answer 2

要把它写成一个迭代算法，你可以这样写：

long F(int n) {
    long a = 1;
    long b = 1;
    long c = 1;
    for(int x = 3; x <= n; x++) {
        a = b;
        b = c;
        c = ...
    }
    return c;
}

Answer 3

用一个数组来存储F的所有中间值：

long F_r(int n)
{
    long[] f = new long [n + 1]; // f[0] is not used
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        f[i] = i * f[i - 1] + ((i - 1) * f[i - 2]); // the formula goes here
    }
    return f[n];
}

如果您只想使用 O(1) space，请注意您不需要存储整个数组，只需存储每个时间点的前两个值。因此，这可以重写为 .

Answer 4

纯属娱乐——求解与Wolfram Alpha的递归关系，得到：

F(n) = (2 * factorial(n + 2) - 5 * subfactorial(n + 2)) / (n + 1)

我们可以计算为：

long F(int n) {
    long p = 1;
    long q = 1;
    for (int i = 1; i <= n + 2; i++) {
        p *= i;
        q = q * i + (1 - (i % 2) * 2);
    }
    return (2 * p - 5 * q) / (n + 1);
}

迭代 n * F(n - 1)+((n - 1) * F(n - 2))

Iteration n * F(n - 1)+((n - 1) * F(n - 2))

iteration

algorithm

recursion