Suma de cuadrados de números de Fibonacci

Dado un entero positivo N. La tarea es encontrar la suma de los cuadrados de todos los números de Fibonacci hasta el N-ésimo número de Fibonacci. Eso es, 
 

f02 + f12 + f22+.......+fn2 

where fi indicates i-th fibonacci number.

Números de Fibonacci: f 0 =0 y f 1 =1 y f i =f i-1 + f i-2 para todo i>=2.
Ejemplos: 
 

Input: N = 3
Output: 6
Explanation: 0 + 1 + 1 + 4 = 6

Input: N = 6
Output: 104
Explanation: 0 + 1 + 1 + 4 + 9 + 25 + 64 = 104

Método 1: encuentra todos los números de Fibonacci hasta N y suma sus cuadrados. Este método tomará una complejidad de tiempo O(n) .
A continuación se muestra la implementación de este enfoque: 
 

C++

// C++ Program to find sum of
// squares of Fibonacci numbers
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate sum of
// squares of Fibonacci numbers
int calculateSquareSum(int n)
{
    if (n <= 0)
        return 0;
 
    int fibo[n + 1];
    fibo[0] = 0, fibo[1] = 1;
 
    // Initialize result
    int sum = (fibo[0] * fibo[0]) + (fibo[1] * fibo[1]);
 
    // Add remaining terms
    for (int i = 2; i <= n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
        sum += (fibo[i] * fibo[i]);
    }
 
    return sum;
}
 
// Driver program to test above function
int main()
{
    int n = 6;
 
    cout << "Sum of squares of Fibonacci numbers is : "
         << calculateSquareSum(n) << endl;
 
    return 0;
}

Java

// Java Program to find sum of
// squares of Fibonacci numbers
   
public class Improve {
     
     // Function to calculate sum of
    // squares of Fibonacci numbers
    static int calculateSquareSum(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[0]) + (fibo[1] * fibo[1]);
       
        // Add remaining terms
        for (int i = 2; i <= n; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
            sum += (fibo[i] * fibo[i]);
        }
       
        return sum;
    }
       
    // Driver code
    public static void main(String args[])
    {
           int n = 6;
           System.out.println("Sum of squares of Fibonacci numbers is : " +
                                calculateSquareSum(n));
           
    }
    // This Code is contributed by ANKITRAI1
}

Python3

# Python3 Program to find sum of
# squares of Fibonacci numbers
 
# Function to calculate sum of
# squares of Fibonacci numbers
def calculateSquareSum(n):
    fibo = [0] * (n + 1);
    if (n <= 0):
        return 0;
    fibo[0] = 0;
    fibo[1] = 1;
     
    # Initialize result
    sum = ((fibo[0] * fibo[0]) +
           (fibo[1] * fibo[1]));
     
    # Add remaining terms
    for i in range(2, n + 1):
        fibo[i] = (fibo[i - 1] +
                   fibo[i - 2]);
        sum += (fibo[i] * fibo[i]);
 
    return sum;
 
# Driver Code
n = 6;
 
print("Sum of squares of Fibonacci numbers is :",
                          calculateSquareSum(n));
 
# This Code is contributed by mits

C#

// C# Program to find sum of
// squares of Fibonacci numbers
  
using System;
public class Improve {
      
     // Function to calculate sum of
    // squares of Fibonacci numbers
    static int calculateSquareSum(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[0]) + (fibo[1] * fibo[1]);
        
        // Add remaining terms
        for (int i = 2; i <= n; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
            sum += (fibo[i] * fibo[i]);
        }
        
        return sum;
    }
        
    // Driver code
    public static void Main()
    {
           int n = 6;
           Console.Write("Sum of squares of Fibonacci numbers is : " +
                                calculateSquareSum(n));
            
    }
     
}

PHP

<?php
// PHP Program to find sum of
// squares of Fibonacci numbers
 
// Function to calculate sum of
// squares of Fibonacci numbers
function calculateSquareSum($n)
{
    if ($n <= 0)
        return 0;
    $fibo[0] = 0;
    $fibo[1] = 1;
 
    // Initialize result
    $sum = ($fibo[0] * $fibo[0]) +
           ($fibo[1] * $fibo[1]);
 
    // Add remaining terms
    for ($i = 2; $i <= $n; $i++)
    {
        $fibo[$i] = $fibo[$i - 1] +
                    $fibo[$i - 2];
        $sum += ($fibo[$i] * $fibo[$i]);
    }
 
    return $sum;
}
 
// Driver Code
$n = 6;
 
echo "Sum of squares of Fibonacci numbers is : ",
                          calculateSquareSum($n);
 
// This Code is contributed by ajit
?>

Javascript

<script>
 
// Javascript Program to find sum of
// squares of Fibonacci numbers
 
 
 
    // Function to calculate sum of
    // squares of Fibonacci numbers
    function calculateSquareSum(n)
    {
        if (n <= 0)
            return 0;
 
        var fibo = Array(n + 1).fill(0);
        fibo[0] = 0;
        fibo[1] = 1;
 
        // Initialize result
        var sum = (fibo[0] * fibo[0]) +
                  (fibo[1] * fibo[1]);
 
        // Add remaining terms
        for (i = 2; i <= n; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
            sum += (fibo[i] * fibo[i]);
        }
 
        return sum;
    }
 
    // Driver code
     
        var n = 6;
        document.write(
"Sum of squares of Fibonacci numbers is :"
+ calculateSquareSum(n)
);
 
// This code contributed by gauravrajput1
 
</script>
Producción: 

Sum of squares of Fibonacci numbers is : 104

 

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

Método 2: Sabemos que para el i-ésimo número de Fibonacci,
 

fi+1 = fi + fi-1  for all i>0

Or, fi = fi+1 - fi-1 for all i>0
Or, fi2 = fifi+1 - fi-1fi

Así que para cualquier n>0 vemos,
 

f 0 2 + f 1 2 + f 2 2 +…….+f n 2 
= f 0 2 + ( f 1 f 2 – f 0 f 1 )+(f 2 f 3 – f 1 f 2 ) +…… …….+ (f n f n+1 – f n-1 f n
= f n f n+1 (Ya que f 0 = 0) 
 

Esta identidad también se cumple para n=0 (Para n=0, f 0 2 = 0 = f 0 f 1 ).
Por lo tanto, para encontrar la suma, solo se necesita encontrar f n y f n+1 . Para encontrar f n en tiempo O (log n). Consulte el método 5 o el método 6 de este artículo .
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ Program to find sum of squares 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];
}
 
// Function to calculate sum of
// squares of Fibonacci numbers
int calculateSumOfSquares(int n)
{
    return fib(n) * fib(n + 1);
}
 
// Driver Code
int main()
{
    int n = 6;
 
    cout << "Sum of Squares of Fibonacci numbers is : "
         << calculateSumOfSquares(n) << endl;
 
    return 0;
}

Java

// Java Program to find sum of squares of
// Fibonacci numbers in O(Log n) time.
 
class gfg {
 
    static int[] f = new int[1000];
// Create an array for memoization
 
// Returns n'th Fibonacci number using table f[]
    public 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];
    }
 
// Function to calculate sum of
// squares of Fibonacci numbers
    public static int calculateSumOfSquares(int n) {
        return fib(n) * fib(n + 1);
    }
}
 
// Driver Code
class geek {
 
    public static void main(String[] args) {
        gfg g = new gfg();
        int n = 6;
        System.out.println("Sum of Squares of Fibonacci numbers is : "
                + g.calculateSumOfSquares(n));
    }
 
}
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find sum of squares
# of Fibonacci numbers in O(Log n) time.
MAX = 1000
 
# Create an array for memoization
f = [0 for i in range(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:
        return 1
 
    # If fib(n) is already computed
    if f[n]:
        return f[n]
 
    if n & 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:
        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]
 
# Function to calculate sum of
# squares of Fibonacci numbers
def calculateSumOfSquares(n):
 
    return fib(n) * fib(n + 1)
 
# Driver Code
n = 6
print("Sum of Squares of "
      "Fibonacci numbers is :",
      calculateSumOfSquares(n))
 
# This code is contributed by Gaurav Kumar Tailor

C#

// C# Program to find sum of squares of
// Fibonacci numbers in O(Log n) time.
using System;
class gfg
{
 int []f = new int [1000];
  // Create an array for memoization
      
 // Returns n'th Fibonacci number using table f[] 
 public 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];
 }
 
// Function to calculate sum of
// squares of Fibonacci numbers
public int calculateSumOfSquares(int n)
 {
    return fib(n) * fib(n + 1);
 }
}
 
// Driver Code
class geek
{
 public static int Main()
 {
    gfg g = new gfg();
    int n = 6;
    Console.WriteLine( "Sum of Squares of Fibonacci numbers is : {0}", g.calculateSumOfSquares(n));
    return 0;
 }
     
}

PHP

<?php
// PHP Program to find sum of squares of
// Fibonacci numbers in O(Log n) time.
 
$MAX = 1000;
global $f;
 
// Create an array for memoization
$f = array_fill(0, $MAX, 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);
 
    $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];
}
 
// Function to calculate sum of
// squares of Fibonacci numbers
function calculateSumOfSquares( $n)
{
    return fib($n) * fib($n + 1);
}
 
// Driver Code
$n = 6;
 
echo "Sum of Squares of Fibonacci numbers is : ";
echo calculateSumOfSquares($n);
 
// This code is contributed by Rajput-Ji
?>

Javascript

<script>
    // Javascript Program to find sum of squares of
    // Fibonacci numbers in O(Log n) time.
     
    // Create an array for memoization
    let f = new Array(1000);
    f.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];
        }
  
        let 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];
    }
  
    // Function to calculate sum of
    // squares of Fibonacci numbers
    function calculateSumOfSquares(n) {
        return fib(n) * fib(n + 1);
    }
     
    let n = 6;
  
    document.write("Sum of Squares of Fibonacci numbers is : "
         + calculateSumOfSquares(n));
 
</script>
Producción: 

Sum of Squares of Fibonacci numbers is : 104

 

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

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *