Suma de números de Fibonacci en un rango

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 = 11

Entrada: 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 ⁿ – psi ⁿ ) / ?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>

Producción:

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>

Producción:

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

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta