Dado un número positivo n, encuentre el valor de f 0 + f 1 + f 2 + …. + f n donde f i indica el i-ésimo número de Fibonacci. Recuerda que f 0 = 0, f 1 = 1, f 2 = 1, f 3 = 2, f 4 = 3, f 5 = 5, …
Ejemplos:
Input : n = 3 Output : 4 Explanation : 0 + 1 + 1 + 2 = 4 Input : n = 4 Output : 7 Explanation : 0 + 1 + 1 + 2 + 3 = 7
Método 1 (O(n)) El enfoque
de fuerza bruta es bastante sencillo, encuentra todos los números de Fibonacci hasta f(n) y luego súmalos.
C++
// C++ Program to find sum of Fibonacci numbers
#include<bits/stdc++.h>
using namespace std;
// Computes value of first fibonacci numbers
int calculateSum(int n)
{
if (n <= 0)
return 0;
int fibo[n+1];
fibo[0] = 0, fibo[1] = 1;
// Initialize result
int sum = fibo[0] + fibo[1];
// Add remaining terms
for (int i=2; i<=n; i++)
{
fibo[i] = fibo[i-1]+fibo[i-2];
sum += fibo[i];
}
return sum;
}
// Driver program to test above function
int main()
{
int n = 4;
cout << "Sum of Fibonacci numbers is : "
<< calculateSum(n) << endl;
return 0;
}
Java
// Java Program to find
// sum of Fibonacci numbers
import java.io.*;
class GFG {
// Computes value of first
// fibonacci numbers
static int calculateSum(int n)
{
if (n <= 0)
return 0;
int fibo[]=new int[n+1];
fibo[0] = 0; fibo[1] = 1;
// Initialize result
int sum = fibo[0] + fibo[1];
// Add remaining terms
for (int i=2; i<=n; i++)
{
fibo[i] = fibo[i-1]+fibo[i-2];
sum += fibo[i];
}
return sum;
}
// Driver program to test above function
public static void main(String args[])
{
int n = 4;
System.out.println("Sum of Fibonacci" +
" numbers is : "+ calculateSum(n));
}
}
// This code is contributed by Nikita tiwari.
Python3
# Python 3 Program to find
# sum of Fibonacci numbers
# Computes value of first
# fibonacci numbers
def calculateSum(n) :
if (n <= 0) :
return 0
fibo =[0] * (n+1)
fibo[1] = 1
# Initialize result
sm = fibo[0] + fibo[1]
# Add remaining terms
for i in range(2,n+1) :
fibo[i] = fibo[i-1] + fibo[i-2]
sm = sm + fibo[i]
return sm
# Driver program to test
# above function
n = 4
print("Sum of Fibonacci numbers is : " ,
calculateSum(n))
# This code is contributed
# by Nikita tiwari.
C#
// C# Program to find
// sum of Fibonacci numbers
using System;
class GFG
{
// Computes value of first
// fibonacci numbers
static int calculateSum(int n)
{
if (n <= 0)
return 0;
int []fibo = new int[n + 1];
fibo[0] = 0; fibo[1] = 1;
// Initialize result
int sum = fibo[0] + fibo[1];
// Add remaining terms
for (int i = 2; i <= n; i++)
{
fibo[i] = fibo[i - 1] + fibo[i - 2];
sum += fibo[i];
}
return sum;
}
// Driver Code
static void Main()
{
int n = 4;
Console.WriteLine( "Sum of Fibonacci" +
" numbers is : "+
calculateSum(n));
}
}
// This code is contributed by Anuj_67
PHP
<?php
// PHP Program to find sum
// of Fibonacci numbers
// Computes value of first
// fibonacci numbers
function calculateSum($n)
{
if ($n <= 0)
return 0;
$fibo[0] = 0;
$fibo[1] = 1;
// Initialize result
$sum = $fibo[0] + $fibo[1];
// Add remaining terms
for($i = 2; $i <= $n; $i++)
{
$fibo[$i] = $fibo[$i - 1] +
$fibo[$i - 2];
$sum += $fibo[$i];
}
return $sum;
}
// Driver Code
$n = 4;
echo "Sum of Fibonacci numbers is : ",
calculateSum($n),"\n";
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript Program to find sum
// of Fibonacci numbers
// Computes value of first
// fibonacci numbers
function calculateSum(n)
{
let fibo = [];
if (n <= 0)
return 0;
fibo[0] = 0;
fibo[1] = 1;
// Initialize result
let sum = fibo[0] + fibo[1];
// Add remaining terms
for(let i = 2; i <= n; i++)
{
fibo[i] = fibo[i - 1] +
fibo[i - 2];
sum += fibo[i];
}
return sum;
}
// Driver Code
let n = 4;
document.write(`Sum of Fibonacci numbers is :
${calculateSum(n)} <br>`);
// This code is contributed by _saurabh_jaiswal
</script>
Producción :
Sum of Fibonacci numbers is : 7
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Método 2 (O(Log n))
La idea es encontrar la relación entre la suma de los números de Fibonacci y el n-ésimo número de Fibonacci.
F(i) se refiere al i-ésimo número de Fibonacci.
S(i) se refiere a la suma de los números de Fibonacci hasta F(i),
We can rewrite the relation F(n+1) = F(n) + F(n-1) as below F(n-1) = F(n+1) - F(n) Similarly, F(n-2) = F(n) - F(n-1) . . . . . . . . . F(0) = F(2) - F(1) -------------------------------
Sumando todas las ecuaciones, en el lado izquierdo, tenemos
F(0) + F(1) + … F(n-1) que es S(n-1).
Por tanto,
S(n-1) = F(n+1) – F(1)
S(n-1) = F(n+1) – 1
S(n) = F(n+2) – 1 —- (1)
Para encontrar S(n), simplemente calcule el número de Fibonacci (n+2) y reste 1 del resultado.
F(n) se puede evaluar en tiempo O(log n) utilizando el método 5 o el método 6 de este artículo (consulte los métodos 5 y 6).
A continuación se muestra la implementación basada en el método 6 de este
C++
// C++ Program to find sum of Fibonacci numbers 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 first Fibonacci numbers
int calculateSum(int n)
{
return fib(n+2) - 1;
}
// Driver program to test above function
int main()
{
int n = 4;
cout << "Sum of Fibonacci numbers is : "
<< calculateSum(n) << endl;
return 0;
}
Java
// Java Program to find sum of Fibonacci numbers in
// O(Log n) time.
import java.util.*;
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]>0)
return f[n];
int k = ((n & 1)>0)? (n+1)/2 : n/2;
// Applying above formula [Note value n&1 is 1
// if n is odd, else 0].
f[n] = (n & 1)>0? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
: (2*fib(k-1) + fib(k))*fib(k);
return f[n];
}
// Computes value of first Fibonacci numbers
static int calculateSum(int n)
{
return fib(n+2) - 1;
}
// Driver program to test above function
public static void main(String[] args)
{
int n = 4;
System.out.print("Sum of Fibonacci numbers is : "
+ calculateSum(n) +"\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python 3 Program to find sum of
# Fibonacci numbers 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):
n = int(n)
# Base cases
if (n == 0):
return 0
if (n == 1 or n == 2):
return (1)
# If fib(n) is already computed
if (f[n] == True):
return f[n]
k = (n+1)/2 if (n & 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 & 1) else (2 * fib(k-1) + fib(k)) * fib(k)
return f[n]
# Computes value of first Fibonacci numbers
def calculateSum(n):
return fib(n+2) - 1
# Driver program to test above function
n = 4
print("Sum of Fibonacci numbers is :", calculateSum(n))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// C# Program to find sum
// of Fibonacci numbers 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)
{
for(int i = 0;i < MAX;i++)
f[i] = 0;
//Arrays.fill(f, 0);
// 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;
if((n & 1) == 1)
k = (n + 1) / 2 ;
else
k = n / 2;
// Applying above formula
// [Note value n&1 is 1
// if n is odd, else 0].
if((n & 1) == 1)
f[n] = (fib(k) * fib(k) + fib(k - 1)
* fib(k - 1));
else
f[n] = (2 * fib(k - 1) + fib(k)) *
fib(k);
return f[n];
}
// Computes value of first
// Fibonacci numbers
static int calculateSum(int n)
{
return fib(n + 2) - 1;
}
// Driver Code
public static void Main()
{
int n = 4;
Console.Write( "Sum of Fibonacci numbers is : "
+ calculateSum(n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to find sum of Fibonacci
// numbers in O(Log n) time.
$MAX = 1000;
// Create an array for memoization
$f = array_fill(0, $MAX, 0);
// Returns n'th Fibonacci number
// using table f[]
function fib($n)
{
global $f;
// 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];
$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 first Fibonacci numbers
function calculateSum($n)
{
return fib($n + 2) - 1;
}
// Driver Code
$n = 4;
print("Sum of Fibonacci numbers is : " .
calculateSum($n));
// This code is contributed by mits
?>
Javascript
<script>
// javascript Program to find sum of Fibonacci numbers 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] > 0)
return f[n];
var k = ((n & 1) > 0) ? (n + 1) / 2 : n / 2;
// Applying above formula [Note value n&1 is 1
// if n is odd, else 0].
f[n] = (n & 1) > 0 ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) + fib(k)) * fib(k);
return f[n];
}
// Computes value of first Fibonacci numbers
function calculateSum(n) {
return fib(n + 2) - 1;
}
// Driver program to test above function
var n = 4;
document.write("Sum of Fibonacci numbers is : " + calculateSum(n) + "\n");
// This code is contributed by gauravrajput1
</script>
Producción :
Sum of Fibonacci numbers is : 7
Complejidad de tiempo: O (logn)
Espacio auxiliar: O(MAX)
Este artículo es una contribución de Chirag Agarwal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA