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.
Post Reply
User avatar
WIL
Posts: 11
Joined: 7 years ago
Gender: Male

About efficient algorithms in java??

Post by WIL » 7 years ago

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


I'm interesting in learn!!!

User avatar
jelara
Posts: 37
Joined: 7 years ago
Location: Guadalajara, Mexico
Gender: Male
Mexico

Re: About efficient algorithms in java??

Post by jelara » 6 years ago

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: 4 years ago
Gender: Male

Re: About efficient algorithms in java??

Post by luismawolf » 4 years ago

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: 3 years ago
Gender: None specified

Re: About efficient algorithms in java??

Post by isaac » 3 years ago

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]

Post Reply

Return to “Java”