Programa Java para encontrar la suma de los números de serie de Fibonacci de los primeros índices N pares

Para un entero positivo dado N, el propósito es encontrar el valor de F2 + F4 + F6 +…………+ F2n hasta el número N. Donde Fi indica el i-ésimo número de Fibonacci.

La serie de Fibonacci son los números en la secuencia de enteros dada a continuación.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……

Ejemplos:

Input: n = 4
Output: 33
N = 4, So here the fibonacci series will be produced from 0th term till 8th term:
0, 1, 1, 2, 3, 5, 8, 13, 21
Sum of numbers at even indexes = 0 + 1 + 3 + 8 + 21 = 33.

Input: n = 7
Output: 609
0 + 1 + 3 + 8 + 21 + 55 + 144 + 377 = 609.

Enfoque 1:

// Java Program to find even sum of
// fibonacci Series Till number N
import java.io.*;
  
class geeksforgeeks {
  
    // Computing the value of first fibonacci series
    // and storing the sum of even indexed numbers
    static int Fib_Even_Sum(int N)
    {
        if (N <= 0)
            return 0;
  
        int fib[] = new int[2 * N + 1];
        fib[0] = 0;
        fib[1] = 1;
  
        // Initializing the sum
        int s = 0;
  
        // Adding remaining numbers
        for (int j = 2; j <= 2 * N; j++) {
            fib[j] = fib[j - 1] + fib[j - 2];
  
            // Only considering even indexes
            if (j % 2 == 0)
                s += fib[j];
        }
  
        return s;
    }
  
    // The Driver code
    public static void main(String[] args)
    {
        int N = 11;
  
        // Prints the sum of even-indexed numbers
        System.out.println(
            "Even sum of fibonacci series till number " + N
            + " is: " + +Fib_Even_Sum(N));
    }
}

Even sum of fibonacci series till number 11 is: 28656

Complejidad de tiempo: O(n)

Enfoque 2:

Se puede ver claramente que la suma requerida se puede obtener así:
2 ( F ₂ + F ₄ + F ₆ +………+ F _2n ) = (F ₁ + F ₂ + F ₃ + F ₄ +………+ F _2n ) – (F ₁ – F ₂ + F ₃ – F ₄ +………+ F _2n )

Ahora el primer término se puede obtener si ponemos 2n en lugar de n en la fórmula dada aquí .

Así F ₁ + F ₂ + F ₃ + F ₄ +………+ F _2n = F _2n+2 – 1.

El segundo término también se puede encontrar si ponemos 2n en lugar de n en la fórmula dada aquí

Así, F ₁ – F ₂ + F ₃ – F ₄ +………- F _2n = 1 + (-1) ²ⁿ⁺¹ F _2n-1 = 1 – F _2n-1 .

Entonces, 2 ( F ₂ + F ₄ + F ₆ +………+ F _2n )
= F _2n+2 – 1 – 1 + F _2n-1
= F _2n+2 + F _2n-1 – 2
= F _2n + F _2n+1 + F _2n+1 – F _2n – 2
= 2 ( F _2n+1 -1)
Por lo tanto, ( F ₂ + F ₄ + F ₆ +………+ F _2n ) = F _2n+1 -1 .

La tarea es encontrar solo F _2n+1 -1.

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

// Java Program to find even indexed
// Fibonacci Sum in O(Log n) time.
  
class GFG {
  
    static int MAX = 1000;
  
    // Create an array for memoization
    static int f[] = new int[MAX];
  
    // Returns n'th Fibonacci number
    // using table f[]
    static int fib(int n)
    {
        // Base cases
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return (f[n] = 1);
        }
  
        // If fib(n) is already computed
        if (f[n] == 1) {
            return f[n];
        }
  
        int k = (n % 2 == 1) ? (n + 1) / 2 : n / 2;
  
        // Applying above formula [Note value n&1 is 1
        // if n is odd, else 0].
        f[n] = (n % 2 == 1)
                   ? (fib(k) * fib(k)
                      + fib(k - 1) * fib(k - 1))
                   : (2 * fib(k - 1) + fib(k)) * fib(k);
  
        return f[n];
    }
  
    // Computes value of even-indexed Fibonacci Sum
    static int calculateEvenSum(int n)
    {
        return (fib(2 * n + 1) - 1);
    }
  
    // Driver program to test above function
    public static void main(String[] args)
    {
        // Get n
        int n = 11;
  
        // Find the alternating sum
        System.out.println(
            "Even indexed Fibonacci Sum upto " + n
            + " terms: " + calculateEvenSum(n));
    }
}

Even indexed Fibonacci Sum upto 8 terms: 1596

Complejidad de tiempo: O (log n)