even – Página 3 – Exercitium

Elemento del árbol binario completo según su posición

José A. Alonso, 6-diciembre-2018, Medio

Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

                  1
                 /  \
                /    \
               /      \
              2        3
             / \      / \
            4   5    6   7
           / \ 
          8   9

Los árboles binarios se puede representar mediante el siguiente tipo

   data Arbol = H
              | N Integer Arbol Arbol
     deriving (Show, Eq)

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 9 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

   data Movimiento = I | D deriving (Show, Eq)
   type Posicion   = [Movimiento]

Definir la función

   elementoEnPosicion :: Posicion -> Integer

tal que (elementoEnPosicion ms) es el elemento en la posición ms. Por ejemplo,

   elementoEnPosicion [D,I]    ==  6
   elementoEnPosicion [D,D]    ==  7
   elementoEnPosicion [I,I,D]  ==  9
   elementoEnPosicion []       ==  1

Soluciones

import Test.QuickCheck
 
data Arbol = H
           | N Integer Arbol Arbol
  deriving (Eq, Show)
 
data Movimiento = I | D deriving (Show, Eq)
 
type Posicion = [Movimiento]
 
-- 1ª solución
-- ===========
 
elementoEnPosicion :: Posicion -> Integer
elementoEnPosicion ms =
  aux ms (arbolBinarioCompleto (2^(1 + length ms)))
  where aux []     (N x _ _) = x
        aux (I:ms) (N _ i _) = aux ms i
        aux (D:ms) (N _ _ d) = aux ms d
 
-- (arbolBinarioCompleto n) es el árbol binario completo con n
-- nodos. Por ejemplo, 
--    λ> arbolBinarioCompleto 4
--    N 1 (N 2 (N 4 H H) H) (N 3 H H)
--    λ> pPrint (arbolBinarioCompleto 9)
--    N 1
--      (N 2
--         (N 4
--            (N 8 H H)
--            (N 9 H H))
--         (N 5 H H))
--      (N 3
--         (N 6 H H)
--         (N 7 H H))
arbolBinarioCompleto :: Integer -> Arbol
arbolBinarioCompleto n = aux 1
  where aux i | i <= n    = N i (aux (2*i)) (aux (2*i+1))
              | otherwise = H
 
-- 2ª solución
-- ===========
 
elementoEnPosicion2 :: Posicion -> Integer
elementoEnPosicion2 = aux . reverse
  where aux []     = 1
        aux (I:ms) = 2 * aux ms
        aux (D:ms) = 2 * aux ms + 1
 
-- Equivalencia
-- ============
 
-- La propiedad es
prop_elementoEnPosicion_equiv :: Positive Integer -> Bool
prop_elementoEnPosicion_equiv (Positive n) =
  elementoEnPosicion  ps == n &&
  elementoEnPosicion2 ps == n 
  where ps = posicionDeElemento n
 
-- tal que (posicionDeElemento n) es la posición del elemento n en el
-- árbol binario completo. Por ejemplo,
--    posicionDeElemento 6  ==  [D,I]
--    posicionDeElemento 7  ==  [D,D]
--    posicionDeElemento 9  ==  [I,I,D]
--    posicionDeElemento 1  ==  []
posicionDeElemento :: Integer -> Posicion
posicionDeElemento n =
  [f x | x <- tail (reverse (binario n))]
  where f 0 = I
        f 1 = D
 
-- (binario n) es la lista de los dígitos de la representación binaria
-- de n. Por ejemplo,
--    binario 11  ==  [1,1,0,1]
binario :: Integer -> [Integer]
binario n
  | n < 2     = [n]
  | otherwise = n `mod` 2 : binario (n `div` 2)
 
-- La comprobación es
--    λ> quickCheck prop_elementoEnPosicion_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (show (elementoEnPosicion (replicate (3*10^5) D)))
--    90310
--    (1.96 secs, 11,518,771,016 bytes)
--    λ> length (show (elementoEnPosicion2 (replicate (3*10^5) D)))
--    90310
--    (14.32 secs, 11,508,181,176 bytes)

import Test.QuickCheck data Arbol = H | N Integer Arbol Arbol deriving (Eq, Show) data Movimiento = I | D deriving (Show, Eq) type Posicion = [Movimiento] -- 1ª solución -- =========== elementoEnPosicion :: Posicion -> Integer elementoEnPosicion ms = aux ms (arbolBinarioCompleto (2^(1 + length ms))) where aux [] (N x _ _) = x aux (I:ms) (N _ i _) = aux ms i aux (D:ms) (N _ _ d) = aux ms d -- (arbolBinarioCompleto n) es el árbol binario completo con n -- nodos. Por ejemplo, -- λ> arbolBinarioCompleto 4 -- N 1 (N 2 (N 4 H H) H) (N 3 H H) -- λ> pPrint (arbolBinarioCompleto 9) -- N 1 -- (N 2 -- (N 4 -- (N 8 H H) -- (N 9 H H)) -- (N 5 H H)) -- (N 3 -- (N 6 H H) -- (N 7 H H)) arbolBinarioCompleto :: Integer -> Arbol arbolBinarioCompleto n = aux 1 where aux i | i <= n = N i (aux (2*i)) (aux (2*i+1)) | otherwise = H -- 2ª solución -- =========== elementoEnPosicion2 :: Posicion -> Integer elementoEnPosicion2 = aux . reverse where aux [] = 1 aux (I:ms) = 2 * aux ms aux (D:ms) = 2 * aux ms + 1 -- Equivalencia -- ============ -- La propiedad es prop_elementoEnPosicion_equiv :: Positive Integer -> Bool prop_elementoEnPosicion_equiv (Positive n) = elementoEnPosicion ps == n && elementoEnPosicion2 ps == n where ps = posicionDeElemento n -- tal que (posicionDeElemento n) es la posición del elemento n en el -- árbol binario completo. Por ejemplo, -- posicionDeElemento 6 == [D,I] -- posicionDeElemento 7 == [D,D] -- posicionDeElemento 9 == [I,I,D] -- posicionDeElemento 1 == [] posicionDeElemento :: Integer -> Posicion posicionDeElemento n = [f x | x <- tail (reverse (binario n))] where f 0 = I f 1 = D -- (binario n) es la lista de los dígitos de la representación binaria -- de n. Por ejemplo, -- binario 11 == [1,1,0,1] binario :: Integer -> [Integer] binario n | n < 2 = [n] | otherwise = n `mod` 2 : binario (n `div` 2) -- La comprobación es -- λ> quickCheck prop_elementoEnPosicion_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> length (show (elementoEnPosicion (replicate (3*10^5) D))) -- 90310 -- (1.96 secs, 11,518,771,016 bytes) -- λ> length (show (elementoEnPosicion2 (replicate (3*10^5) D))) -- 90310 -- (14.32 secs, 11,508,181,176 bytes)

Pensamiento

Las más hondas palabras
del sabio nos enseñan
lo que el silbar del viento cuando sopla
o el sonar de las aguas cuando ruedan.

Antonio Machado

Leer más →

Posiciones en árboles binarios completos

José A. Alonso, 5-diciembre-2018, Medio

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

                  1
                 /  \
                /    \
               /      \
              2        3
             / \      / \
            4   5    6   7
           / \    
          8   9

Los árboles binarios se puede representar mediante el siguiente tipo

   data Arbol = H
              | N Integer Arbol Arbol
     deriving (Show, Eq)

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 9 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

   data Movimiento = I | D deriving (Show, Eq)
   type Posicion   = [Movimiento]

Definir la función

   posicionDeElemento :: Integer -> Posicion

tal que (posicionDeElemento n) es la posición del elemento n en el árbol binario completo. Por ejemplo,

   posicionDeElemento 6  ==  [D,I]
   posicionDeElemento 7  ==  [D,D]
   posicionDeElemento 9  ==  [I,I,D]
   posicionDeElemento 1  ==  []
 
   length (posicionDeElemento (10^50000))  ==  166096

Soluciones

import Test.QuickCheck
 
data Arbol = H
           | N Integer Arbol Arbol
  deriving (Eq, Show)
 
data Movimiento = I | D deriving (Show, Eq)
 
type Posicion = [Movimiento]
 
-- 1ª solución
-- ===========
 
posicionDeElemento :: Integer -> Posicion
posicionDeElemento n =
  head (posiciones n (arbolBinarioCompleto n))
 
-- (arbolBinarioCompleto n) es el árbol binario completo con n
-- nodos. Por ejemplo, 
--    λ> arbolBinarioCompleto 4
--    N 1 (N 2 (N 4 H H) H) (N 3 H H)
--    λ> pPrint (arbolBinarioCompleto 9)
--    N 1
--      (N 2
--         (N 4
--            (N 8 H H)
--            (N 9 H H))
--         (N 5 H H))
--      (N 3
--         (N 6 H H)
--         (N 7 H H))
arbolBinarioCompleto :: Integer -> Arbol
arbolBinarioCompleto n = aux 1
  where aux i | i <= n    = N i (aux (2*i)) (aux (2*i+1))
              | otherwise = H
 
-- (posiciones n a) es la lista de las posiciones del elemento n
-- en el árbol a. Por ejemplo,
--    posiciones 9 (arbolBinarioCompleto 9)  ==  [[I,I,D]]
posiciones :: Integer -> Arbol -> [Posicion]
posiciones n a = aux n a [[]]
  where aux _ H _                      = []
        aux n (N x i d) cs | x == n    = cs ++ ps
                           | otherwise = ps
          where ps = map (I:) (aux n i cs) ++
                     map (D:) (aux n d cs)
 
-- 2ª solución
-- ===========
 
posicionDeElemento2 :: Integer -> Posicion
posicionDeElemento2 1 = []
posicionDeElemento2 n
  | even n    = posicionDeElemento2 (n `div` 2) ++ [I]
  | otherwise = posicionDeElemento2 (n `div` 2) ++ [D]
 
-- 3ª solución
-- ===========
 
posicionDeElemento3 :: Integer -> Posicion
posicionDeElemento3 = reverse . aux
  where aux 1 = []
        aux n | even n    = I : aux (n `div` 2) 
              | otherwise = D : aux (n `div` 2) 
 
-- 4ª solución
-- ===========
 
posicionDeElemento4 :: Integer -> Posicion
posicionDeElemento4 n =
  [f x | x <- tail (reverse (binario n))]
  where f 0 = I
        f 1 = D
 
-- (binario n) es la lista de los dígitos de la representación binaria
-- de n. Por ejemplo,
--    binario 11  ==  [1,1,0,1]
binario :: Integer -> [Integer]
binario n
  | n < 2     = [n]
  | otherwise = n `mod` 2 : binario (n `div` 2)
 
-- Equivalencia
-- ============
 
-- La propiedad es
prop_posicionDeElemento_equiv :: Positive Integer -> Bool
prop_posicionDeElemento_equiv (Positive n) =
  posicionDeElemento n == posicionDeElemento2 n &&
  posicionDeElemento n == posicionDeElemento3 n &&
  posicionDeElemento n == posicionDeElemento4 n
 
-- La comprobación es
--    λ> quickCheck prop_posicionDeElemento_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> posicionDeElemento (10^7)
--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]
--    (5.72 secs, 3,274,535,328 bytes)
--    λ> posicionDeElemento2 (10^7)
--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]
--    (0.01 secs, 189,560 bytes)
--    λ> posicionDeElemento3 (10^7)
--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]
--    (0.01 secs, 180,728 bytes)
--    λ> posicionDeElemento4 (10^7)
--    [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I]
--    (0.01 secs, 184,224 bytes)
--    
--    λ> length (posicionDeElemento2 (10^4000))
--    13287
--    (2.80 secs, 7,672,011,280 bytes)
--    λ> length (posicionDeElemento3 (10^4000))
--    13287
--    (0.03 secs, 19,828,744 bytes)
--    λ> length (posicionDeElemento4 (10^4000))
--    13287
--    (0.03 secs, 18,231,536 bytes)
--    
--    λ> length (posicionDeElemento3 (10^50000))
--    166096
--    (1.34 secs, 1,832,738,136 bytes)
--    λ> length (posicionDeElemento4 (10^50000))
--    166096
--    (1.70 secs, 1,812,806,080 bytes)

import Test.QuickCheck data Arbol = H | N Integer Arbol Arbol deriving (Eq, Show) data Movimiento = I | D deriving (Show, Eq) type Posicion = [Movimiento] -- 1ª solución -- =========== posicionDeElemento :: Integer -> Posicion posicionDeElemento n = head (posiciones n (arbolBinarioCompleto n)) -- (arbolBinarioCompleto n) es el árbol binario completo con n -- nodos. Por ejemplo, -- λ> arbolBinarioCompleto 4 -- N 1 (N 2 (N 4 H H) H) (N 3 H H) -- λ> pPrint (arbolBinarioCompleto 9) -- N 1 -- (N 2 -- (N 4 -- (N 8 H H) -- (N 9 H H)) -- (N 5 H H)) -- (N 3 -- (N 6 H H) -- (N 7 H H)) arbolBinarioCompleto :: Integer -> Arbol arbolBinarioCompleto n = aux 1 where aux i | i <= n = N i (aux (2*i)) (aux (2*i+1)) | otherwise = H -- (posiciones n a) es la lista de las posiciones del elemento n -- en el árbol a. Por ejemplo, -- posiciones 9 (arbolBinarioCompleto 9) == [[I,I,D]] posiciones :: Integer -> Arbol -> [Posicion] posiciones n a = aux n a [[]] where aux _ H _ = [] aux n (N x i d) cs | x == n = cs ++ ps | otherwise = ps where ps = map (I:) (aux n i cs) ++ map (D:) (aux n d cs) -- 2ª solución -- =========== posicionDeElemento2 :: Integer -> Posicion posicionDeElemento2 1 = [] posicionDeElemento2 n | even n = posicionDeElemento2 (n `div` 2) ++ [I] | otherwise = posicionDeElemento2 (n `div` 2) ++ [D] -- 3ª solución -- =========== posicionDeElemento3 :: Integer -> Posicion posicionDeElemento3 = reverse . aux where aux 1 = [] aux n | even n = I : aux (n `div` 2) | otherwise = D : aux (n `div` 2) -- 4ª solución -- =========== posicionDeElemento4 :: Integer -> Posicion posicionDeElemento4 n = [f x | x <- tail (reverse (binario n))] where f 0 = I f 1 = D -- (binario n) es la lista de los dígitos de la representación binaria -- de n. Por ejemplo, -- binario 11 == [1,1,0,1] binario :: Integer -> [Integer] binario n | n < 2 = [n] | otherwise = n `mod` 2 : binario (n `div` 2) -- Equivalencia -- ============ -- La propiedad es prop_posicionDeElemento_equiv :: Positive Integer -> Bool prop_posicionDeElemento_equiv (Positive n) = posicionDeElemento n == posicionDeElemento2 n && posicionDeElemento n == posicionDeElemento3 n && posicionDeElemento n == posicionDeElemento4 n -- La comprobación es -- λ> quickCheck prop_posicionDeElemento_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> posicionDeElemento (10^7) -- [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I] -- (5.72 secs, 3,274,535,328 bytes) -- λ> posicionDeElemento2 (10^7) -- [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I] -- (0.01 secs, 189,560 bytes) -- λ> posicionDeElemento3 (10^7) -- [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I] -- (0.01 secs, 180,728 bytes) -- λ> posicionDeElemento4 (10^7) -- [I,I,D,D,I,I,I,D,I,I,D,I,D,D,I,D,I,I,I,I,I,I,I] -- (0.01 secs, 184,224 bytes) -- -- λ> length (posicionDeElemento2 (10^4000)) -- 13287 -- (2.80 secs, 7,672,011,280 bytes) -- λ> length (posicionDeElemento3 (10^4000)) -- 13287 -- (0.03 secs, 19,828,744 bytes) -- λ> length (posicionDeElemento4 (10^4000)) -- 13287 -- (0.03 secs, 18,231,536 bytes) -- -- λ> length (posicionDeElemento3 (10^50000)) -- 166096 -- (1.34 secs, 1,832,738,136 bytes) -- λ> length (posicionDeElemento4 (10^50000)) -- 166096 -- (1.70 secs, 1,812,806,080 bytes)

Pensamiento

El ojo que ves no es
ojo porque tú lo veas;
es ojo porque te ve.

Antonio Machado

Leer más →

Último dígito no nulo del factorial

José A. Alonso, 13-noviembre-2018, Ejercicio

El factorial de 7 es

   7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

   ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

   ultimoNoNuloFactorial  7  == 4
   ultimoNoNuloFactorial 10  == 8
   ultimoNoNuloFactorial 12  == 6
   ultimoNoNuloFactorial 97  == 2
   ultimoNoNuloFactorial  0  == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Soluciones

import Test.QuickCheck
 
-- 1ª definición
-- =============
 
ultimoNoNuloFactorial :: Integer -> Integer
ultimoNoNuloFactorial n = ultimoNoNulo (factorial n)
 
-- (ultimoNoNulo n) es el último dígito no nulo de n. Por ejemplo,
--    ultimoNoNulo 5040  ==  4
ultimoNoNulo :: Integer -> Integer
ultimoNoNulo n
  | m /= 0    = m
  | otherwise = ultimoNoNulo (n `div` 10)
  where m = n `rem` 10
 
-- (factorial n) es el factorial de n. Por ejemplo,
--    factorial 7  ==  5040
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- 2ª definición
-- =============
 
ultimoNoNuloFactorial2 :: Integer -> Integer
ultimoNoNuloFactorial2 n = ultimoNoNulo2 (factorial n)
 
-- (ultimoNoNulo2 n) es el último dígito no nulo de n. Por ejemplo,
--    ultimoNoNulo 5040  ==  4
ultimoNoNulo2 :: Integer -> Integer
ultimoNoNulo2 n = read [head (dropWhile (=='0') (reverse (show n)))]
 
-- Comprobación
-- ============
 
-- La propiedad es
prop_ultimoNoNuloFactorial :: Integer -> Property
prop_ultimoNoNuloFactorial n = 
  n > 4 ==> even (ultimoNoNuloFactorial n)
 
-- La comprobación es
--    ghci> quickCheck prop_ultimoNoNuloFactorial
--    +++ OK, passed 100 tests.

Pensamiento

Incierto es, lo porvenir. ¿Quién sabe lo que va a pasar? Pero incierto es también lo pretérito. ¿Quién sabe lo que ha pasado? De suerte que ni el porvenir está escrito en ninguna parte, ni el pasado tampoco.

Antonio Machado

Leer más →

Sucesión fractal

José A. Alonso, 12-junio-2018, Avanzado

La sucesión fractal

   0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 
   10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

los términos pares forman la sucesión de los números naturales

     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

los términos impares forman la misma sucesión original

     0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

   sucFractal     :: [Integer]
   sumaSucFractal :: Integer -> Integer

tales que

sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo,

     take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
     sucFractal !! 30     == 15
     sucFractal !! (10^7) == 5000000

(sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,

     sumaSucFractal 10      == 13
     sumaSucFractal (10^5)  == 1666617368
     sumaSucFractal (10^10) == 16666666661668691669
     sumaSucFractal (10^15) == 166666666666666166673722792954
     sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
     length (show (sumaSucFractal (10^15000))) == 30000
     sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

Soluciones

-- 1ª definición de sucFractal
-- ===========================
 
sucFractal1 :: [Integer]
sucFractal1 = 
  map termino [0..]
 
-- (termino n) es el término n de la secuencia anterior. Por ejemplo,
--   termino 0            ==  0
--   termino 1            ==  0
--   map termino [0..10]  ==  [0,0,1,0,2,1,3,0,4,2,5]
termino :: Integer -> Integer
termino 0 = 0
termino n 
  | even n    = n `div` 2
  | otherwise = termino (n `div` 2)
 
-- 2ª definición de sucFractal
-- ===========================
 
sucFractal2 :: [Integer]
sucFractal2 =
    0 : 0 : mezcla [1..] (tail sucFractal2)
 
-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas
-- xs e ys. Por ejemplo,
--    take 10 (mezcla [0,2..] [0,-2..])  ==  [0,0,2,-2,4,-4,6,-6,8,-8]
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla (x:xs) (y:ys) =
  x : y : mezcla xs ys
 
-- Comparación de eficiencia de definiciones de sucFractal
-- =======================================================
 
--    λ> sum (take (10^6) sucFractal1)
--    166666169612
--    (5.56 secs, 842,863,264 bytes)
--    λ> sum (take (10^6) sucFractal2)
--    166666169612
--    (1.81 secs, 306,262,616 bytes)
 
-- En lo que sigue usaremos la 2ª definición
sucFractal :: [Integer]
sucFractal = sucFractal2
 
-- 1ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal1 :: Integer -> Integer
sumaSucFractal1 n =
  sum (map termino [0..n-1])
 
-- 2ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal2 :: Integer -> Integer
sumaSucFractal2 n =
    sum (take (fromIntegral n) sucFractal)
 
-- 3ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal3 :: Integer -> Integer
sumaSucFractal3 0 = 0
sumaSucFractal3 1 = 0
sumaSucFractal3 n
  | even n    = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)
  | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)
  where sumaN n = (n*(n-1)) `div` 2
 
-- Comparación de eficiencia de definiciones de sumaSucFractal
-- ===========================================================
 
--    λ> sumaSucFractal1 (10^6)
--    166666169612
--    (5.25 secs, 810,622,504 bytes)
--    λ> sumaSucFractal2 (10^6)
--    166666169612
--    (1.72 secs, 286,444,048 bytes)
--    λ> sumaSucFractal3 (10^6)
--    166666169612
--    (0.01 secs, 0 bytes)
--    
--    λ> sumaSucFractal2 (10^7)
--    16666661685034
--    (17.49 secs, 3,021,580,920 bytes)
--    λ> sumaSucFractal3 (10^7)
--    16666661685034
--    (0.01 secs, 0 bytes)

-- 1ª definición de sucFractal -- =========================== sucFractal1 :: [Integer] sucFractal1 = map termino [0..] -- (termino n) es el término n de la secuencia anterior. Por ejemplo, -- termino 0 == 0 -- termino 1 == 0 -- map termino [0..10] == [0,0,1,0,2,1,3,0,4,2,5] termino :: Integer -> Integer termino 0 = 0 termino n | even n = n `div` 2 | otherwise = termino (n `div` 2) -- 2ª definición de sucFractal -- =========================== sucFractal2 :: [Integer] sucFractal2 = 0 : 0 : mezcla [1..] (tail sucFractal2) -- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas -- xs e ys. Por ejemplo, -- take 10 (mezcla [0,2..] [0,-2..]) == [0,0,2,-2,4,-4,6,-6,8,-8] mezcla :: [Integer] -> [Integer] -> [Integer] mezcla (x:xs) (y:ys) = x : y : mezcla xs ys -- Comparación de eficiencia de definiciones de sucFractal -- ======================================================= -- λ> sum (take (10^6) sucFractal1) -- 166666169612 -- (5.56 secs, 842,863,264 bytes) -- λ> sum (take (10^6) sucFractal2) -- 166666169612 -- (1.81 secs, 306,262,616 bytes) -- En lo que sigue usaremos la 2ª definición sucFractal :: [Integer] sucFractal = sucFractal2 -- 1ª definición de sumaSucFractal -- =============================== sumaSucFractal1 :: Integer -> Integer sumaSucFractal1 n = sum (map termino [0..n-1]) -- 2ª definición de sumaSucFractal -- =============================== sumaSucFractal2 :: Integer -> Integer sumaSucFractal2 n = sum (take (fromIntegral n) sucFractal) -- 3ª definición de sumaSucFractal -- =============================== sumaSucFractal3 :: Integer -> Integer sumaSucFractal3 0 = 0 sumaSucFractal3 1 = 0 sumaSucFractal3 n | even n = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2) | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2) where sumaN n = (n*(n-1)) `div` 2 -- Comparación de eficiencia de definiciones de sumaSucFractal -- =========================================================== -- λ> sumaSucFractal1 (10^6) -- 166666169612 -- (5.25 secs, 810,622,504 bytes) -- λ> sumaSucFractal2 (10^6) -- 166666169612 -- (1.72 secs, 286,444,048 bytes) -- λ> sumaSucFractal3 (10^6) -- 166666169612 -- (0.01 secs, 0 bytes) -- -- λ> sumaSucFractal2 (10^7) -- 16666661685034 -- (17.49 secs, 3,021,580,920 bytes) -- λ> sumaSucFractal3 (10^7) -- 16666661685034 -- (0.01 secs, 0 bytes)

Referencia

+ [Fractal sequences and restricted Nim](http://bit.ly/1WX1IjB) por Lionel Levine.

Leer más →

Números superpares

José A. Alonso, 12-abril-2018, Inicial

Definir la función

   superpar :: Int -> Bool

tal que (superpar n) se verifica si n es un número par tal que todos sus dígitos son pares. Por ejemplo,

   superpar 426  ==  True
   superpar 456  ==  False

Soluciones

-- 1ª definición (por recursión)
superpar :: Int -> Bool
superpar n | n < 10    = even n
           | otherwise = even n && superpar (n `div` 10)
 
-- 2ª definición (por comprensión):
superpar2 :: Int -> Bool
superpar2 n = and [even d | d <- digitos n]
 
digitos :: Int -> [Int]
digitos n = [read [d] | d <- show n]
 
-- 3ª definición (por recursión sobre los dígitos):
superpar3 :: Int -> Bool
superpar3 n = sonPares (digitos n)
    where sonPares []     = True
          sonPares (d:ds) = even d && sonPares ds
 
-- la función sonPares se puede definir por plegado:
superpar3' :: Int -> Bool
superpar3' n = sonPares (digitos n)
    where sonPares ds = foldr ((&&) . even) True ds
 
-- 4ª definición (con all):
superpar4 :: Int -> Bool
superpar4 n = all even (digitos n)
 
-- 5ª definición (con filter):
superpar5 :: Int -> Bool
superpar5 n = filter even (digitos n) == digitos n
 
-- 6ª definición (con filter):
superpar6 :: Int -> Bool
superpar6 n = all (`elem` "02468") (show n)

Leer más →

Etiqueta: even

Elemento del árbol binario completo según su posición

Soluciones

Pensamiento

Posiciones en árboles binarios completos

Soluciones

Pensamiento

Último dígito no nulo del factorial

Soluciones

Pensamiento

Sucesión fractal

Soluciones

Referencia

Números superpares

Soluciones

Subscribe to Blog via Email

Entradas recientes

Etiquetas

junio 2023
L	M	X	J	V	S	D
« May
			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