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