Encuentra la suma de los primeros N números impares de Fibonacci

Dado un número, N. Encuentra la suma de los primeros N números impares de Fibonacci.

Nota : la respuesta puede ser muy grande, así que imprima el módulo de respuesta 10^9+7.

Ejemplos :  

Input : N = 3
Output : 5
Explanation : 1 + 1 + 3

Input : 6
Output : 44
Explanation : 1 + 1 + 3 + 5 + 13 + 21

Enfoque : La serie impar de Fibonacci es:  

1, 1, 3, 5, 13, 21, 55, 89......

La suma del prefijo de la serie impar de Fibonacci es:  

1, 2, 5, 10, 23, 44, 99, 188.....

La fórmula para la suma de los primeros N números impares de Fibonacci es: 

a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3) + a(n-4) - a(n-5) for n>5  

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

// CPP program to Find the sum of
// first N odd Fibonacci numbers
#include <bits/stdc++.h>
using namespace std;
 
#define mod 1000000007
 
// Function to calculate sum of first
// N odd Fibonacci numbers
long long sumOddFibonacci(int n)
{
    long long Sum[n + 1];
 
    // base values
    Sum[0] = 0;
    Sum[1] = 1;
    Sum[2] = 2;
    Sum[3] = 5;
    Sum[4] = 10;
    Sum[5] = 23;
 
    for (int i = 6; i <= n; i++) {
        Sum[i] = ((Sum[i - 1] + (4 * Sum[i - 2]) % mod -
                  (4 * Sum[i - 3]) % mod + mod) % mod +
                  (Sum[i - 4] - Sum[i - 5] + mod) % mod) % mod;
    }
 
    return Sum[n];
}
 
// Driver code
int main()
{
    long long n = 6;
 
    cout << sumOddFibonacci(n);
 
    return 0;
}

// Java  program to Find the sum of
// first N odd Fibonacci numbers
 
import java.io.*;
 
class GFG {
    static int mod =1000000007;
 
// Function to calculate sum of first
// N odd Fibonacci numbers
static  int sumOddFibonacci(int n)
{
     int Sum[]=new int[n + 1];
 
    // base values
    Sum[0] = 0;
    Sum[1] = 1;
    Sum[2] = 2;
    Sum[3] = 5;
    Sum[4] = 10;
    Sum[5] = 23;
 
    for (int i = 6; i <= n; i++) {
        Sum[i] = ((Sum[i - 1] + (4 * Sum[i - 2]) % mod -
                (4 * Sum[i - 3]) % mod + mod) % mod +
                (Sum[i - 4] - Sum[i - 5] + mod) % mod) % mod;
    }
 
    return Sum[n];
}
 
// Driver code
     
    public static void main (String[] args) {
 
    int n = 6;
    System.out.println(sumOddFibonacci(n));
    }
//This Code is Contributed by Sachin   
}

# Python3 program to Find the sum of
# first N odd Fibonacci numbers
mod = 1000000007 ;
 
# Function to calculate sum of
# first N odd Fibonacci numbers
def sumOddFibonacci(n):
 
    Sum=[0]*(n + 1);
 
    # base values
    Sum[0] = 0;
    Sum[1] = 1;
    Sum[2] = 2;
    Sum[3] = 5;
    Sum[4] = 10;
    Sum[5] = 23;
 
    for i in range(6,n+1):
        Sum[i] = ((Sum[i - 1] +
                    (4 * Sum[i - 2]) % mod -
                    (4 * Sum[i - 3]) % mod +
                    mod) % mod + (Sum[i - 4] -
                    Sum[i - 5] + mod) % mod) % mod;
 
    return Sum[n];
 
# Driver code
n = 6;
print(sumOddFibonacci(n));
 
# This code is contributed by mits

// C#  program to Find the sum of
// first N odd Fibonacci numbers
 
using System;
 
public class GFG{
 
static int mod =1000000007;
// Function to calculate sum of first
// N odd Fibonacci numbers
static int sumOddFibonacci(int n)
{
    int []Sum=new int[n + 1];
 
    // base values
    Sum[0] = 0;
    Sum[1] = 1;
    Sum[2] = 2;
    Sum[3] = 5;
    Sum[4] = 10;
    Sum[5] = 23;
 
    for (int i = 6; i <= n; i++) {
        Sum[i] = ((Sum[i - 1] + (4 * Sum[i - 2]) % mod -
                (4 * Sum[i - 3]) % mod + mod) % mod +
                (Sum[i - 4] - Sum[i - 5] + mod) % mod) % mod;
    }
 
    return Sum[n];
}
 
// Driver code
     
     
     
    static public void Main (){
        int n = 6;
    Console.WriteLine(sumOddFibonacci(n));
    }
//This Code is Contributed by Sachin    
}

<?php
// PHP program to Find the sum of
// first N odd Fibonacci numbers
$mod = 1000000007 ;
 
// Function to calculate sum of
// first N odd Fibonacci numbers
function sumOddFibonacci($n)
{
    global $mod;
    $Sum[$n + 1] = array();
 
    // base values
    $Sum[0] = 0;
    $Sum[1] = 1;
    $Sum[2] = 2;
    $Sum[3] = 5;
    $Sum[4] = 10;
    $Sum[5] = 23;
 
    for ($i = 6; $i <= $n; $i++)
    {
        $Sum[$i] = (($Sum[$i - 1] +
                    (4 * $Sum[$i - 2]) % $mod -
                    (4 * $Sum[$i - 3]) % $mod +
                    $mod) % $mod + ($Sum[$i - 4] -
                    $Sum[$i - 5] + $mod) % $mod) % $mod;
    }
 
    return $Sum[$n];
}
 
// Driver code
$n = 6;
echo sumOddFibonacci($n);
 
// This code is contributed by jit_t
?>

<script>
// javascript  program to Find the sum of
// first N odd Fibonacci numbers
 
    var mod = 1000000007;
 
    // Function to calculate sum of first
    // N odd Fibonacci numbers
    function sumOddFibonacci(n) {
        var Sum = Array(n + 1).fill(0);
 
        // base values
        Sum[0] = 0;
        Sum[1] = 1;
        Sum[2] = 2;
        Sum[3] = 5;
        Sum[4] = 10;
        Sum[5] = 23;
 
        for (i = 6; i <= n; i++) {
            Sum[i] = ((Sum[i - 1] + (4 * Sum[i - 2]) % mod - (4 * Sum[i - 3]) % mod + mod) % mod
                    + (Sum[i - 4] - Sum[i - 5] + mod) % mod) % mod;
        }
 
        return Sum[n];
    }
 
    // Driver code
 
     
 
        var n = 6;
        document.write(sumOddFibonacci(n));
 
// This code contributed by umadevi9616
</script>

44

Complejidad de Tiempo: O(n), Espacio Auxiliar: O(n)