Dado un rango [l, r] , la tarea es encontrar la suma fib(l) + fib(l + 1) + fib(l + 2) + ….. + fib(r) donde fib(n) es el n -ésimo número de Fibonacci.
Ejemplos:
Entrada: l = 2, r = 5
Salida: 11
fib(2) + fib(3) + fib(4) + fib(5) = 1 + 2 + 3 + 5 = 11Entrada: l = 4, r = 8
Salida: 50
Enfoque ingenuo: simplemente calcule fib(l) + fib(l + 1) + fib(l + 2) + ….. + fib(r) en la complejidad del tiempo O(r – l) .
Para encontrar fib(n) en O(1) nos ayudaremos de la proporción áurea.
Cálculo de Fibonacci usando la fórmula de Binet
fib(n) = phi n – psi n ) / ?5
Donde,
phi = (1 + sqrt(5)) / 2 que es aproximadamente igual a 1.61803398875
psi = 1 – phi = (1 – sqrt(5)) / 2 que es aproximadamente igual a 0.61803398875
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to return the nth Fibonacci number
int fib(int n)
{
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}
// Function to return the required sum
ll calculateSum(int l, int r)
{
// To store the sum
ll sum = 0;
// Calculate the sum
for (int i = l; i <= r; i++)
sum += fib(i);
return sum;
}
// Driver code
int main()
{
int l = 4, r = 8;
cout << calculateSum(l, r);
return 0;
}
Java
// Java implementation of the approach
import java.lang.Math;
class GFG
{
// Function to return the nth Fibonacci number
static int fib(int n)
{
double phi = (1 + Math.sqrt(5)) / 2;
return (int)Math.round(Math.pow(phi, n) / Math.sqrt(5));
}
// Function to return the required sum
static int calculateSum(int l, int r)
{
// To store the sum
int sum = 0;
// Calculate the sum
for (int i = l; i <= r; i++)
sum += fib(i);
return sum;
}
// Driver code
public static void main(String[] args)
{
int l = 4, r = 8;
System.out.println(calculateSum(l, r));
}
}
//This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach # Function to return the nth # Fibonacci number def fib(n): phi = ((1 + (5 ** (1 / 2))) / 2); return round((phi ** n) / (5 ** (1 / 2))); # Function to return the required sum def calculateSum(l, r): # To store the sum sum = 0; # Calculate the sum for i in range(l, r + 1): sum += fib(i); return sum; # Driver Code if __name__ == '__main__': l, r = 4, 8; print(calculateSum(l, r)); # This code contributed by Rajput-Ji
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the nth Fibonacci number
static int fib(int n)
{
double phi = (1 + Math.Sqrt(5)) / 2;
return (int)Math.Round(Math.Pow(phi, n) / Math.Sqrt(5));
}
// Function to return the required sum
static int calculateSum(int l, int r)
{
// To store the sum
int sum = 0;
// Calculate the sum
for (int i = l; i <= r; i++)
sum += fib(i);
return sum;
}
// Driver code
public static void Main()
{
int l = 4, r = 8;
Console.WriteLine(calculateSum(l, r));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
// Function to return the nth
// Fibonacci number
function fib($n)
{
$phi = (1 + sqrt(5)) / 2;
return (int)round(pow($phi, $n) / sqrt(5));
}
// Function to return the required sum
function calculateSum($l, $r)
{
// To store the sum
$sum = 0;
// Calculate the sum
for ($i = $l; $i <= $r; $i++)
$sum += fib($i);
return $sum;
}
// Driver code
$l = 4;
$r = 8;
echo calculateSum($l, $r);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the nth Fibonacci number
function fib(n) {
var phi = (1 + Math.sqrt(5)) / 2;
return parseInt( Math.round
(Math.pow(phi, n)/ Math.sqrt(5))
);
}
// Function to return the required sum
function calculateSum(l , r) {
// To store the sum
var sum = 0;
// Calculate the sum
for (i = l; i <= r; i++)
sum += fib(i);
return sum;
}
// Driver code
var l = 4, r = 8;
document.write(calculateSum(l, r));
// This code contributed by gauravrajput1
</script>
50
Enfoque eficiente: la idea es encontrar la relación entre la suma de los números de Fibonacci y el n -ésimo número de Fibonacci y usar la fórmula de Binet para calcular su valor.
Deducción de relación
- 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).
Podemos reescribir la relación F(n + 1) = F(n) + F(n – 1) como sigue:
F(n – 1) = F(n + 1) – F(n)
De manera similar,
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 lo tanto,
S(n – 1) = F(n + 1) – F(1)
S(n – 1) = F(n + 1) – 1
S(n) = F(n + 2) – 1
Para encontrar S(n) , simplemente calcule el (n + 2) número de Fibonacci y reste 1 del resultado.
Por lo tanto,
S(l, r) = S(r) – S(l – 1)
S(l, r) = F(r + 2) – 1 – (F(l + 1) – 1)
S(l, r) = F(r + 2) – F(l + 1)
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the nth Fibonacci number
int fib(int n)
{
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}
// Function to return the required sum
int calculateSum(int l, int r)
{
// Using our deduced result
int sum = fib(r + 2) - fib(l + 1);
return sum;
}
// Driver code
int main()
{
int l = 4, r = 8;
cout << calculateSum(l, r);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the nth Fibonacci number
static int fib(int n)
{
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n) / Math.sqrt(5));
}
// Function to return the required sum
static int calculateSum(int l, int r)
{
// Using our deduced result
int sum = fib(r + 2) - fib(l + 1);
return sum;
}
// Driver code
public static void main(String[] args)
{
int l = 4, r = 8;
System.out.println(calculateSum(l, r));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach import math # Function to return the nth # Fibonacci number def fib(n): phi = (1 + math.sqrt(5)) / 2; return int(round(pow(phi, n) / math.sqrt(5))); # Function to return the required sum def calculateSum(l, r): # Using our deduced result sum = fib(r + 2) - fib(l + 1); return sum; # Driver code l = 4; r = 8; print(calculateSum(l, r)); # This code is contributed by mits
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the nth Fibonacci number
static int fib(int n)
{
double phi = (1 + Math.Sqrt(5)) / 2;
return (int) Math.Round(Math.Pow(phi, n) /
Math.Sqrt(5));
}
// Function to return the required sum
static int calculateSum(int l, int r)
{
// Using our deduced result
int sum = fib(r + 2) - fib(l + 1);
return sum;
}
// Driver code
public static void Main()
{
int l = 4, r = 8;
Console.WriteLine(calculateSum(l, r));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to return the nth Fibonacci number
function fib($n)
{
$phi = (1 + sqrt(5)) / 2;
return (int) round(pow($phi, $n) / sqrt(5));
}
// Function to return the required sum
function calculateSum($l, $r)
{
// Using our deduced result
$sum = fib($r + 2) - fib($l + 1);
return $sum;
}
// Driver code
$l = 4; $r = 8;
echo(calculateSum($l, $r));
// This code is contributed by Code_Mech
?>
Javascript
<script>
// javascript implementation of the approach
// Function to return the nth Fibonacci number
function fib(n) {
var phi = (1 + Math.sqrt(5)) / 2;
return parseInt( Math.round(Math.pow(phi, n) / Math.sqrt(5)));
}
// Function to return the required sum
function calculateSum(l , r) {
// Using our deduced result
var sum = fib(r + 2) - fib(l + 1);
return sum;
}
// Driver code
var l = 4, r = 8;
document.write(calculateSum(l, r));
// This code contributed by aashish1995
</script>
50
Complejidad de Tiempo: O(log r)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ShivamChauhan5 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA