Números de Lucas
Los números de Lucas son los elementos de la sucesión L(n) definida por
|
1 2 3 |
L(0) = 2 L(1) = 1 L(n) = L(n-1) + L(n-2), si n > 1. |
Los primeros números de Lucas son
|
1 |
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... |
Definir las funciones
|
1 2 |
nLucas :: Integer -> Integer lucas :: [Integer] |
tales que
- (nLucas n) es el n-ésimo número de Lucas. Por ejemplo,
|
1 2 3 |
nLucas 5 == 11 nLucas 32 == 4870847 length (show (nLucas (10^5))) == 20899 |
- lucas es la lista de los números de Lucas. Por ejemplo,
|
1 |
take 11 lucas == [2,1,3,4,7,11,18,29,47,76,123] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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) |
Soluciones en Maxima
|
1 |
nLucas (n) := lucas (n)$ |
La evaluación de los ejemplos es
|
1 2 3 4 |
(%i5) nLucas (5); (%o5) 11 (%i6) nLucas (32); (%o6) 4870847 |
En Maxima está predefinido