Identidad de Cassini

Dado un número N, la tarea es evaluar la siguiente expresión. La complejidad de tiempo esperada es O(1).

 f(n-1)*f(n+1) - f(n)*f(n)

Donde f(n) es el n-ésimo número de Fibonacci con n >= 1. Los primeros números de Fibonacci son 0, 1, 1, 2, 3, 5, 8, 13, ………..ie (considerando 0 como 0th número de Fibonacci) Ejemplos:

Input : n = 5
Output : -1
f(5-1=4) = 3
f(5+1=6) = 8
f(5)*f(5)= 5*5 = 25
f(4)*f(6)- f(5)*f(5)= 24-25= -1

Aunque la tarea es simple, es decir, encontrar n-1th, nth y (n+1)-th números de Fibonacci. Evalúe la expresión y muestre el resultado. Pero esto se puede hacer en tiempo O(1) usando la Identidad de Cassini , que establece que:

           f(n-1)*f(n+1) - f(n*n) = (-1)^n 

Entonces, no necesitamos calcular ningún término de Fibonacci, lo único es verificar si n es par o impar. ¿Cómo funciona la fórmula anterior? La fórmula se basa en la representación matricial de los números de Fibonacci. 

C/C++

// C++ implementation to demonstrate working
// of Cassini’s Identity
#include <bits/stdc++.h>
using namespace std;
 
// Returns (-1)^n
int cassini(int n) { return (n & 1) != 0 ? -1 : 1; }
 
// Driver Method
int main()
{
    int n = 5;
    cout << (cassini(n));
 
    return 0;
}
 
// This code is contributed by phasing17

// Java implementation to demonstrate working
// of Cassini’s Identity
 
class Gfg
{
    // Returns (-1)^n
    static int cassini(int n)
    {
       return (n & 1) != 0 ? -1 : 1;
    }
 
    // Driver method
    public static void main(String args[])
    {
         int n = 5;
         System.out.println(cassini(n));
    }
}

# Python implementation
# to demonstrate working
# of Cassini’s Identity
 
# Returns (-1)^n
def cassini(n):
 
   return -1 if (n & 1) else 1
  
# Driver program
  
n = 5
print(cassini(n))
    
# This code is contributed
# by Anant Agarwal.

// C# implementation to demonstrate
// working of Cassini’s Identity
using System;
 
class GFG {
 
    // Returns (-1) ^ n
    static int cassini(int n)
    {
       return (n & 1) != 0 ? -1 : 1;
    }
  
    // Driver Code
    public static void Main()
    {
         int n = 5;
         Console.Write(cassini(n));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP implementation to
// demonstrate working of
// Cassini’s Identity
 
// Returns (-1)^n
function cassini($n)
{
    return ($n & 1) ? -1 : 1;
}
 
// Driver Code
$n = 5;
echo(cassini($n));
 
// This code is contributed by Ajit.
?>

<script>
// Javascript implementation to
// demonstrate working of
// Cassini’s Identity
 
// Returns (-1)^n
function cassini(n)
{
    return (n & 1) ? -1 : 1;
}
 
// Driver Code
let n = 5;
document.write(cassini(n));
 
// This code is contributed by _saurabh_jaiswal.
 
</script>

Producción :

-1

Complejidad temporal : O(1) ya que solo se realizan operaciones constantes 

Espacio Auxiliar: O(1)

Referencia: https://en.wikipedia.org/wiki/Cassini_and_Catalan_identities Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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.