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: 
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