Enésimo número par de Fibonacci

Dado un valor n, encuentre el n-ésimo número par de Fibonacci .
Ejemplos: 
 

Input  : n  = 3
Output : 34

Input  : n  = 4
Output : 144

Input : n = 7
Output : 10946

Los números de Fibonacci son los números en la siguiente secuencia de enteros. 
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …. 
donde cualquier número en secuencia está dado por: 
 

 Fn = Fn-1 + Fn-2 
      with seed values
      F0 = 0 and F1 = 1.

La sucesión de números pares de Fibonacci es 0, 2, 8, 34, 144, 610, 2584…. Necesitamos encontrar el número n en esta secuencia.
Si observamos más de cerca la secuencia de Fibonacci, podemos notar que cada tercer número en secuencia es par y la secuencia de números pares sigue la siguiente fórmula recursiva. 
 

Recurrence for Even Fibonacci sequence is:
     EFn = 4EFn-1 + EFn-2
with seed values
     EF0 = 0 and EF1 = 2.

EFn represents n'th term in Even Fibonacci sequence.

¿Cómo funciona la fórmula anterior?  
Echemos un vistazo a la fórmula original de Fibonacci y escribámosla en forma de Fn-3 y Fn-6 debido al hecho de que uno de cada tres números de Fibonacci es par. 

Fn = Fn-1 + Fn-2 [Expanding both terms]
   = Fn-2 + Fn-3 + Fn-3 + Fn-4 
   = Fn-2 + 2Fn-3 + Fn-4 [Expanding first term]
   = Fn-3 + Fn-4 + 2Fn-3 + Fn-4
   = 3Fn-3 + 2Fn-4  [Expanding one Fn-4]
   = 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [Combing Fn-4 and Fn-5]
   = 4Fn-3 + Fn-6  

Since every third Fibonacci Number is even, So if Fn is 
even then Fn-3 is even and Fn-6 is also even. Let Fn be
xth even element and mark it as EFx.
If Fn is EFx, then Fn-3 is previous even number i.e. EFx-1
and Fn-6 is previous of EFx-1 i.e. EFx-2
So
Fn = 4Fn-3 + Fn-6
which means,
EFx = 4EFx-1 + EFx-2

// C++ code to find Even Fibonacci
//Series using normal Recursion
#include<iostream>
using namespace std;
 
// Function which return
//nth even fibonacci number
long int evenFib(int n)
{
    if (n < 1)
    return n;
    if (n == 1)
    return 2;
 
    // calculation of
    // Fn = 4*(Fn-1) + Fn-2
    return ((4 * evenFib(n-1)) +
             evenFib(n-2));
}
 
// Driver Code
int main ()
{
    int n = 7;
    cout << evenFib(n);
    return 0;
}

// Java code to find Even Fibonacci
// Series using normal Recursion
 
class GFG{
  
// Function which return
// nth even fibonacci number
static long evenFib(int n)
{
    if (n < 1)
    return n;
 
    if (n == 1)
    return 2;
 
    // calculation of
    // Fn = 4*(Fn-1) + Fn-2
    return ((4 * evenFib(n-1)) +
                 evenFib(n-2));
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 7;
    System.out.println(evenFib(n));
}
}
 
// This code is contributed by
// Smitha Dinesh Semwal

# Python3 code to find Even  Fibonacci
# Series using normal Recursion
  
# Function which return
#nth even fibonacci number
def evenFib(n) :
    if (n < 1) :
        return n
    if (n == 1)  :
        return 2
  
    # calculation of
    # Fn = 4*(Fn-1) + Fn-2
    return ((4 * evenFib(n-1)) + evenFib(n-2)) 
 
 
# Driver Code
n = 7
print(evenFib(n))
 
 
# This code is contributed by Nikita Tiwari.

// C# code to find Even Fibonacci
// Series using normal Recursion
using System;
 
class GFG {
 
// Function which return
// nth even fibonacci number
static long evenFib(int n)
{
    if (n < 1)
    return n;
 
    if (n == 1)
    return 2;
 
    // calculation of Fn = 4*(Fn-1) + Fn-2
    return ((4 * evenFib(n - 1)) +
                 evenFib(n - 2));
}
 
// Driver code
public static void Main ()
{
    int n = 7;
    Console.Write(evenFib(n));
}
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP code to find Even Fibonacci
// Series using normal Recursion
 
// Function which return
// nth even fibonacci number
function evenFib($n)
{
    if ($n < 1)
        return $n;
    if ($n == 1)
        return 2;
 
    // calculation of
    // Fn = 4*(Fn-1) + Fn-2
    return ((4 * evenFib($n-1)) +
                 evenFib($n-2));
}
 
// Driver Code
$n = 7;
echo(evenFib($n));
 
// This code is contributed by Ajit.
?>

<script>
// Javascript code to find Even Fibonacci
// Series using normal Recursion
 
// Function which return
// nth even fibonacci number
function evenFib(n)
{
    if (n < 1)
        return n;
    if (n == 1)
        return 2;
 
    // calculation of
    // Fn = 4*(Fn-1) + Fn-2
    return ((4 * evenFib(n-1)) +
                 evenFib(n-2));
}
 
// Driver Code
let n = 7;
document.write(evenFib(n));
 
// This code is contributed by _saurabh_jaiswal.
</script>

Producción : 

10946

La complejidad temporal de la implementación anterior es exponencial. Podemos hacerlo en tiempo lineal usando Programación Dinámica. También podemos hacerlo en tiempo O(Log n) usando el hecho EF _n = F _3n . Tenga en cuenta que podemos encontrar el n-ésimo número de Fibonacci en el tiempo O (Log n) (consulte los Métodos 5 y 6 aquí ). 
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.