code - fibonacci series algorithm

Recursion rapida de fibonacci

Question

Estoy tratando de recordar un algoritmo en la recursión de Fibonacci. El seguimiento:

public int fibonacci(int n)  {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

No es lo que busco porque es codicioso. Esto crecerá exponencialmente (solo observe la secuencia de Fibonacci recursiva de Java , cuanto más grande sea el argumento inicial, más llamadas inútiles se harán).

Probablemente haya algo así como un "cambio de argumento cíclico", en el que la llamada al valor anterior de Fibonacci recuperará el valor en lugar de calcularlo nuevamente.

Answer 1

Debe memorizar el valor calculado para detener el crecimiento exponencial.

1. Solo usa una matriz para almacenar el valor.
2. Comprueba la matriz si ya la has calculado.
3. Si lo encuentra, utilícelo o calcúlelo y guárdelo.

Aquí hay un ejemplo de trabajo para una recursión más rápida usando la memoria.

Cálculo del número de fibonacci

Answer 2

Digamos que quieres tener el noveno número de fib y luego construir una matriz que contenga los números anteriores

int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];

Answer 3

El algoritmo de duedl0r traducido a Swift:

func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
    guard n > 0 else { return 0 }
    if n == 1 { return previous.1 }
    return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}

ejemplo trabajado

fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3

Answer 4

Este tipo de problemas son tipos de recurrencia lineal y se resuelven más rápido a través de una rápida exponenciación de matriz . Aquí está el blogpost que describe este tipo de enfoque de manera concisa.

Answer 5

Puede hacer una versión bastante rápida de Fibonacci recursiva utilizando la memoization (es decir, almacenar los resultados anteriores para evitar volver a calcularlos). por ejemplo, aquí hay una prueba de concepto en Python, donde se usa un diccionario para guardar resultados anteriores:

results = { 0:0, 1:1 }

def memofib(n):
    if n not in results:
        results[n] = memofib(n-1) + memofib(n-2)
    return results[n]

Devuelve rápidamente los valores de entrada que normalmente bloquearían la versión recursiva "normal". Solo tenga en cuenta que un tipo de datos int no será suficiente para obtener grandes resultados, y se recomienda el uso de enteros de precisión arbitrarios.

Una opción totalmente diferente: reescribir esta versión iterativa ...

def iterfib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

... como una función recursiva de cola, llamada loop en mi código:

def tailfib(n):
    return loop(n, 0, 1)

def loop(i, a, b):
    if i == 0:
        return a
    return loop(i-1, b, a+b)

Answer 6

Un buen algoritmo para cálculos rápidos de fibonacci es (en python):

def fib2(n):
    # return (fib(n), fib(n-1))
    if n ==  0: return (0,  1)
    if n == -1: return (1, -1)
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    u_k_s, u_km1_s = u_k**2, u_km1**2  # Can be improved by parallel calls
    u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
    u_2km1 = u_k_s + u_km1_s
    u_2k   = u_2kp1 - u_2km1
    return (u_2kp1, u_2k) if r else (u_2k, u_2km1)

def fib(n):
    k, r = divmod(n, 2) # n=2k+r
    u_k, u_km1 = fib2(k)
    return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)

Si necesita un cálculo muy rápido, haga enlaces a libgmp y use las funciones mpz_fib_ui () o mpz_fib2_ui ().

Answer 7

Un ejemplo en JavaScript que utiliza la recursión y un caché inicializado perezosamente para una mayor eficiencia:

var cache = {};

function fibonacciOf (n) {
  if(n === 0) return 0;
  if(n === 1) return 1;
  var previous = cache[n-1] || fibonacciOf(n-1);
  cache[n-1] = previous;
  return previous + fibonacciOf(n-2);
};

Answer 8

tal vez así:

int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}

Esta función es la cola recursiva. esto significa que podría ser optimizado y ejecutado de manera muy eficiente. De hecho, se optimiza en un bucle simple ..

Answer 9

Encontré un artículo interesante sobre el problema de fibonacci.

aquí el fragmento de código

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

# added iterative version base on C# example
def iterFib(n):
    a = 0
    b = 1
    i=31
    while i>=0:
        d = a * (b * 2 - a)
        e = a * a + b * b
        a = d
        b = e
        if ((n >> i) & 1) != 0:
            c = a + b;
            a = b
            b = c
        i=i-1
    return a