About efficient algorithms in java??

Discussion on Java at the COJ. This is the place to clear your doubts about these languages, and to share with the community the new things you learn about them.
User avatar
WIL
Posts: 11
Joined: Thu Dec 08, 2011 12:02 pm
Gender: Male

About efficient algorithms in java??

Postby WIL » Mon Dec 12, 2011 10:49 pm

An algorithm for solving exercises such as the Fibonacci series??? :roll: :roll: :roll:


I'm interesting in learn!!!

User avatar
jelara
Posts: 37
Joined: Mon Nov 07, 2011 9:00 pm
Location: Universidad de las Ciencias Informáticas (UCi)
Gender: None specified

Re: About efficient algorithms in java??

Postby jelara » Thu Jan 12, 2012 1:32 am

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.

User avatar
luismawolf
Posts: 30
Joined: Thu Nov 13, 2014 3:12 pm
Gender: Male

Re: About efficient algorithms in java??

Postby luismawolf » Mon Nov 17, 2014 1:38 pm

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));
}

}

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: About efficient algorithms in java??

Postby isaac » Wed Oct 28, 2015 3:32 pm

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]


Return to “Java”

Who is online

Users browsing this forum: No registered users and 1 guest