3 formas diferentes de imprimir series de Fibonacci en Java

Dado un número N , necesitamos encontrar la serie de Fibonacci hasta el término N.

La serie de Fibonacci es una serie de elementos donde los dos elementos anteriores se suman para obtener el siguiente elemento, comenzando con 0 y 1. 

Ejemplos: 

Entrada: N = 10 
Salida: 0 1 1 2 3 5 8 13 21 34 
Aquí el primer término de Fibonacci es 0 y el segundo es 1, por lo que el tercer término = primero (o) + segundo (1), etc. y así sucesivamente.

Entrada: N = 15 
Salida: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377  

Método 1: iterativo: inicialice el primer y el segundo número en 0 y 1 . A continuación, imprimimos el primer y segundo número. Luego enviamos el flujo al ciclo while iterativo donde obtenemos el siguiente número sumando los dos números anteriores y simultáneamente intercambiamos el primer número con el segundo y el segundo con el tercero.

A continuación se muestra la implementación del enfoque anterior:

// Java program for the above approach
  
class GFG {
  
    // Function to print N Fibonacci Number
    static void Fibonacci(int N)
    {
        int num1 = 0, num2 = 1;
  
        int counter = 0;
  
        // Iterate till counter is N
        while (counter < N) {
  
            // Print the number
            System.out.print(num1 + " ");
  
            // Swap
            int num3 = num2 + num1;
            num1 = num2;
            num2 = num3;
            counter = counter + 1;
        }
    }
  
    // Driver Code
    public static void main(String args[])
    {
        // Given Number N
        int N = 10;
  
        // Function Call
        Fibonacci(N);
    }
}

0 1 1 2 3 5 8 13 21 34

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Método 2: uso de la recursividad : dado que el número de Fibonacci es la suma de los dos números anteriores. Podemos usar la recursividad según la siguiente condición:

1. Obtenga el número cuya serie de Fibonacci necesita calcularse.
2. Iterar recursivamente del valor N a 1:
   • Caso base: si el valor llamado recursivamente es menor que 1, devuelve 1 la función.
   • Llamada recursiva: si no se cumple el caso base, llame recursivamente a los dos valores anteriores como:
     

     función_recurso(N – 1) + función_recurso(N – 2);

   • Declaración de devolución: en cada llamada recursiva (excepto el caso base), devuelva la función recursiva para los dos valores anteriores como:
     

     función_recurso(N – 1) + función_recurso(N – 2);

A continuación se muestra la implementación del enfoque anterior:

// Recursive implementation of
// Fibonacci Series
  
class GFG {
  
    // Function to print the fibonacci series
    static int fib(int n)
    {
        // Base Case
        if (n <= 1)
            return n;
  
        // Recursive call
        return fib(n - 1)
            + fib(n - 2);
    }
  
    // Driver Code
    public static void
    main(String args[])
    {
        // Given Number N
        int N = 10;
  
        // Print the first N numbers
        for (int i = 0; i < N; i++) {
  
            System.out.print(fib(i) + " ");
        }
    }
}

0 1 1 2 3 5 8 13 21 34

Complejidad temporal: O(2 ^N )  
Espacio auxiliar: O(1)

Método 3: uso de la programación dinámica :

1. Cree una array arr[] de tamaño N .
2. Inicializar arr[0] = 0, arr[1] = 1.
3. Itere sobre [2, N] y actualice la array arr[] como:
   

   arr[i] = arr[i – 2] + arr[i – 1]

4. Imprime el valor de arr[N] .

A continuación se muestra la implementación del enfoque anterior:

// Dynamic Programming approach for
// Fibonacci Series
  
class fibonacci {
  
    // Function to find the fibonacci Series
    static int fib(int n)
    {
  
        // Declare an array to store
        // Fibonacci numbers.
        // 1 extra to handle case, n = 0
        int f[] = new int[n + 2];
  
        int i;
  
        // 0th and 1st number of
        // the series are 0 and 1
        f[0] = 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];
        }
  
        // Nth Fibonacci Number
        return f[n];
    }
  
    public static void
    main(String args[])
    {
        // Given Number N
        int N = 10;
  
        // Print first 10 term
        for (int i = 0; i < N; i++)
            System.out.print(fib(i) + " ");
    }
}

0 1 1 2 3 5 8 13 21 34

Complejidad temporal: O(N)  
Espacio auxiliar: O(N)