Números oblongos
Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.
Definir las funciones
1 2 |
esOblongo :: Integer -> Bool oblongos :: [Integer] |
tales que
- (esOblongo n) se verifica si n es oblongo. Por ejemplo,
1 2 3 |
esOblongo 42 == True esOblongo 40 == False esOblongo 100000010000000 == True |
- oblongos es la suceción de los números oblongos. Por ejemplo,
1 2 3 |
take 15 oblongos == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210] oblongos !! 50 == 2550 oblongos !! (10^7) == 100000010000000 |
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 |
-- 1ª definición de esOblongo esOblongo1 :: Integer -> Bool esOblongo1 n = n == x * (x+1) where x = round (sqrt (fromIntegral n)) -- 2ª definición de esOblongo esOblongo2 :: Integer -> Bool esOblongo2 n = n `pertenece` oblongos3 pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (< x) ys) -- 1ª definición de oblongos oblongos1 :: [Integer] oblongos1 = [n | n <- [0..] , esOblongo1 n] -- 2ª definición de oblongos oblongos2 :: [Integer] oblongos2 = filter esOblongo1 [0..] -- 3ª definición de oblongos oblongos3 :: [Integer] oblongos3 = zipWith (*) [0..] [1..] |
Se puede escribir haciendo uso de la composición de funciones y de ese modo queda más sencilla la lectura de la definición. Quedaría así:
Buenas, la definición de esOblongos es mejorable. Por ejemplo si la comparas con la primera definición dada:
λ> esOblongo 100000010000000
True
(0.00 secs, 116,592 bytes)
λ> esOblongos1 100000010000000
True
(15.67 secs, 2,448,115,616 bytes)
Esto se debe a que en tu definición tienes que generar todos los números oblongos hasta llegar al que quieres comprobar, lo cual es bastante ineficiente para índices grandes.
Otro detalle bastante más importante es que tu función no funciona para números que no sean oblongos, ya que tienes que comprobar que un número no está en una lista infinita por lo cual nunca va a parar de comprobarlo y no va a dar False.
Buenas, puedes mejorar la definición de esOblongo1. Por ejemplo, comparada con la primera respuesta de la entrada:
λ> esOblongo 10000000100000000
True
(0.00 secs, 116,560 bytes)
λ> esOblongo1 10000000100000000
True
(13.48 secs, 19,200,114,192 bytes)
Dado que un número es oblongo si cumple una determinada propiedad (ser producto de dos números naturales consecutivos), es más eficiente (sobre todo para enteros grandes) comprobar si el número cumple esa propiedad antes que comprobar si pertenece a la lista de números que cumplen esta propiedad (pues tiene que generar esta lista de números hasta llegar al que quieres comprobar).
Y todo esto en caso de que el número sea oblongo, pues en caso de no serlo tienes que comprobar que un número no es elemento de una lista infinita, por lo que el programa no va a dejar de comprobar si el número pertenece a la lista y no va a devolverte False.
También a la hora de definir la función oblongos, puesto que sabes que un número oblongo es producto de dos naturales consecutivos, es más eficiente definirla como la lista de los n*(n+1) (siendo n un número natural o más bien n <- [0..]) pues en este caso solo generas la lista de oblongos en vez de calcular de entre toda la lista de naturales cuales son oblongos. Además es incorrecto añadir el 0 a la lista y que después el generador x sea x take 3 oblongos2
[0,0,2]
Comparación de la eficiencia:
λ> oblongos !! (10^3)
1001000
(0.00 secs, 116,304 bytes)
λ> oblongos2 !! (10^3)
1001000
(4.36 secs, 845,915,528 bytes)
Donde oblongos2 es tu función sin añadir el 0 al principio.
Perdón, esto es incorrecto «Y todo esto en caso de que el número sea oblongo, pues en caso de no serlo tienes que comprobar que un número no es elemento de una lista infinita, por lo que el programa no va a dejar de comprobar si el número pertenece a la lista y no va a devolverte False.» pues has limitado xs hasta n y por tanto la lista sí es finita y sí devuelve el booleano