Page 1 of 1

About efficient algorithms in java??

Posted: Mon Dec 12, 2011 10:49 pm
by WIL
An algorithm for solving exercises such as the Fibonacci series??? :roll: :roll: :roll:

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]