Page 1 of 1
About efficient algorithms in java??
Posted: Mon Dec 12, 2011 10:49 pm
by WIL
Re: About efficient algorithms in java??
Posted: Thu Jan 12, 2012 1:32 am
by jelara
Well, Fibonacci can be solved in many ways (with recursion, iteration, precalculation, etc). One of the fastests I know (if not the fastest), is to use the closed solution of the recurrence. That can be implemented in many languages.
Re: About efficient algorithms in java??
Posted: Mon Nov 17, 2014 1:38 pm
by luismawolf
package fibonacci;
import java.util.Scanner;
public class Fibonacci {
static int fibonacci(int numero) {
if ((numero == 0) || (numero == 1)) {
return 1;
} else {
return fibonacci(numero - 1) + fibonacci(numero - 2);
}
}
public static void main(String[] args) {
Scanner miScanner = new Scanner(System.in);
System.out.println("Entre un número: ");
int prueba = miScanner.nextInt();
System.out.println(fibonacci(prueba));
}
}
Re: About efficient algorithms in java??
Posted: Wed Oct 28, 2015 3:32 pm
by isaac
La sucesion de Fibonnaci, si se necesitan varios términos de ella, es mejor calcularla de la forma F[n] = F[n-1] + F[n-2], pero cuando se necesita un término en particular, se puede calcular en O(log2 N) utilizando propiedades de las matrices. La matriz:
0 1
1 1
elevada a la N, da como resultado
F[N-2] F[N-1]
F[N-1] F[N]
Esto se puede demostrar por induccion y de ahi se derivan las propiedades siguientes:
1-> F[n]^2 + F[n+1]^2 = F[2n + 1]
2-> F[n+1] *( F[n] + F[n+2] ) = F[2n + 2]
