Cómo calcular esto recursivamente y luego iterativamente

Answer 1

De la misma manera que resuelves una ecuación diferencial.

Suponga que [matemáticas] f (n) = a \ cdot f (n-1) [/ matemáticas]

La segunda ecuación ahora establece que [matemáticas] a ^ 3 – a ^ 2 – 2a – 3 = 0 [/ matemáticas]

Esta ecuación proporciona tres valores posibles para a: [matemáticas] a_1, a_2 [/ matemáticas] y [matemáticas] a_3 [/ matemáticas].

ahora la f (n) que necesita es igual a [matemáticas] b_1 \ cdot a_1 ^ n + b_2 \ cdot a_2 ^ n
+ b_3 \ cdot a_3 ^ n [/ math] con [math] b_1, b_2 [/ math] y [math] b_3 [/ math] tres constantes fijas para que [math] f (n) = n [/ math] para n <3.

Oh, espera … esto es informática, no matemáticas.

int tribbonaci(int a)
{
if(a<3) return a;
int i=a-2,x0=0,x1=1,x2=2;
while(i>0)
{
int res = x2+x1*2+x0*3;
x0 = x1;
x1 = x2;
x2 = res;
i--;
}
return x2;
}


Larga historia corta : quédate con la iteración.

EDITAR: errores eliminados.

Answer 2

El método recursivo es muy fácil y es significativamente más confiable que el método iterativo.

público estático doble f (doble x) {
retorno x <3? X
: f (x – 1) + (2 * f (x – 2)) + (3 * f (x – 3));
}

El método iterativo es más difícil de implementar.

Dado que la recursión es solo una expansión sintácticamente sucinta, para la función anterior, podemos representar [matemáticas] f (5) [/ matemáticas] como [matemáticas] f (4) + 2f (3) + 3f (2) [/ matemáticas], y esta expansión continúa sin cesar.

Podríamos usar tuplas para representar las funciones y sus coeficientes, pero como se trata de Java, necesitaremos una clase dedicada.

Clase privada estática Función {
multiplicador doble público, valor;

Función pública (doble multiplicador, doble valor) {
this.multiplier = multiplicador;
this.value = value;
}
}

Ahora usamos este código para expandir iterativamente la función:

público estático doble f (doble x) {
si (x <3) devuelve x;

suma doble = 0;

// Ahora necesitamos expandir la lista.
Lista funciones = nueva ArrayList ();
functions.add (nueva función (1, x));

while (needsRepeat (funciones))
funciones = expandir (funciones);

para (Función f: funciones)
sum + = f.multiplier * f.value;

suma de retorno;
}

public static List expand (List current) {
for (int i = 0; i Función f = current.get (i);
if (f.value> = 3) {
current.set (i, nueva función (f.multiplier, f.value – 1));
current.add (nueva función (2 * f.multiplier, f.value – 2));
current.add (nueva función (3 * f.multiplier, f.value – 3));
corriente de retorno; // No queremos problemas de concurrencia.
}
}

corriente de retorno;
}

public static boolean needsRepeat (Comprobación de Lista) {
para (Función f: verificar)
if (valor f> = 3)
volver verdadero;

falso retorno;
}

Larga historia corta : quédate con la recursividad.

(Editar # 10,000: no puedo hacer que LaTeX funcione, así que he eliminado la mayor parte).