Números de Lucas
Los números de Lucas son los elementos de la sucesión L(n) definida por
L(0) = 2 L(1) = 1 L(n) = L(n-1) + L(n-2), si n > 1.
Los primeros números de Lucas son
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...
Definir las funciones
nLucas :: Integer -> Integer lucas :: [Integer]
tales que
- (nLucas n) es el n-ésimo número de Lucas. Por ejemplo,
nLucas 5 == 11 nLucas 32 == 4870847 length (show (nLucas (10^5))) == 20899
- lucas es la lista de los números de Lucas. Por ejemplo,
take 11 lucas == [2,1,3,4,7,11,18,29,47,76,123]
Soluciones
import Data.List (genericIndex) -- 1ª definición -- ============= nLucas1 :: Integer -> Integer nLucas1 0 = 2 nLucas1 1 = 1 nLucas1 n = nLucas1 (n-1) + nLucas1 (n-2) lucas1 :: [Integer] lucas1 = [nLucas1 n | n <- [0..]] -- 2ª definición -- ============= lucas2 :: [Integer] lucas2 = 2 : 1 : zipWith (+) lucas2 (tail lucas2) nLucas2 :: Integer -> Integer nLucas2 n = lucas2 `genericIndex` n -- 3ª definición -- ============= lucas3 :: [Integer] lucas3 = 2 : scanl (+) 1 lucas3 nLucas3 :: Integer -> Integer nLucas3 = genericIndex lucas3 -- Comparación de eficiencia -- ========================= -- λ> nLucas1 32 -- 4870847 -- (3.22 secs, 1,467,677,208 bytes) -- λ> nLucas2 32 -- 4870847 -- (0.00 secs, 0 bytes) -- λ> nLucas3 32 -- 4870847 -- (0.00 secs, 0 bytes) -- -- λ> length (show (nLucas2 230000)) -- 48068 -- (1.57 secs, 2,415,008,392 bytes) -- λ> length (show (nLucas3 230000)) -- 48068 -- (2.08 secs, 2,411,107,352 bytes)