En términos matemáticos, la secuencia Fn de los números de Fibonacci está definida por la relación de recurrencia
Fn = Fn-1 + Fn-2
con valores semilla
F0 = 0 and F1 = 1.
Método 1 (Usar recursividad)
// Fibonacci Series using Recursion
class Fibonacci {
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra */
Producción:
34
Método 2 (usar programación dinámica)
// Fibonacci Series using Dynamic Programming
class Fibonacci {
static int fib(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[] = new int[n + 1];
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
if (n > 0) {
f[1] = 1;
for (i = 2; i <= n; i++) {
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i - 1] + f[i - 2];
}
}
return f[n];
}
public static void main(String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra
and improved by MichaelJoshuaRamos */
Producción:
34
Método 3 (Usar Programación Dinámica con Optimización de Espacio)
// Java program for Fibonacci Series using Space
// Optimized Method
class Fibonacci {
static int fib(int n)
{
int a = 0, b = 1, c;
if (n == 0)
return a;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
public static void main(String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
// This code is contributed by Mihir Joshi
Producción:
34
Método 4 (Divide y vencerás)
class Fibonacci {
static int fib(int n)
{
int F[][] = new int[][] { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
/* Helper function that multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][])
{
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is designed only for fib() and won't work as general
power function */
static void power(int F[][], int n)
{
int i;
int M[][] = new int[][] { { 1, 1 }, { 1, 0 } };
// n - 1 times multiply the matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
/* Driver program to test above function */
public static void main(String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra */
Producción:
34
Método 5 (Divide y vencerás)
// Fibonacci Series using Optimized Method
class Fibonacci {
/* function that returns nth Fibonacci number */
static int fib(int n)
{
int F[][] = new int[][] { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
static void multiply(int F[][], int M[][])
{
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Optimized version of power() in method 4 */
static void power(int F[][], int n)
{
if (n == 0 || n == 1)
return;
int M[][] = new int[][] { { 1, 1 }, { 1, 0 } };
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
/* Driver program to test above function */
public static void main(String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra */
Producción:
34
¡ Consulte el artículo completo sobre Programa para números de Fibonacci para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA