Ricorsione Fast Fibonacci

Question

Sto cercando di richiamare un algoritmo sulla ricorsione di Fibonacci. Il seguente:

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

è non quello che sto cercando perché è avido. Crescerà in modo esponenziale (guardate allo Java recursive Fibonacci sequence - più grande è l'argomento iniziale, più chiamate inutili saranno fatte).

Probabilmente c'è qualcosa di simile a uno "spostamento di argomento ciclico", in cui chiamare il valore precedente di Fibonacci recupererà il valore invece di calcolarlo nuovamente.

Answer 1

forse in questo modo:

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

questa funzione è ricorsiva di coda. questo significa che potrebbe essere ottimizzato ed eseguito in modo molto efficiente. In realtà, viene ottimizzato in un semplice ciclo ..

Answer 2

dire che si desidera avere il numero del n'th fib poi costruire una matrice contenente i numeri precedenti che

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

Answer 3

È possibile fare una versione piuttosto veloce di Fibonacci ricorsiva utilizzando memoization (che significa: memorizzare i risultati precedenti per evitare di ricalcolo). per esempio, ecco una prova di concetto in Python, in cui un dizionario viene utilizzato per il salvataggio dei risultati precedenti:

results = { 0:0, 1:1 } 

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

Si ritorna rapidamente per valori di input che normalmente bloccano la versione ricorsiva "normale". Tieni presente che un tipo di dati int non sarà sufficiente per contenere risultati di grandi dimensioni e si consiglia di utilizzare numeri interi di precisione arbitrari.

Una scelta completamente diversa - riscrivere questa versione iterativa ...

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

... come una funzione ricorsiva in coda, chiamato loop nel mio codice:

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 4

Questo tipo di problemi sono recidive lineari tipi e sono risolti più velocemente tramite esponenziazione a matrice veloce. Ecco lo blogpost che descrive questo tipo di approccio in modo conciso.

Answer 5

I found interesting article about fibonacci problem

qui il frammento di codice

# 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 

Answer 6

Un esempio in JavaScript che usa la ricorsione e una cache pigramente inizializzato per l'efficienza aggiunto:

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 7

algoritmo di duedl0r tradotto 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)) 
} 

lavorato esempio:

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

Answer 8

un buon algoritmo per il calcolo di Fibonacci veloci è (in 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) 

Se avete bisogno di calcolo molto veloce, collega al libgmp e utilizzare mpz_fib_ui() o mpz_fib2_ui() funzioni.

Answer 9

È necessario memorizzare il valore calcolato per arrestare la crescita esponenziale.

1. Basta utilizzare una matrice per memorizzare il valore.
2. Controllare la matrice se è già stata calcolata.
3. Se lo trova, usarlo o altrimenti calcolarlo e memorizzarlo.

Ecco un esempio pratico per la ricorsione più veloce utilizzando la memoria.

Calculating fibonacci number