Итерация 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

С массивом для хранения всех промежуточных значений 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) пространство, обратите внимание, что вам не нужно хранить весь массив, а только два предыдущих значения в каждый момент времени. Итак, это можно переписать как в fgb's answer.

Answer 2

Знание Итерация просто отладка для n = 3 или некоторые другие значения (больше 3 поможет лучше). Для математического понимания, whatch это:

. 
. 
. 
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 3

Чтобы записать его в виде итерационного алгоритма, вы можете написать что-то в виде:

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 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); 
}