Che cos’è una soluzione non ricorsiva per la sequenza simile a Fibonacci in Java?

Dato questo pseudo codice di una funzione

f(0) = 1; f(1) = 3; f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2. 

C’è un modo non ricorsivo per farlo?

Sì, tutti gli algoritmi ricorsivi possono essere convertiti in iterativi. La soluzione ricorsiva al tuo problema è qualcosa di simile (pseudo-codice):

 def f(n): if n == 0: return 1 if n == 1: return 3 return 3 * f(n-1) - f(n-2) 

Dal momento che devi solo ricordare i due termini precedenti per calcolare quello corrente, puoi usare qualcosa come il seguente pseudo-codice:

 def f(n): if n == 0: return 1 if n == 1: return 3 grandparent = 1 parent = 3 for i = 2 to n: me = 3 * parent - grandparent grandparent = parent parent = me return me 

Questo semplicemente gestisce la condizione di terminazione “ricorsiva” prima quindi itera dove normalmente si chiamerebbe. Ad ogni iterazione, si calcola il termine corrente, quindi si ruotano i termini attraverso il nonno e il genitore.

Non è necessario mantenere il nonno in giro una volta calcasting l’iterazione corrente poiché non è più utilizzata.

In effetti, si potrebbe dire che la soluzione iterativa è migliore (dal punto di vista delle prestazioni) poiché i termini non vengono ricalcolati così come sono nella soluzione ricorsiva. La soluzione ricorsiva ha tuttavia una certa eleganza (le soluzioni ricorsive generalmente lo fanno).


Ovviamente, come la sequenza di Fibonacci, quel valore che calcoli aumenta molto velocemente, quindi, se vuoi la soluzione più rapida (dovresti controllare tutte le dichiarazioni di performance, inclusa la mia), una tabella di ricerca precalcasting potrebbe essere la strada da percorrere.

Utilizzando il seguente codice Java per creare una tabella di valori lunghi (che while condizione è solo un trucco subdolo per catturare l’overflow, che è il punto in cui è ansible interrompere la costruzione della matrice):

 class GenLookup { public static void main(String args[]) { long a = 1, b = 3, c; System.out.print ("long lookup[] = { " + a + "L, " + b + "L"); c = 3 * b - a; while ((c + a) / 3 == b) { System.out.print (", " + c + "L"); a = b; b = c; c = 3 * b - a; } System.out.println (" };"); } } 

ti fornisce una definizione di array che puoi semplicemente colbind a una funzione di ricerca, come nell’esempio seguente:

 public static long fn (int n) { long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L, 17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L, 14930352L, 39088169L, 102334155L, 267914296L, 701408733L, 1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L, 225851433717L, 591286729879L, 1548008755920L, 4052739537881L, 10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L, 498454011879264L, 1304969544928657L, 3416454622906707L, 8944394323791464L, 23416728348467685L, 61305790721611591L, 160500643816367088L, 420196140727489673L, 1100087778366101931L, 2880067194370816120L, 7540113804746346429L }; if ((n < 1) || (n > lookup.length)) return -1L; return lookup[n-1]; } 

È interessante notare come WolframAlpha abbia un approccio formulato che non usa nemmeno l’iterazione. Se vai al loro sito e inserisci f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2) , otterrai la formula:

inserisci la descrizione dell'immagine qui

Sfortunatamente, potrebbe non essere veloce quanto l’iterazione, dato il numero limitato di valori di input che si traducono in qualcosa che può essere contenuto in un Java long , poiché utilizza un punto mobile. È quasi certamente (ma, ancora una volta, dovresti controllarlo) più lentamente di una tabella di ricerca.

Ed è probabilmente perfetto nel mondo della matematica in cui i limiti del mondo reale come lo storage non infinito non entrano in gioco ma, probabilmente a causa dei limiti della precisione IEEE, si rompono a valori più alti di n .

Le seguenti funzioni sono l’equivalente di tale espressione e la soluzione di ricerca:

 class CheckWolf { public static long fn2 (int n) { return (long)( (5.0 - 3.0 * Math.sqrt(5.0)) * Math.pow(((3.0 - Math.sqrt(5.0)) / 2.0), n-1) + (5.0 + 3.0 * Math.sqrt(5.0)) * Math.pow(((3.0 + Math.sqrt(5.0)) / 2.0), n-1) ) / 10; } public static long fn (int n) { long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L, 17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L, 14930352L, 39088169L, 102334155L, 267914296L, 701408733L, 1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L, 225851433717L, 591286729879L, 1548008755920L, 4052739537881L, 10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L, 498454011879264L, 1304969544928657L, 3416454622906707L, 8944394323791464L, 23416728348467685L, 61305790721611591L, 160500643816367088L, 420196140727489673L, 1100087778366101931L, 2880067194370816120L, 7540113804746346429L }; if ((n < 1) || (n > lookup.length)) return -1L; return lookup[n-1]; } 

Ora abbiamo bisogno di una linea principale per confrontarli:

  public static void main(String args[]) { for (int i = 1; i < 50; i++) if (fn(i) != fn2(i)) System.out.println ("BAD: " + i + ": " + fn(i) + ", " + fn2(i) + " (" + Math.abs(fn(i) - fn2(i)) + ")"); else System.out.println ("GOOD: " + i + ": " + fn(i) + ", " + fn2(i)); } } 

Questo produrrà:

 GOOD: 1: 1, 1 GOOD: 2: 3, 3 GOOD: 3: 8, 8 GOOD: 4: 21, 21 GOOD: 5: 55, 55 GOOD: 6: 144, 144 GOOD: 7: 377, 377 GOOD: 8: 987, 987 GOOD: 9: 2584, 2584 GOOD: 10: 6765, 6765 GOOD: 11: 17711, 17711 GOOD: 12: 46368, 46368 GOOD: 13: 121393, 121393 GOOD: 14: 317811, 317811 GOOD: 15: 832040, 832040 GOOD: 16: 2178309, 2178309 GOOD: 17: 5702887, 5702887 GOOD: 18: 14930352, 14930352 GOOD: 19: 39088169, 39088169 GOOD: 20: 102334155, 102334155 GOOD: 21: 267914296, 267914296 GOOD: 22: 701408733, 701408733 GOOD: 23: 1836311903, 1836311903 GOOD: 24: 4807526976, 4807526976 GOOD: 25: 12586269025, 12586269025 

Guardando bene fino a qui, un po 'di più:

 GOOD: 26: 32951280099, 32951280099 GOOD: 27: 86267571272, 86267571272 GOOD: 28: 225851433717, 225851433717 GOOD: 29: 591286729879, 591286729879 GOOD: 30: 1548008755920, 1548008755920 GOOD: 31: 4052739537881, 4052739537881 GOOD: 32: 10610209857723, 10610209857723 GOOD: 33: 27777890035288, 27777890035288 GOOD: 34: 72723460248141, 72723460248141 GOOD: 35: 190392490709135, 190392490709135 GOOD: 36: 498454011879264, 498454011879264 

Ma poi qualcosa inizia ad andare storto:

 BAD: 37: 1304969544928657, 1304969544928658 (1) BAD: 38: 3416454622906707, 3416454622906709 (2) BAD: 39: 8944394323791464, 8944394323791472 (8) BAD: 40: 23416728348467685, 23416728348467705 (20) BAD: 41: 61305790721611591, 61305790721611648 (57) BAD: 42: 160500643816367088, 160500643816367232 (144) BAD: 43: 420196140727489673, 420196140727490048 (375) 

Il fatto che quanto sopra sia allettantemente vicino e che il numero di cifre nell'errore sia proporzionale al numero di cifre nel risultato, indica che probabilmente si tratta di un problema di perdita di precisione.

Dopo questo punto, la funzione formulaica inizia a restituire il massimo valore lungo:

 BAD: 44: 1100087778366101931, 922337203685477580 (177750574680624351) BAD: 45: 2880067194370816120, 922337203685477580 (1957729990685338540) BAD: 46: 7540113804746346429, 922337203685477580 (6617776601060868849) 

E poi la nostra funzione di ricerca si interrompe anche perché i numeri sono troppo grandi per un lungo:

 BAD: 47: -1, 922337203685477580 (922337203685477581) BAD: 48: -1, 922337203685477580 (922337203685477581) BAD: 49: -1, 922337203685477580 (922337203685477581) 

Le risposte qui sono corrette, ma funzionano in O (n), mentre puoi farlo in O (log n), esponenzialmente più veloce. Osservalo

 [f(n) ] = [3 -1] [f(n-1)] [f(n-1)] [1 0] [f(n-2)] 

Sia v n il vettore [f (n), f (n-1)] e A la matrice come sopra, così ottieni v n = A v n-1 , quindi v n = A n-1 v 1 . Calcola (n-1) -th potenza della matrice A usando l’ esponenziazione binaria e moltiplicala per v 1 . Per maggiori informazioni sulle recidive lineari vedi qui .

Se la tua domanda riguarda la possibilità di trovare una definizione equivalente non ricorsiva della funzione, dovresti cercare le proprietà della sequenza di Fibonacci .

La sequenza può essere trovata scrivendo il Fibonacci (senza i primi 2 numeri) e rimuovendo ogni 2 ° numero: 1, 3, 8, 21, 55, 144, …

 sqrt5 = sqrt(5) phi = ( 1 + sqrt5 ) / 2 fibonacci(n) = round( power( phi, n ) / sqrt5 ) f(n) = fibonacci( 2*n + 2 ) 

È semplice, in Java la soluzione si presenta così:

 public int f(int n) { int tmp; int a = 3; int b = 1; for (int i = 0; i < n; i++) { tmp = a; a = 3 * a - b; b = tmp; } return b; } 

Tutte le soluzioni ricorsive possono essere trasformate in soluzioni iterative (è vero anche il contrario, vedi questo post ), anche se è più facile se la soluzione ricorsiva è in forma ricorsiva in coda.

L'algoritmo di cui sopra può essere inteso come una soluzione di programmazione dynamic alla ricorsione originale, è molto efficiente poiché ha solo bisogno di salvare i due valori precedenti in ogni punto dell'iterazione.

[Oops, ho pensato che fosse una domanda Perl. Tuttavia, il codice dovrebbe essere sufficientemente leggibile per uno sviluppatore Java. ]

In realtà questo è solo spostando la ricorsione in terra utente, ma è ansible utilizzare:

 sub f { my ($n) = @_; my @f = (1,3); $f[$_] = 3 * $f[$_-1]- $f[$_-2] for 2 .. $n; return $f[$n]; } 

Certo, questo richiede il caching. Non è necessario ricalcolare i valori che già conosciamo.

 my @f = (1,3); sub f { my ($n) = @_; $f[$_] = 3 * $f[$_-1]- $f[$_-2] for @f .. $n; return $f[$n]; } 

La funzione è definita in termini di se stessa, quindi in un certo senso qualsiasi implementazione è ricorsiva, a meno che qualche matematico arrivi e ci dice che f(n) possa essere valutato senza valutare f(n-1) f(n-2) . Come altri hanno mostrato, c’è un modo per implementarlo in una funzione Java che non chiama se stessa.

 def func(n): f= array(n+1) f[0]=1 f[1]=3 for i in 2:n : f[i] = 3*f[i-1]-f[i-2] return f[n] 

La sequenza di numeri della serie di Fibonacci inizia come: 0,1,1,2,3,5,8,13,21,34,55 ….

questo può essere definito da una semplice relazione di ricorrenza F (n) = F (n-1) + F (n-2) per n> 1 e due condizioni iniziali, F (0) = 1 e F (1) = 1

Algoritmo Fibonacci

// Calcola il n ° numero di Fibonacci

// Input: un numero intero non negativo

// Output: l’ennesimo numero di Fibonacci

 1. Begin Fibo 2. integer n, i; 3. if n<=1 then 4. return n; 5. else 6. F(0)<-0; F(1)<-1; 7. for i<-2 to n do 8. F(i)<-F(i-1)+F(i-2); 9. F(i-2)=F(i-2); 10. F(i-1)=F(i); 11. done 12. end if 13. end Fibo 

Qui è semplicemente una funzione con una linea di codice minima e massima flessibilità.

Puoi aggiungere qualsiasi “valore iniziale” e qualsiasi altra “funzione” ricorsiva che desideri semplicemente.

 def fib(n): fibs = [1, 3] # <-- your initial values here if n == 1: return fibs[0] if n == 2: return fibs[:1] for i in range(2, n): fibs.append(3*fibs[-1] - fibs[-2]) # <-- your function here return fibs 

E il risultato è:

 n=10 print(fib(n)) [1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765] 

Come richiesto da @paxdiablo, sto facendo una risposta. È una relazione di ricorrenza e può essere risolta in modo non ricorsivo, simile alla sequenza di fibonacci menzionata in un’altra risposta. Risulta essere (notazione Python).

 def f(n): return int((13**0.5-3)/(2*13**0.5)*((3-13**0.5)/2)**n + (0.5+3/(2*13**0.5))*((3+13**0.5)/2)**n) 

Tuttavia, questo forumula probabilmente non funziona per n grandi, a causa della precisione del float limitata. La data versione di Python fallisce per n = 30:

 >>> print ([f(n) == 3 * f(n-1) + f(n-2) for n in range(2, 30)]) [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False] >>> print([f(n) for n in range(30)]) [1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090, 93679022931153, 309400794703549, 1021881407041801] 

Attenzione: ho usato un “+” anziché un “-“, quindi la formula è sbagliata. Vedi i commenti.