Números de Lucas

Los números de Lucas son similares a los números de Fibonacci. Los números de Lucas también se definen como la suma de sus dos términos inmediatamente anteriores. Pero aquí los dos primeros términos son 2 y 1 mientras que en los números de Fibonacci los dos primeros términos son 0 y 1 respectivamente. 
Matemáticamente, los Números de Lucas se pueden definir como:
{\displaystyle L_{n}:={\begin{cases}2&{\text{if }}n=0;\\1&{\text{if }}n=1;\\L_{n-1}+L_{n-2}&{\text{if }}n>1.\\\end{cases}}}
Los números de Lucas están en la siguiente secuencia de enteros:
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 …………..
Escribe una función int lucas(int n) n como argumento y devuelve el enésimo número de Lucas.
Ejemplos: 
 

Input : 3
Output : 4

Input : 7
Output : 29

Método 1 (solución recursiva) 
A continuación se muestra una implementación recursiva basada en una fórmula recursiva simple. 
 

C++

// Recursive C/C++ program
// to find n'th Lucas number
#include <stdio.h>
 
// recursive function
int lucas(int n)
{
    // Base cases
    if (n == 0)
        return 2;
    if (n == 1)
        return 1;
 
    // recurrence relation
    return lucas(n - 1) +
        lucas(n - 2);
}
 
// Driver Code
int main()
{
    int n = 9;
    printf("%d", lucas(n));
    return 0;
}

Java

// Recursive Java program to
// find n'th Lucas number
 
class GFG
{
 
    // recursive function
    public static int lucas(int n)
    {
 
        // Base cases
        if (n == 0)
            return 2;
        if (n == 1)
            return 1;
 
        // recurrence relation
        return lucas(n - 1) +
               lucas(n - 2);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int n = 9;
        System.out.println(lucas(n));
    }
}
// This code is contributed
// by Nikita Tiwari.

Python3

# Python3 program to
# find n'th Lucas number
 
# recursive function
def lucas(n):
   
    # Base cases
    if n == 0:
        return 2;
    if n == 1:
        return 1;
   
    # recurrence relation
    return lucas(n - 1) + lucas(n - 2);
     
# Driver code to test above methods
n = 9;
print(lucas(n));
 
# This code is contributed by phasing17

C#

// Recursive C# program to
// find n'th Lucas number
using System;
 
class GFG {
 
    // recursive function
    public static int lucas(int n)
    {
 
        // Base cases
        if (n == 0)
            return 2;
        if (n == 1)
            return 1;
 
        // recurrence relation
        return lucas(n - 1) + lucas(n - 2);
    }
 
    // Driver program
    public static void Main()
    {
 
        int n = 9;
 
        Console.WriteLine(lucas(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// Recursive php program to
// find n'th Lucas number
 
// recursive function
function lucas($n)
{
     
// Base cases
if ($n == 0)
    return 2;
if ($n == 1)
    return 1;
 
// recurrence relation
return lucas($n - 1) +
       lucas($n - 2);
}
 
// Driver Code
$n = 9;
echo lucas($n);
 
// This code is contributed by ajit.
?>

Javascript

<script>
 
// Javascript program to
// find n'th Lucas number
 
    // recursive function
    function lucas(n)
    {
   
        // Base cases
        if (n == 0)
            return 2;
        if (n == 1)
            return 1;
   
        // recurrence relation
        return lucas(n - 1) +
               lucas(n - 2);
    }
 
// Driver code to test above methods
 
        let n = 9;
        document.write(lucas(n));
  
 // This code is contributed by avijitmondal1998.
</script>

Producción : 
 

76

Método 2 (solución iterativa) 
La complejidad temporal de la implementación anterior es exponencial. Podemos optimizarlo para que funcione en tiempo O(n) mediante iteración. 
 

C++

// Iterative C/C++ program
// to find n'th Lucas Number
#include <stdio.h>
 
// Iterative function
int lucas(int n)
{
    // declaring base values
    // for positions 0 and 1
    int a = 2, b = 1, c, i;
 
    if (n == 0)
        return a;
 
    // generating number
    for (i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
 
// Driver Code
int main()
{
    int n = 9;
    printf("%d", lucas(n));
    return 0;
}

Java

// Iterative Java program to
// find n'th Lucas Number
class GFG
{
    // Iterative function
    static int lucas(int n)
    {
        // declaring base values
        // for positions 0 and 1
        int a = 2, b = 1, c, i;
 
        if (n == 0)
            return a;
 
        // generating number
        for (i = 2; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int n = 9;
        System.out.println(lucas(n));
    }
}
 
// This code is contributed
// by Nikita tiwari.

Python3

# Iterative Python 3 program
# to find n'th Lucas Number
 
# Iterative function
def lucas(n) :
 
    # declaring base values
    # for positions 0 and 1
    a = 2
    b = 1
     
    if (n == 0) :
        return a
  
    # generating number
    for i in range(2, n + 1) :
        c = a + b
        a = b
        b = c
     
    return b
     
  
# Driver Code
n = 9
print(lucas(n))
 
# This code is contributed
# by Nikita tiwari.

C#

// Iterative C# program to
// find n'th Lucas Number
using System;
 
class GFG {
 
    // Iterative function
    static int lucas(int n)
    {
 
        // declaring base values
        // for positions 0 and 1
        int a = 2, b = 1, c, i;
 
        if (n == 0)
            return a;
 
        // generating number
        for (i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
 
        return b;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 9;
 
        Console.WriteLine(lucas(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// Iterative php program
// to find n'th Lucas Number
 
function lucas($n)
{
    // declaring base values
    // for positions 0 and 1
    $a = 2; $b = 1; $c; $i;
 
    if ($n == 0)
        return $a;
 
    // generating number
    for ($i = 2; $i <= $n; $i++)
    {
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }
    return $b;
}
 
// Driver Code
$n = 9;
echo lucas($n);
 
// This code is contributed by ajit
?>

Javascript

<script>
    // Iterative Javascript program to find n'th Lucas Number
     
    // Iterative function
    function lucas(n)
    {
  
        // declaring base values
        // for positions 0 and 1
        let a = 2, b = 1, c, i;
  
        if (n == 0)
            return a;
  
        // generating number
        for (i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
  
        return b;
    }
     
    let n = 9;
  
      document.write(lucas(n));
         
</script>

Producción : 
 

76

Complejidad de tiempo : O (n) desde que se usa un ciclo for

Complejidad del espacio : O(1) ya que usa variables constantes

Referencias:  
https://en.wikipedia.org/wiki/Lucas_number
Este artículo es una contribución de Harsh Agarwal . 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.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *