Dado un entero positivo N, la tarea es encontrar el valor de F 2 + F 4 + F 6 +………+ F 2n hasta N términos donde F i denota el i-ésimo número de Fibonacci.
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, ……
Ejemplos:
Entrada: n = 5
Salida: 88
N = 5, por lo que la serie de Fibonacci se generará desde el término 0 hasta el término 10:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Suma de elementos en índices pares = 0 + 1 + 3 + 8 + 21 + 55
Entrada: n = 8
Salida: 1596
0 + 1 + 3 + 8 + 21 + 55 + 144 + 377 + 987 = 1596.
Método 1: este método incluye resolver el problema directamente encontrando todos los números de Fibonacci hasta 2n y sumando solo los índices pares. Pero esto requerirá una complejidad de tiempo O(n).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find sum
// of even-indiced Fibonacci numbers
#include <bits/stdc++.h>
using namespace std;
// Computes value of first fibonacci numbers
// and stores the even-indexed sum
int calculateEvenSum(int n)
{
if (n <= 0)
return 0;
int fibo[2 * n + 1];
fibo[0] = 0, fibo[1] = 1;
// Initialize result
int sum = 0;
// Add remaining terms
for (int i = 2; i <= 2 * n; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
// For even indices
if (i % 2 == 0)
sum += fibo[i];
}
// Return the alternating sum
return sum;
}
// Driver program to test above function
int main()
{
// Get n
int n = 8;
// Find the even-indiced sum
cout << "Even indexed Fibonacci Sum upto "
<< n << " terms: "
<< calculateEvenSum(n) << endl;
return 0;
}
Java
// Java Program to find sum
// of even-indiced Fibonacci numbers
import java.io.*;
class GFG {
// Computes value of first fibonacci numbers
// and stores the even-indexed sum
static int calculateEvenSum(int n)
{
if (n <= 0)
return 0;
int fibo[] = new int[2 * n + 1];
fibo[0] = 0; fibo[1] = 1;
// Initialize result
int sum = 0;
// Add remaining terms
for (int i = 2; i <= 2 * n; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
// For even indices
if (i % 2 == 0)
sum += fibo[i];
}
// Return the alternating sum
return sum;
}
// Driver program
public static void main (String[] args) {
// Get n
int n = 8;
// Find the even-indiced sum
System.out.println("Even indexed Fibonacci Sum upto "
+ n + " terms: "+
+ calculateEvenSum(n));
}
}
// This code is contributed
// by shs
Python 3
# Python3 Program to find sum
# of even-indiced Fibonacci numbers
# Computes value of first fibonacci
# numbers and stores the even-indexed sum
def calculateEvenSum(n) :
if n <= 0 :
return 0
fibo = [0] * (2 * n + 1)
fibo[0] , fibo[1] = 0 , 1
# Initialize result
sum = 0
# Add remaining terms
for i in range(2, 2 * n + 1) :
fibo[i] = fibo[i - 1] + fibo[i - 2]
# For even indices
if i % 2 == 0 :
sum += fibo[i]
# Return the alternating sum
return sum
# Driver code
if __name__ == "__main__" :
# Get n
n = 8
# Find the even-indiced sum
print("Even indexed Fibonacci Sum upto",
n, "terms:", calculateEvenSum(n))
# This code is contributed
# by ANKITRAI1
C#
// C# Program to find sum of
// even-indiced Fibonacci numbers
using System;
class GFG
{
// Computes value of first fibonacci
// numbers and stores the even-indexed sum
static int calculateEvenSum(int n)
{
if (n <= 0)
return 0;
int []fibo = new int[2 * n + 1];
fibo[0] = 0; fibo[1] = 1;
// Initialize result
int sum = 0;
// Add remaining terms
for (int i = 2; i <= 2 * n; i++)
{
fibo[i] = fibo[i - 1] +
fibo[i - 2];
// For even indices
if (i % 2 == 0)
sum += fibo[i];
}
// Return the alternating sum
return sum;
}
// Driver Code
static public void Main ()
{
// Get n
int n = 8;
// Find the even-indiced sum
Console.WriteLine("Even indexed Fibonacci Sum upto " +
n + " terms: " + calculateEvenSum(n));
}
}
// This code is contributed
// by Sach_Code
PHP
<?php
// PHP Program to find sum of
// even-indiced Fibonacci numbers
// Computes value of first fibonacci
// numbers and stores the even-indexed sum
function calculateEvenSum($n)
{
if ($n <= 0)
return 0;
$fibo[2 * $n + 1] = array();
$fibo[0] = 0; $fibo[1] = 1;
// Initialize result
$sum = 0;
// Add remaining terms
for ($i = 2; $i <= 2 * $n; $i++)
{
$fibo[$i] = $fibo[$i - 1] +
$fibo[$i - 2];
// For even indices
if ($i % 2 == 0)
$sum += $fibo[$i];
}
// Return the alternating sum
return $sum;
}
// Driver Code
// Get n
$n = 8;
// Find the even-indiced sum
echo "Even indexed Fibonacci Sum upto " . $n .
" terms: " . calculateEvenSum($n) . "\n";
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Javascript
<script>
// Javascript Program to find sum
// of even-indiced Fibonacci numbers
// Computes value of first fibonacci numbers
// and stores the even-indexed sum
function calculateEvenSum( n)
{
if (n <= 0)
return 0;
let fibo = Array(2 * n + 1);
fibo[0] = 0;
fibo[1] = 1;
// Initialize result
let sum = 0;
// Add remaining terms
for ( i = 2; i <= 2 * n; i++)
{
fibo[i] = fibo[i - 1] + fibo[i - 2];
// For even indices
if (i % 2 == 0)
sum += fibo[i];
}
// Return the alternating sum
return sum;
}
// Driver program
// Get n
let n = 8;
// Find the even-indiced sum
document.write("Even indexed Fibonacci Sum upto " + n + " terms: " + +calculateEvenSum(n));
// This code is contributed by 29AjayKumar
</script>
Producción:
Even indexed Fibonacci Sum upto 8 terms: 1596
Método-2:
Se puede ver claramente que la suma requerida se puede obtener así:
2 ( F 2 + F 4 + F 6 +………+ F 2n ) = (F 1 + F 2 + F 3 + F 4 +………+ F 2n ) – (F 1 – F 2 + F 3 – F 4 +………+ 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 1 + F 2 + F 3 + F 4 +………+ F2n = 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 1 – F 2 + F 3 – F 4 +…………- F 2n = 1 + (-1) 2n+1 F 2n-1 = 1 – F 2n-1 .
Entonces, 2 ( F 2 + F 4 + F 6 +………+ 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 2 + F 4 + F 6 +………+ F 2n ) = F 2n+ 1 -1 .
Entonces, para encontrar la suma requerida, la tarea es encontrar solo F 2n+1 que requiere tiempo O (log n). (Consulte el método 5 o el método 6 en este artículo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find even indexed Fibonacci Sum in
// O(Log n) time.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Create an array for memoization
int f[MAX] = { 0 };
// Returns n'th Fibonacci number
// using table f[]
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])
return f[n];
int k = (n & 1) ? (n + 1) / 2 : n / 2;
// Applying above formula [Note value n&1 is 1
// if n is odd, else 0].
f[n] = (n & 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
int calculateEvenSum(int n)
{
return (fib(2 * n + 1) - 1);
}
// Driver program to test above function
int main()
{
// Get n
int n = 8;
// Find the alternating sum
cout << "Even indexed Fibonacci Sum upto "
<< n << " terms: "
<< calculateEvenSum(n) << endl;
return 0;
}
Java
// 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 = 8;
// Find the alternating sum
System.out.println("Even indexed Fibonacci Sum upto "
+ n + " terms: "
+ calculateEvenSum(n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 Program to find even indexed
# Fibonacci Sum in O(Log n) time.
MAX = 1000;
# Create an array for memoization
f = [0] * MAX;
# Returns n'th Fibonacci number
# using table f[]
def fib(n):
# Base cases
if (n == 0):
return 0;
if (n == 1 or n == 2):
f[n] = 1;
return f[n];
# If fib(n) is already computed
if (f[n]):
return f[n];
k = (n + 1) // 2 if (n % 2 == 1) else n // 2;
# Applying above formula [Note value n&1 is 1
# if n is odd, else 0].
f[n] = (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) \
if (n % 2 == 1) else (2 * fib(k - 1) + fib(k)) * fib(k);
return f[n];
# Computes value of even-indexed Fibonacci Sum
def calculateEvenSum(n):
return (fib(2 * n + 1) - 1);
# Driver Code
if __name__ == '__main__':
# Get n
n = 8;
# Find the alternating sum
print("Even indexed Fibonacci Sum upto",
n, "terms:", calculateEvenSum(n));
# This code is contributed by PrinciRaj1992
C#
// C# Program to find even indexed Fibonacci Sum in
// O(Log n) time.
using System;
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 code
public static void Main()
{
// Get n
int n = 8;
// Find the alternating sum
Console.WriteLine("Even indexed Fibonacci Sum upto "
+ n + " terms: "
+ calculateEvenSum(n));
}
}
//This code is contributed by 29AjayKumar
Javascript
<script>
// javascript Program to find even indexed Fibonacci Sum in
// O(Log n) time.
var MAX = 1000;
// Create an array for memoization
var f = Array(MAX).fill(0);
// Returns n'th Fibonacci number
// using table f
function fib(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];
}
var 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
function calculateEvenSum(n) {
return (fib(2 * n + 1) - 1);
}
// Driver program to test above function
// Get n
var n = 8;
// Find the alternating sum
document.write("Even indexed Fibonacci Sum upto " + n + " terms: " + calculateEvenSum(n));
// This code is contributed by todaysgaurav
</script>
Producción:
Even indexed Fibonacci Sum upto 8 terms: 1596
Publicación traducida automáticamente
Artículo escrito por tufan_gupta2000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA