Exercitium

Árboles acotados

PorJosé A. Alonso 27-enero-20213-febrero-2021

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, el árbol

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

/ \

4 9

/ \ / \

1 3 5 6

se puede representar por

   N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

1	N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

Un árbol está acotado por un conjunto ys si todos los valores de sus hojas y sus nodos pertenecen a ys. Por ejemplo, el árbol anterior está acotado por [1..10] pero no lo está por [1..7].

Un árbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes árboles sólo son monovalorados los dos primeros

    5          9           5          9
   / \        / \         / \        / \
  5   5      9   9       5   6      9   7
                / \                    / \
               9   9                  9   9

5 9 5 9

/ \ / \ / \ / \

5 5 9 9 5 6 9 7

/ \ / \

9 9 9 9

Definir las funciones

   acotado :: Eq a => Arbol a -> [a] -> Bool
   monovalorados :: Arbol -> [Arbol]

1 2	acotado :: Eq a => Arbol a -> [a] -> Bool monovalorados :: Arbol -> [Arbol]

tales que

(acotado a ys) se verifica si a está acotado por ys. Por ejemplo,

     acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..10] == True
     acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..7]  == False

1 2	acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..10] == True acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..7] == False

(monovalorado a) se verifica si a es monovalorado. Por ejemplo,

     monovalorado (N 5 (H 5) (H 5))              ==  True
     monovalorado (N 5 (H 5) (H 6))              ==  False
     monovalorado (N 9 (H 9) (N 9 (H 9) (H 9)))  ==  True
     monovalorado (N 9 (H 9) (N 7 (H 9) (H 9)))  ==  False
     monovalorado (N 9 (H 9) (N 9 (H 7) (H 9)))  ==  False

monovalorado (N 5 (H 5) (H 5)) == True

monovalorado (N 5 (H 5) (H 6)) == False

monovalorado (N 9 (H 9) (N 9 (H 9) (H 9))) == True

monovalorado (N 9 (H 9) (N 7 (H 9) (H 9))) == False

monovalorado (N 9 (H 9) (N 9 (H 7) (H 9))) == False

Soluciones

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving Show

acotado :: Eq a => Arbol a -> [a] -> Bool
acotado (H x) ys     = x `elem` ys
acotado (N x i d) ys = x `elem` ys && acotado i ys && acotado d ys

monovalorado :: Eq a => Arbol a -> Bool
monovalorado (H _) = True
monovalorado (N x i d) = acotado i [x] && acotado d [x]

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

acotado :: Eq a => Arbol a -> [a] -> Bool

acotado (H x) ys = x `elem` ys

acotado (N x i d) ys = x `elem` ys && acotado i ys && acotado d ys

monovalorado :: Eq a => Arbol a -> Bool

monovalorado (H _) = True

monovalorado (N x i d) = acotado i [x] && acotado d [x]

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Limitación del número de repeticiones

PorJosé A. Alonso 26-enero-20212-febrero-2021

Definir la función

   conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a]

1	conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a]

tal que (conRepeticionesAcotadas xs n) es una lista que contiene cada elemento de xs como máximo n veces sin reordenar (se supone que n es un número positivo).. Por ejemplo,

   conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 1  ==  [1,2,3,5]
   conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 2  ==  [1,2,3,1,2,3,5]
   conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 3  ==  [1,2,3,1,2,1,3,2,3,5]
   conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 4  ==  [1,2,3,1,2,1,3,2,3,5]

conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 1 == [1,2,3,5]

conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 2 == [1,2,3,1,2,3,5]

conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 3 == [1,2,3,1,2,1,3,2,3,5]

conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 4 == [1,2,3,1,2,1,3,2,3,5]

Soluciones

import Data.List (foldl')
import Data.Maybe (fromJust, isNothing)
import Test.QuickCheck (Property, (==>),quickCheck)

-- 1ª solución
-- ===========

conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a]
conRepeticionesAcotadas xs n = reverse (aux [] xs)
  where aux zs []     = zs
        aux zs (y:ys) | m < n     = aux (y:zs) ys
                      | otherwise = aux zs ys
          where m = nOcurrencias y zs

-- (nOcurrencias x ys) es el número de ocurrencias de x en ys. Por
-- ejemplo,
--    nOcurrencias 7 [7,2,7,7,5]  ==  3
nOcurrencias :: Eq a => a -> [a] -> Int
nOcurrencias x ys = length (filter (== x) ys)

-- Se puede simplificar la definición de nOcurrencias:
nOcurrencias2 :: Eq a => a -> [a] -> Int
nOcurrencias2 x = length . filter (== x)

-- 2ª solución
-- ===========

conRepeticionesAcotadas2 :: Eq a => [a] -> Int -> [a]
conRepeticionesAcotadas2 xs n = reverse (foldl' aux [] xs)
  where aux zs y | m < n     = y:zs
                 | otherwise = zs
          where m = nOcurrencias y zs

-- 3ª solución
-- ===========

conRepeticionesAcotadas3 :: Eq a => [a] -> Int -> [a]
conRepeticionesAcotadas3 xs n = reverse (aux [] [] xs)
  where aux as _ []      = as
        aux as bs (y:ys) | y `elem` bs = aux as bs ys
                         | m < n       = aux (y:as) bs ys
                         | otherwise   = aux as (y:bs) ys
          where m = nOcurrencias y as

-- 4ª solución
-- ===========

conRepeticionesAcotadas4 :: Eq a => [a] -> Int -> [a]
conRepeticionesAcotadas4 xs n = aux xs []
  where aux [] _      = []
        aux (y:ys) ps | r == Nothing = y : aux ys ((y,1) : ps)
                      | m < n        = y : aux ys ((y,m+1) : ps)
                      | otherwise    = aux ys ps
                      where r = busca y ps
                            Just m = r

-- (busca x ps) es justamente la segunda componente del primer par de ps
-- cuya primera componente es xs, si ps tiene algún par cuya primera
-- componente es x; y Nothing en caso contrario. Por ejemplo,
--    busca 'a' [('b',2),('a',3),('a',1)]  ==  Just 3
--    busca 'c' [('b',2),('a',3),('a',1)]  ==  Nothing
busca :: Eq a => a -> [(a,b)] -> Maybe b
busca x ps
  | null ys   = Nothing
  | otherwise = Just (head ys)
  where ys = [n | (y,n) <- ps, y == x]

-- 5ª solución
-- ===========

conRepeticionesAcotadas5 :: Eq a => [a] -> Int -> [a]
conRepeticionesAcotadas5 xs n = aux xs []
  where aux [] _      = []
        aux (y:ys) ps | isNothing r = y : aux ys ((y,1) : ps)
                      | m < n       = y : aux ys ((y,m+1) : ps)
                      | otherwise   = aux ys ps
                      where r = lookup y ps
                            m = fromJust r

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_conRepeticionesAcotadas :: [Int] -> Int -> Property
prop_conRepeticionesAcotadas xs n =
  n > 0 ==>
  all (==(conRepeticionesAcotadas xs n))
      [ conRepeticionesAcotadas2 xs n
      , conRepeticionesAcotadas3 xs n
      , conRepeticionesAcotadas4 xs n
      , conRepeticionesAcotadas5 xs n]

-- La comprobación es
--    λ> quickCheck prop_conRepeticionesAcotadas
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (conRepeticionesAcotadas (concat [[1..n] | n <- [1..500]]) 2)
--    999
--    (5.14 secs, 64,372,768 bytes)
--    λ> length (conRepeticionesAcotadas2 (concat [[1..n] | n <- [1..500]]) 2)
--    999
--    (4.95 secs, 62,322,880 bytes)
--    λ> length (conRepeticionesAcotadas3 (concat [[1..n] | n <- [1..500]]) 2)
--    999
--    (0.38 secs, 38,764,952 bytes)
--    λ> length (conRepeticionesAcotadas4 (concat [[1..n] | n <- [1..500]]) 2)
--    999
--    (5.66 secs, 2,429,904,144 bytes)
--    λ> length (conRepeticionesAcotadas5 (concat [[1..n] | n <- [1..500]]) 2)
--    999
--    (0.68 secs, 48,536,872 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

import Data.List (foldl')

import Data.Maybe (fromJust, isNothing)

import Test.QuickCheck (Property, (==>),quickCheck)

-- 1ª solución

-- ===========

conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a]

conRepeticionesAcotadas xs n = reverse (aux [] xs)

where aux zs [] = zs

aux zs (y:ys) | m < n = aux (y:zs) ys

| otherwise = aux zs ys

where m = nOcurrencias y zs

-- (nOcurrencias x ys) es el número de ocurrencias de x en ys. Por

-- ejemplo,

-- nOcurrencias 7 [7,2,7,7,5] == 3

nOcurrencias :: Eq a => a -> [a] -> Int

nOcurrencias x ys = length (filter (== x) ys)

-- Se puede simplificar la definición de nOcurrencias:

nOcurrencias2 :: Eq a => a -> [a] -> Int

nOcurrencias2 x = length . filter (== x)

-- 2ª solución

-- ===========

conRepeticionesAcotadas2 :: Eq a => [a] -> Int -> [a]

conRepeticionesAcotadas2 xs n = reverse (foldl' aux [] xs)

where aux zs y | m < n = y:zs

| otherwise = zs

where m = nOcurrencias y zs

-- 3ª solución

-- ===========

conRepeticionesAcotadas3 :: Eq a => [a] -> Int -> [a]

conRepeticionesAcotadas3 xs n = reverse (aux [] [] xs)

where aux as _ [] = as

aux as bs (y:ys) | y `elem` bs = aux as bs ys

| m < n = aux (y:as) bs ys

| otherwise = aux as (y:bs) ys

where m = nOcurrencias y as

-- 4ª solución

-- ===========

conRepeticionesAcotadas4 :: Eq a => [a] -> Int -> [a]

conRepeticionesAcotadas4 xs n = aux xs []

where aux [] _ = []

aux (y:ys) ps | r == Nothing = y : aux ys ((y,1) : ps)

| m < n = y : aux ys ((y,m+1) : ps)

| otherwise = aux ys ps

where r = busca y ps

Just m = r

-- (busca x ps) es justamente la segunda componente del primer par de ps

-- cuya primera componente es xs, si ps tiene algún par cuya primera

-- componente es x; y Nothing en caso contrario. Por ejemplo,

-- busca 'a' [('b',2),('a',3),('a',1)] == Just 3

-- busca 'c' [('b',2),('a',3),('a',1)] == Nothing

busca :: Eq a => a -> [(a,b)] -> Maybe b

busca x ps

| null ys = Nothing

| otherwise = Just (head ys)

where ys = [n | (y,n) <- ps, y == x]

-- 5ª solución

-- ===========

conRepeticionesAcotadas5 :: Eq a => [a] -> Int -> [a]

conRepeticionesAcotadas5 xs n = aux xs []

where aux [] _ = []

aux (y:ys) ps | isNothing r = y : aux ys ((y,1) : ps)

| m < n = y : aux ys ((y,m+1) : ps)

| otherwise = aux ys ps

where r = lookup y ps

m = fromJust r

-- Equivalencia de las definiciones

-- ================================

-- La propiedad es

prop_conRepeticionesAcotadas :: [Int] -> Int -> Property

prop_conRepeticionesAcotadas xs n =

n > 0 ==>

all (==(conRepeticionesAcotadas xs n))

[ conRepeticionesAcotadas2 xs n

, conRepeticionesAcotadas3 xs n

, conRepeticionesAcotadas4 xs n

, conRepeticionesAcotadas5 xs n]

-- La comprobación es

-- λ> quickCheck prop_conRepeticionesAcotadas

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (conRepeticionesAcotadas (concat [[1..n] | n <- [1..500]]) 2)

-- 999

-- (5.14 secs, 64,372,768 bytes)

-- λ> length (conRepeticionesAcotadas2 (concat [[1..n] | n <- [1..500]]) 2)

-- 999

-- (4.95 secs, 62,322,880 bytes)

-- λ> length (conRepeticionesAcotadas3 (concat [[1..n] | n <- [1..500]]) 2)

-- 999

-- (0.38 secs, 38,764,952 bytes)

-- λ> length (conRepeticionesAcotadas4 (concat [[1..n] | n <- [1..500]]) 2)

-- 999

-- (5.66 secs, 2,429,904,144 bytes)

-- λ> length (conRepeticionesAcotadas5 (concat [[1..n] | n <- [1..500]]) 2)

-- 999

-- (0.68 secs, 48,536,872 bytes)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Potencias de dos más cercanas

PorJosé A. Alonso 25-enero-20211-febrero-2021

Definir la función

   potenciasDeDosMasCercanas :: [Integer] -> [Integer]

1	potenciasDeDosMasCercanas :: [Integer] -> [Integer]

tal que (potenciasDeDosMasCercanas xs) es la lista sustituyendo cada elemento de xs por su potencia de dos más cercana (en el caso de que haya dos equidistantes se elige la menor). Por ejemplo,

   potenciasDeDosMasCercanas2 [6,7,8,9,2021]  ==  [4,8,8,8,2048]

1	potenciasDeDosMasCercanas2 [6,7,8,9,2021] == [4,8,8,8,2048]

Soluciones

-- 1ª solución
-- ===========

potenciasDeDosMasCercanas :: [Integer] -> [Integer]
potenciasDeDosMasCercanas = map potenciaDeDosMasCercana

-- (potenciaDeDosMasCercana n) es la potencia de dos más cercana (en el
-- caso de que haya dos equidistantes se elige la menor). Por ejemplo,
--    potenciaDeDosMasCercana 6  ==  4
--    potenciaDeDosMasCercana 7  ==  8
--    potenciaDeDosMasCercana 8  ==  8
--    potenciaDeDosMasCercana 9  ==  8
potenciaDeDosMasCercana :: Integer -> Integer
potenciaDeDosMasCercana n
  | dx <= dy  = x
  | otherwise = y
  where (x,y) = potenciasDeDosCercanas n
        dx    = n - x
        dy    = y - n

-- (potenciasDeDosMasCercanas n) es par formado por las dos potencias de
-- dos más cercana a n. Por ejemplo,
--    potenciasDeDosCercanas 6  ==  (4,8)
--    potenciasDeDosCercanas 7  ==  (4,8)
--    potenciasDeDosCercanas 8  ==  (4,8)
--    potenciasDeDosCercanas 9  ==  (8,16)
potenciasDeDosCercanas :: Integer -> (Integer, Integer)
potenciasDeDosCercanas n =
  (x `div` 2, x)
  where x = menorPotenciaDeDosMayorOIgual n

-- (menorPotenciaDeDosMayorOIgual n) es la menor potencia de dos mayor o
-- igual que n. Por ejemplo,
--    menorPotenciaDeDosMayorOIgual 6  ==  8
--    menorPotenciaDeDosMayorOIgual 8  ==  8
menorPotenciaDeDosMayorOIgual :: Integer -> Integer
menorPotenciaDeDosMayorOIgual n =
  head [2^x | x <- [0..], 2^x >= n]

-- 2ª solución
-- ===========

potenciasDeDosMasCercanas2 :: [Integer] -> [Integer]
potenciasDeDosMasCercanas2 = map potenciaDeDosMasCercana2

potenciaDeDosMasCercana2 :: Integer -> Integer
potenciaDeDosMasCercana2 n =
  snd (min (n-x,x) (y-n,y))
  where (x,y) = potenciasDeDosCercanas2 n

potenciasDeDosCercanas2 :: Integer -> (Integer, Integer)
potenciasDeDosCercanas2 n = (x `div` 2, x)
  where (x:_) = dropWhile (<n) potenciasDeDos

-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,
--    take 11 potenciasDeDos  ==  [1,2,4,8,16,32,64,128,256,512,1024]
potenciasDeDos :: [Integer]
potenciasDeDos = iterate (*2) 1

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> maximum (potenciasDeDosMasCercanas [10^5..10^6])
--    1048576
--    (18.28 secs, 20,835,181,624 bytes)
--    λ> maximum (potenciasDeDosMasCercanas2 [10^5..10^6])
--    1048576
--    (2.44 secs, 830,307,736 bytes)

-- 1ª solución

-- ===========

potenciasDeDosMasCercanas :: [Integer] -> [Integer]

potenciasDeDosMasCercanas = map potenciaDeDosMasCercana

-- (potenciaDeDosMasCercana n) es la potencia de dos más cercana (en el

-- caso de que haya dos equidistantes se elige la menor). Por ejemplo,

-- potenciaDeDosMasCercana 6 == 4

-- potenciaDeDosMasCercana 7 == 8

-- potenciaDeDosMasCercana 8 == 8

-- potenciaDeDosMasCercana 9 == 8

potenciaDeDosMasCercana :: Integer -> Integer

potenciaDeDosMasCercana n

| dx <= dy = x

| otherwise = y

where (x,y) = potenciasDeDosCercanas n

dx = n - x

dy = y - n

-- (potenciasDeDosMasCercanas n) es par formado por las dos potencias de

-- dos más cercana a n. Por ejemplo,

-- potenciasDeDosCercanas 6 == (4,8)

-- potenciasDeDosCercanas 7 == (4,8)

-- potenciasDeDosCercanas 8 == (4,8)

-- potenciasDeDosCercanas 9 == (8,16)

potenciasDeDosCercanas :: Integer -> (Integer, Integer)

potenciasDeDosCercanas n =

(x `div` 2, x)

where x = menorPotenciaDeDosMayorOIgual n

-- (menorPotenciaDeDosMayorOIgual n) es la menor potencia de dos mayor o

-- igual que n. Por ejemplo,

-- menorPotenciaDeDosMayorOIgual 6 == 8

-- menorPotenciaDeDosMayorOIgual 8 == 8

menorPotenciaDeDosMayorOIgual :: Integer -> Integer

menorPotenciaDeDosMayorOIgual n =

head [2^x | x <- [0..], 2^x >= n]

-- 2ª solución

-- ===========

potenciasDeDosMasCercanas2 :: [Integer] -> [Integer]

potenciasDeDosMasCercanas2 = map potenciaDeDosMasCercana2

potenciaDeDosMasCercana2 :: Integer -> Integer

potenciaDeDosMasCercana2 n =

snd (min (n-x,x) (y-n,y))

where (x,y) = potenciasDeDosCercanas2 n

potenciasDeDosCercanas2 :: Integer -> (Integer, Integer)

potenciasDeDosCercanas2 n = (x `div` 2, x)

where (x:_) = dropWhile (<n) potenciasDeDos

-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,

-- take 11 potenciasDeDos == [1,2,4,8,16,32,64,128,256,512,1024]

potenciasDeDos :: [Integer]

potenciasDeDos = iterate (*2) 1

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> maximum (potenciasDeDosMasCercanas [10^5..10^6])

-- 1048576

-- (18.28 secs, 20,835,181,624 bytes)

-- λ> maximum (potenciasDeDosMasCercanas2 [10^5..10^6])

-- 1048576

-- (2.44 secs, 830,307,736 bytes)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

La serie 1 – 2 + 3 – 4 + ···

PorJosé A. Alonso 22-enero-202129-enero-2021

En este ejercicio se considerará la serie

   1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 10 + ···

1	1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 10 + ···

Definir las funciones

   serie     :: [Integer]
   sumaSerie :: Integer -> Integer

1 2	serie :: [Integer] sumaSerie :: Integer -> Integer

tales que

serie es lalista de los términos de la serie anterior; es decir,

     take 7 serie  ==  [1,-2,3,-4,5,-6,7]

1	take 7 serie == [1,-2,3,-4,5,-6,7]

(sumaSerie n) es la suma de los n primeros términos de la serie. Por ejemplo,

     sumaSerie 5     ==  3
     sumaSerie 6     ==  -3
     sumaSerie 2021  ==  1011
     length (show (sumaSerie (10^1000)))  ==  1001

sumaSerie 5 == 3

sumaSerie 6 == -3

sumaSerie 2021 == 1011

length (show (sumaSerie (10^1000))) == 1001

Comprobar con QuickCheck que

la suma de la serie se puede hacer tan grande como se desee; es decir, que para todo número a existe un n tal que la suma de los n primeros términos de la serie es mayor que a;
la suma de la serie se puede hacer tan pequeña como se desee; es decir, que para todo número a existe un n tal que la suma de los n primeros términos de la serie es menor que a.

Soluciones

import Data.List (cycle, genericTake)
import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª definición de serie
-- ======================

serie :: [Integer]
serie = [(-1)^(n-1) * n | n <- [1..]]

-- 2ª definición de serie
-- ======================

serie2 :: [Integer]
serie2 = zipWith (*) (cycle [1,-1]) [1..]

-- 3ª definición de serie
-- ======================

serie3 :: [Integer]
serie3 = zipWith ($) (cycle [id,negate]) [1..]

-- 1ª definición de sumaSerie
-- ==========================

sumaSerie :: Integer -> Integer
sumaSerie n = sum (genericTake n serie)

-- 2ª definición sumaSerie
-- =======================

-- La 2ª definición se basa en la siguiente observación
-- + Si n es par, entonces
--        1 - 2 + 3 - 4 + 5 - 6 + ··· + (n-1) - n
--      = (1 - 2) + (3 - 4) + (5 - 6) + ··· + ((n-1) - n)
--      = -1      - 1       - 1       - ··· - 1
--      = -1 * n/2
-- + Si n es impar, entonces
--        1 - 2 + 3 - 4 + 5 - 6 + ··· + (n-2) - (n-1) + n
--      = (1 - 2) + (3 - 4) + (5 - 6) + ··· + ((n-2) - (n-1)) + n
--      = -1      - 1       - 1       - ··· - 1               + n
--      = -1 * (n-1)/2 + n
--      = n - ((n-1)/2)

sumaSerie2 :: Integer -> Integer
sumaSerie2 n
  | even n    = -(n `div` 2)
  | otherwise = n - ((n - 1) `div` 2)


-- 3ª definición sumaSerie
-- =======================

-- La 3ª definición se basa en la siguiente observación
--    λ> [sumaSerie n | n <- [1..20]]
--    [1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10]

sumaSerie3 :: Integer -> Integer
sumaSerie3 n = ((-1)^(n-1)*(2*n+1)+1) `div` 4

-- Equivalencia
-- ============

-- La propiedad es
prop_sumaSerie_equiv :: Integer -> Property
prop_sumaSerie_equiv n =
  n > 0 ==>
  sumaSerie  n == sumaSerie2 n &&
  sumaSerie2 n == sumaSerie3 n

-- La comprobación es
--    λ> quickCheck prop_sumaSerie_equiv
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> sumaSerie (10^6)
--    -500000
--    (3.34 secs, 5,106,633,208 bytes)
--    λ> sumaSerie2 (10^6)
--    -500000
--    (0.01 secs, 102,600 bytes)
--    λ> sumaSerie3 (10^6)
--    -500000
--    (0.02 secs, 110,976 bytes)
--    λ> sumaSerie3 (10^6)
--    -500000

-- Propiedad
-- =========

-- La propiedad es
prop_sumaSerie :: Integer -> Bool
prop_sumaSerie a =
  any (> a) sumas && any (< a) sumas
  where sumas = [sumaSerie2 n | n <- [1..]]

-- La comprobación es
--    λ> quickCheck prop_sumaSerie
--    +++ OK, passed 100 tests.

100

101

import Data.List (cycle, genericTake)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª definición de serie

-- ======================

serie :: [Integer]

serie = [(-1)^(n-1) * n | n <- [1..]]

-- 2ª definición de serie

-- ======================

serie2 :: [Integer]

serie2 = zipWith (*) (cycle [1,-1]) [1..]

-- 3ª definición de serie

-- ======================

serie3 :: [Integer]

serie3 = zipWith ($) (cycle [id,negate]) [1..]

-- 1ª definición de sumaSerie

-- ==========================

sumaSerie :: Integer -> Integer

sumaSerie n = sum (genericTake n serie)

-- 2ª definición sumaSerie

-- =======================

-- La 2ª definición se basa en la siguiente observación

-- + Si n es par, entonces

-- 1 - 2 + 3 - 4 + 5 - 6 + ··· + (n-1) - n

-- = (1 - 2) + (3 - 4) + (5 - 6) + ··· + ((n-1) - n)

-- = -1 - 1 - 1 - ··· - 1

-- = -1 * n/2

-- + Si n es impar, entonces

-- 1 - 2 + 3 - 4 + 5 - 6 + ··· + (n-2) - (n-1) + n

-- = (1 - 2) + (3 - 4) + (5 - 6) + ··· + ((n-2) - (n-1)) + n

-- = -1 - 1 - 1 - ··· - 1 + n

-- = -1 * (n-1)/2 + n

-- = n - ((n-1)/2)

sumaSerie2 :: Integer -> Integer

sumaSerie2 n

| even n = -(n `div` 2)

| otherwise = n - ((n - 1) `div` 2)

-- 3ª definición sumaSerie

-- =======================

-- La 3ª definición se basa en la siguiente observación

-- λ> [sumaSerie n | n <- [1..20]]

-- [1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10]

sumaSerie3 :: Integer -> Integer

sumaSerie3 n = ((-1)^(n-1)*(2*n+1)+1) `div` 4

-- Equivalencia

-- ============

-- La propiedad es

prop_sumaSerie_equiv :: Integer -> Property

prop_sumaSerie_equiv n =

n > 0 ==>

sumaSerie n == sumaSerie2 n &&

sumaSerie2 n == sumaSerie3 n

-- La comprobación es

-- λ> quickCheck prop_sumaSerie_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> sumaSerie (10^6)

-- -500000

-- (3.34 secs, 5,106,633,208 bytes)

-- λ> sumaSerie2 (10^6)

-- -500000

-- (0.01 secs, 102,600 bytes)

-- λ> sumaSerie3 (10^6)

-- -500000

-- (0.02 secs, 110,976 bytes)

-- λ> sumaSerie3 (10^6)

-- -500000

-- Propiedad

-- =========

-- La propiedad es

prop_sumaSerie :: Integer -> Bool

prop_sumaSerie a =

any (> a) sumas && any (< a) sumas

where sumas = [sumaSerie2 n | n <- [1..]]

-- La comprobación es

-- λ> quickCheck prop_sumaSerie

-- +++ OK, passed 100 tests.

Clausura respecto del valor absoluto de las diferencias

PorJosé A. Alonso 21-enero-202128-enero-2021

Dado un conjunto de números enteros positivos S su clausura del valor absoluto de la diferencia de pares es el menor conjunto T tal que T contiene a S y para cualquier par de elementos x e y de T (con x distinto de y) el valor absoluto de (x-y) también es un elemento de T. Por ejemplo, si S = {12, 30}, entonces

12 ∈ T, porque 12 ∈ S
30 ∈ T, porque 20 ∈ S
18 = |12 – 30| ∈ T
6 = |18 – 12| ∈ T
24 = |30 – 6| ∈ T

Por tanto, T = {12, 30, 18, 6, 24}.

Definir las funciones

   clausura :: [Int] -> [Int]
   longitudClausura :: [Int] -> Int

1 2	clausura :: [Int] -> [Int] longitudClausura :: [Int] -> Int

tales que

(clausura xs) es la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,

     clausura [12,30]  ==  [12,30,18,6,24]
     clausura [3,5,2]  ==  [3,5,2,1,4]

1 2	clausura [12,30] == [12,30,18,6,24] clausura [3,5,2] == [3,5,2,1,4]

(longitudClausura xs) es el número de elementos de la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,

     longitudClausura [12,30]        ==  5
     longitudClausura [3,5,2]        ==  5
     longitudClausura [3,23..10^6]   ==  999983

longitudClausura [12,30] == 5

longitudClausura [3,5,2] == 5

longitudClausura [3,23..10^6] == 999983

Soluciones

import Data.List (nub, sort, union)
import Test.QuickCheck

-- Definición de clausura
-- ======================

clausura :: [Int] -> [Int]
clausura xs
  | contenida ys xs = xs
  | otherwise       = clausura (union xs ys)
  where ys = diferencias xs

-- (diferencias xs) es el conjunto de los valores absolutos de las
-- diferencias de pares de elementos distintos de xs. Por ejemplo,
--    diferencias [3,7,11]  ==  [4,8]
diferencias :: [Int] -> [Int]
diferencias xs =
  nub [x - y | x <- xs
             , y <- xs
             , x > y]

-- (contenida xs ys) se verifica si la lista xs esta contenida en
-- ys. Por ejemplo,
--    contenida [2,3] [3,5,2]  ==  True
--    contenida [2,3] [3,5,7]  ==  False
contenida :: [Int] -> [Int] -> Bool
contenida xs ys =
  all (`elem` ys) xs

-- 1ª definición de longitudClausura
-- =================================

longitudClausura :: [Int] -> Int
longitudClausura = length . clausura

-- 2ª definición de longitudClausura
-- =================================

--    longitudClausura2 [3,23..10^6]  ==  999983
longitudClausura2 :: [Int] -> Int
longitudClausura2 xs =
  maximum xs `div` mcd xs

-- (mcd xs) es el máximo común divisor de los elememtos de xs. Por
-- ejemplo,
--    mcd [12, 60]      ==  12
--    mcd [12, 60, 42]  ==  6
mcd :: [Int] -> Int
mcd = foldl1 gcd

-- Equivalencia
-- ============

-- La propiedd de equivalencia es
prop_clausura :: [Int] -> Property
prop_clausura xs =
  not (null xs) ==>
  longitudClausura ys == longitudClausura2 ys
  where ys = nub (map ((+1) . abs) xs)

-- La comprobación es
--    λ> quickCheck prop_clausura
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> longitudClausura [3,23..10^3]
--    983
--    (2.22 secs, 239,761,904 bytes)
--    λ> longitudClausura2 [3,23..10^3]
--    983
--    (0.01 secs, 118,968 bytes)

import Data.List (nub, sort, union)

import Test.QuickCheck

-- Definición de clausura

-- ======================

clausura :: [Int] -> [Int]

clausura xs

| contenida ys xs = xs

| otherwise = clausura (union xs ys)

where ys = diferencias xs

-- (diferencias xs) es el conjunto de los valores absolutos de las

-- diferencias de pares de elementos distintos de xs. Por ejemplo,

-- diferencias [3,7,11] == [4,8]

diferencias :: [Int] -> [Int]

diferencias xs =

nub [x - y | x <- xs

, y <- xs

, x > y]

-- (contenida xs ys) se verifica si la lista xs esta contenida en

-- ys. Por ejemplo,

-- contenida [2,3] [3,5,2] == True

-- contenida [2,3] [3,5,7] == False

contenida :: [Int] -> [Int] -> Bool

contenida xs ys =

all (`elem` ys) xs

-- 1ª definición de longitudClausura

-- =================================

longitudClausura :: [Int] -> Int

longitudClausura = length . clausura

-- 2ª definición de longitudClausura

-- =================================

-- longitudClausura2 [3,23..10^6] == 999983

longitudClausura2 :: [Int] -> Int

longitudClausura2 xs =

maximum xs `div` mcd xs

-- (mcd xs) es el máximo común divisor de los elememtos de xs. Por

-- ejemplo,

-- mcd [12, 60] == 12

-- mcd [12, 60, 42] == 6

mcd :: [Int] -> Int

mcd = foldl1 gcd

-- Equivalencia

-- ============

-- La propiedd de equivalencia es

prop_clausura :: [Int] -> Property

prop_clausura xs =

not (null xs) ==>

longitudClausura ys == longitudClausura2 ys

where ys = nub (map ((+1) . abs) xs)

-- La comprobación es

-- λ> quickCheck prop_clausura

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> longitudClausura [3,23..10^3]

-- 983

-- (2.22 secs, 239,761,904 bytes)

-- λ> longitudClausura2 [3,23..10^3]

-- 983

-- (0.01 secs, 118,968 bytes)

Árboles acotados

Soluciones

Nuevas soluciones

Limitación del número de repeticiones

Soluciones

Nuevas soluciones

Potencias de dos más cercanas

Soluciones

Nuevas soluciones

La serie 1 – 2 + 3 – 4 + ···

Soluciones

Clausura respecto del valor absoluto de las diferencias

Soluciones

Entradas recientes

Buscar

Correo electrónico