Menu Close

Categoría: Inicial

Árbol de las divisiones por 2, 3 ó 5

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

Definir la función

   arbolDivisiones :: Int -> Tree Int

tal que (arbolDivisiones x) es el árbol de las divisiones enteras de x entre 2, 3 ó 5. Por ejemplo,

   λ> putStrLn (drawTree (fmap show (arbolDivisiones 20)))
   20
   |
   +- 10
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 2
   |     |
   |     `- 1
   |
   `- 4
      |
      `- 2
         |
         `- 1
 
   λ> putStrLn (drawTree (fmap show (arbolDivisiones 30)))
   30
   |
   +- 15
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 3
   |     |
   |     `- 1
   |
   +- 10
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 2
   |     |
   |     `- 1
   |
   `- 6
      |
      +- 3
      |  |
      |  `- 1
      |
      `- 2
         |
         `- 1

Soluciones

import Data.Tree (Tree (Node), drawTree)
 
arbolDivisiones :: Int -> Tree Int
arbolDivisiones x =
  Node x (map arbolDivisiones (divisiones x))
 
-- (divisiones x) es la lista de las divisiones enteras de x entre 2, 3
-- y 5. Por ejemplo,
--    divisiones 30  ==  [15,10,6]
--    divisiones 15  ==  [5,3]
divisiones :: Int -> [Int]
divisiones x =
  [x `div` y | y <- [2,3,5], x `mod` y == 0]

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>

Cálculo de pi mediante la fórmula de Beeler

El pasado 12 de marzo se publicó en Twitter un mensaje con una fórmula de Beeler para el cálculo de pi

Los primeros valores son

   λ> 2*1
   2
   λ> 2*(1+1/3)
   2.6666666666666665
   λ> 2*(1+1/3+(1*2)/(3*5))
   2.933333333333333
   λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7))
   3.0476190476190474
   λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7)+(1*2*3*4)/(3*5*7*9))
   3.098412698412698

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Beeler. Por ejemplo,
     aproximacionPi 0    ==  2.0
     aproximacionPi 1    ==  2.6666666666666665
     aproximacionPi 2    ==  2.933333333333333
     aproximacionPi 3    ==  3.0476190476190474
     aproximacionPi 4    ==  3.098412698412698
     aproximacionPi 10   ==  3.141106021601377
     aproximacionPi 100  ==  3.1415926535897922
     pi                  ==  3.141592653589793
  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [0..99]) dibuja

Soluciones

import Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)
 
aproximacionPi :: Int -> Double
aproximacionPi n =
  aproximacionesPi !! n
 
aproximacionesPi :: [Double]
aproximacionesPi =
  map (*2) (scanl1 (+) (1 : scanl1 (*) [(x/y) | (x,y) <- zip [1..] [3,5..]]))
 
 
-- Gráfica
-- =======
 
grafica :: [Int] -> IO ()
grafica xs =
  plotList [ Key Nothing
           -- , PNG "Calculo_de_pi_mediante_la_formula_de_Beeler_1.png"
           ]
           [(k,aproximacionPi k) | k <- xs]

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>

Números con cuadrados con dígitos pares

Definir la lista

   numerosConCuadradosConDigitosPares :: [Integer]

cuyos elementos son los números cuyos cuadrados tienen todos sus dígitos pares. Por ejemplo,

   λ> take 20 numerosConCuadradosConDigitosPares
   [0,2,8,20,22,68,78,80,92,162,168,200,202,220,262,298,478,492,498,668]

Comprobar con QuickCheck que numerosConCuadradosConDigitosPares es infinita; es decir, para cualquier n posee algún elemento mayor que n.

Soluciones

import Test.QuickCheck
 
numerosConCuadradosConDigitosPares :: [Integer]
numerosConCuadradosConDigitosPares =
  filter tieneCuadradoConDigitosPares [0..]
 
-- (tieneCuadradoConDigitosPares n) se verifica si todos los dígitos de
-- n^2 son pares. Por ejemplo,
--    tieneCuadradoConDigitosPares 78  ==  True
--    tieneCuadradoConDigitosPares 76  ==  False
tieneCuadradoConDigitosPares :: Integer -> Bool
tieneCuadradoConDigitosPares n =
  tieneDigitosPares (n^2)
 
-- (tieneDigitosPares n) se verifica si todos los dígitos de n son
-- pares. Por ejemplo,
--    tieneDigitosPares 426  ==  True
--    tieneDigitosPares 436  ==  False
tieneDigitosPares :: Integer -> Bool
tieneDigitosPares n =
  all even (digitos n)
 
-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Int]
digitos n =
  [read [c] | c <- show n]
 
-- La propiedad es
prop_infinito :: Integer -> Bool
prop_infinito n =
  not (null (dropWhile (<= n) numerosConCuadradosConDigitosPares))
 
-- La comprobación es
--    λ> quickCheck prop_infinito
--    +++ OK, passed 100 tests.

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>

Cálculo de pi mediante la fórmula de Bauer

El pasado 10 de marzo se publicó en Twitter un mensaje con una fórmula de Bauer para el cálculo de pi

Los primeros valores son

   λ> 2/1
   2.0
   λ> 2/(1 - 5*(1/2)^3)
   5.333333333333333
   λ> 2/(1 - 5*(1/2)^3 + 9*((1*3)/(2*4))^3)
   2.354022988505747
   λ> 2/(1 - 5*(1/2)^3 + 9*((1*3)/(2*4))^3 - 13*((1*3*5)/(2*4*6))^3)
   4.416172506738545

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Bauer. Por ejemplo,
     aproximacionPi 0         ==  2.0
     aproximacionPi 1         ==  5.333333333333333
     aproximacionPi 2         ==  2.354022988505747
     aproximacionPi 3         ==  4.416172506738545
     aproximacionPi (10^2)    ==  2.974407762733626
     aproximacionPi (10^2+1)  ==  3.3277148010019233
     aproximacionPi (10^3)    ==  3.0865454975585744
     aproximacionPi (10^3+1)  ==  3.1986099487445463
     aproximacionPi (10^4)    ==  3.1239682112773868
     aproximacionPi (10^4+1)  ==  3.1594161911246594
     aproximacionPi (10^5)    ==  3.135997665507836
     aproximacionPi (10^5+1)  ==  3.147207613460776
     pi                       ==  3.141592653589793
  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [0..99]) dibuja

Soluciones

import Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)
 
aproximacionPi :: Int -> Double
aproximacionPi n =
  aproximacionesPi !! n
 
aproximacionesPi :: [Double]
aproximacionesPi =
  map (2/)
      (scanl1 (+)
              (zipWith (*)
                       [fromIntegral ((-1)^n*(4*n+1))| n <- [0..]]
                       (1 : scanl1 (*) [(x/y)^3 | (x,y) <- zip [1,3..] [2,4..]])))
 
-- Gráfica
-- =======
 
grafica :: [Int] -> IO ()
grafica xs =
  plotList [ Key Nothing
           -- , PNG "Calculo_de_pi_mediante_la_formula_de_Bauer_1.png"
           ]
           [(k,aproximacionPi k) | k <- xs]

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>

Cálculo de pi mediante la fórmula de Euler

El pasado 6 de marzo se publicó en Twitter un mensaje con una fórmula de Euler para el cálculo de pi

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Euler. Por ejemplo,
     aproximacionPi 1        ==  2.449489742783178
     aproximacionPi 10       ==  3.04936163598207
     aproximacionPi 100      ==  3.1320765318091053
     aproximacionPi 1000     ==  3.1406380562059946
     aproximacionPi 10000    ==  3.1414971639472147
     aproximacionPi 100000   ==  3.141583104326456
     aproximacionPi 1000000  ==  3.1415916986605086
     pi                      ==  3.141592653589793
  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [1..100]) dibuja

Soluciones

import Graphics.Gnuplot.Simple (Attribute (Key, PNG), plotList)
 
aproximacionPi :: Int -> Double
aproximacionPi n =
  sqrt (6 * sum [1/k^2 | k <- [1.0..fromIntegral n]])
 
grafica :: [Int] -> IO ()
grafica xs =
  plotList [ Key Nothing
           -- , PNG "Calculo_de_pi_mediante_la_formula_de_Euler_1.png"
           ]
           [(k,aproximacionPi k) | k <- xs]

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>

Cálculo de pi mediante la serie de Madhava

El mes de marzo es el mes de pi, ya que el 14 de marzo (3/14) es el día de pi. Con ese motivo, el pasado 1 de marzo se publicó en Twitter un mensaje con la fórmula de Madhava para el cálculo de pi

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: Int -> IO ()

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Madhava. Por ejemplo,
     aproximacionPi 0   ==  3.4641016151377544
     aproximacionPi 1   ==  3.0792014356780038
     aproximacionPi 2   ==  3.156181471569954
     aproximacionPi 10  ==  3.1415933045030813
     aproximacionPi 21  ==  3.1415926535879337
     pi                 ==  3.141592653589793
  • (grafica n) dibuja la gráfica de las k-ésimas aproximaciones de pi para k desde 0 a n. Por ejemplo, (grafica 30) dibuja

Soluciones

import Graphics.Gnuplot.Simple (Attribute (Key), plotList)
 
aproximacionPi :: Int -> Double
aproximacionPi n =
  sqrt 12 * aux (fromIntegral n)
  where
    aux 0 = 1
    aux n = aux (n-1) + (-1)**n/(3**n*(2*n+1))
 
grafica :: Int -> IO ()
grafica n =
    plotList [ Key Nothing
             -- , PNG "Calculo_de_pi_mediante_la_serie_de_Madhava_1.png"
             ]
             [aproximacionPi n | n <- [0..n]]

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>

Sumas parciales

Los sufijos de la lista [3,7,2,5,4,6] son

   [3,7,2,5,4,6]
     [7,2,5,4,6]
       [2,5,4,6]
         [5,4,6]
           [4,6]
             [6]
              []

y la lista de sus sumas es [27,24,17,15,10,6,0].

Definir la función

   sumasParciales :: [Integer] -> [Integer]

tal que (sumasParciales xs) es la lista de las sumas de los sufijos de xs. Por ejemplo,

   sumasParciales [3,7,2,5,4,6]  ==  [27,24,17,15,10,6,0]
   sumasParciales [1..10]        ==  [55,54,52,49,45,40,34,27,19,10,0]
   sum (sumasParciales [1..5*10^6])  ==  41666679166667500000

Soluciones

import Data.List (tails)
 
-- 1ª solución
sumasParciales1 :: [Integer] -> [Integer]
sumasParciales1 xs = map sum (tails xs)
 
-- 2ª solución
sumasParciales2 :: [Integer] -> [Integer]
sumasParciales2 []     = [0]
sumasParciales2 (x:xs) = (x + s):s:ss
  where (s:ss) = sumasParciales2 xs
 
-- 3ª solución
sumasParciales3 :: [Integer] -> [Integer]
sumasParciales3 = foldr (\x (s:ss) -> (x + s) : (s:ss)) [0]
 
-- 4ª solución
sumasParciales4 :: [Integer] -> [Integer]
sumasParciales4 xs = scanl (-) (sum xs) xs
 
-- 5ª solución
sumasParciales5 :: [Integer] -> [Integer]
sumasParciales5 xs = reverse (0 : scanl1 (+) (reverse xs))
 
-- 6ª solución
sumasParciales6 :: [Integer] -> [Integer]
sumasParciales6 = scanr (+) 0
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sum (sumasParciales1 [1..3*10^4])
--    9000450005000
--    (19.70 secs, 40,132,872,616 bytes)
--    λ> sum (sumasParciales2 [1..3*10^4])
--    9000450005000
--    (0.04 secs, 16,932,840 bytes)
--    λ> sum (sumasParciales3 [1..3*10^4])
--    9000450005000
--    (0.02 secs, 13,880,608 bytes)
--    λ> sum (sumasParciales4 [1..3*10^4])
--    9000450005000
--    (0.03 secs, 12,178,080 bytes)
--    λ> sum (sumasParciales5 [1..3*10^4])
--    9000450005000
--    (0.02 secs, 9,974,600 bytes)
--    λ> sum (sumasParciales6 [1..3*10^4])
--    9000450005000
--    (0.02 secs, 10,694,368 bytes)
--
--    λ> sum (sumasParciales2 [1..3*10^6])
--    9000004500000500000
--    (3.13 secs, 1,685,139,696 bytes)
--    λ> sum (sumasParciales3 [1..3*10^6])
--    9000004500000500000
--    (2.37 secs, 1,380,492,448 bytes)
--    λ> sum (sumasParciales4 [1..3*10^6])
--    9000004500000500000
--    (1.84 secs, 1,211,188,264 bytes)
--    λ> sum (sumasParciales5 [1..3*10^6])
--    9000004500000500000
--    (1.22 secs, 987,790,392 bytes)
--    λ> sum (sumasParciales6 [1..3*10^6])
--    9000004500000500000
--    (1.34 secs, 1,059,792,344 bytes)
--
--    λ> sum (sumasParciales5 [1..5*10^6])
--    41666679166667500000
--    (2.36 secs, 1,844,332,576 bytes)
--    λ> sum (sumasParciales6 [1..5*10^6])
--    41666679166667500000
--    (2.03 secs, 1,964,365,912 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>

Suma de la lista reducida

Definir las siguientes funciones

   transformada :: Integral a => [a] -> [a]
   reducida     :: Integral a => [a] -> [a]
   sumaReducida :: Integral a => [a] -> a

tales que

  • (transformada xs) es la lista obtenida sustituyendo en el primer de elementos consecutivos de xs el mayor por su diferencia, donde se supone que xs es una lista de enteros positivos. Por ejemplo,
     transformada [7,2,6]  ==  [5,2,6]
     transformada [2,7,6]  ==  [2,5,6]
     transformada [2,2,6]  ==  [2,2,4]
     transformada [2,2,2]  ==  [2,2,2]
  • (reducida xs) es la lista obtenida aplicando la transformación anterior mientras sea posible (es decir, mientras tenga elementos distintos), donde se supone que xs es una lista de enteros positivos. Por ejemplo,
     reducida [7,2,6]   ==  [1,1,1]
     reducida [6,9,21]  ==  [3,3,3]
  • (sumaReducida xs) es la suma de la reducida de la lista xs. Por ejemplo,
     sumaReducida1 [7,2,6]   ==  3
     sumaReducida1 [6,9,21]  ==  9

Soluciones

import Data.List (genericLength)
 
-- Definición de transformada
-- ==========================
 
transformada :: Integral a => [a] -> [a]
transformada []  = []
transformada [x] = [x]
transformada (x:y:zs)
  | x > y = x-y : y : zs
  | x < y = x : y-x : zs
  | otherwise = x : transformada (y:zs)
 
-- 1ª definición de reducida
-- =========================
 
reducida1 :: Integral a => [a] -> [a]
reducida1 xs
  | xs == ys  = xs
  | otherwise = reducida ys
  where ys = transformada xs
 
-- 2ª definición de reducida
-- =========================
 
reducida2 :: Integral a => [a] -> [a]
reducida2 xs =
  replicate (length xs) (foldl1 gcd xs)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sum (reducida1 [2,4..4*10^6])
--    4000000
--    (1.97 secs, 1,277,797,888 bytes)
--    λ> sum (reducida2 [2,4..4*10^6])
--    4000000
--    (1.92 secs, 1,277,798,344 bytes)
 
-- Definición de reducida
-- =======================
 
reducida :: Integral a => [a] -> [a]
reducida = reducida2
 
-- 1ª definición de sumaReducida
-- =============================
 
sumaReducida1 :: Integral a => [a] -> a
sumaReducida1 = sum . reducida
 
-- 2ª solución
-- ===========
 
sumaReducida2 :: Integral a => [a] -> a
sumaReducida2 xs = genericLength xs * foldl1 gcd xs
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sumaReducida1 [2,4..4*10^6]
--    4000000
--    (2.53 secs, 1,277,796,760 bytes)
--    λ> sumaReducida2 [2,4..4*10^6]
--    4000000
--    (1.89 secs, 1,214,376,960 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>

Eliminaciones anotadas

Definir la función

   eliminaciones :: [a] -> [(a,Int,[a])]

tal que (eliminaciones xs) es la lista de ternas (x,i,zs) tales que x es un elemento de xs, i es la posición de x en xs y zs es la lista de los restantes elementos de xs. Por ejemplo,

   λ> eliminaciones [5,7,6,5]
   [(5,0,[7,6,5]),(7,1,[5,6,5]),(6,2,[5,7,5]),(5,3,[5,7,6])]

Soluciones

import Test.QuickCheck (quickCheck)
 
-- 1ª solución
eliminaciones :: [a] -> [(a,Int,[a])]
eliminaciones xs = [(z,i,zs) | ((z,zs),i) <- zip (aux xs) [0..]]
  where aux []       = []
        aux [x]      = [(x,[])]
        aux (x:y:zs) = (x,y:zs) : [(v,x:vs) | (v,vs) <- aux (y:zs)]
 
-- 2ª solución
eliminaciones2 :: [a] -> [(a,Int,[a])]
eliminaciones2 xs =
  [(v,i,us++vs) | i <- [0..length xs - 1],
                  let (us,v:vs) = splitAt i xs]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_equivalencia :: [Int] -> Bool
prop_equivalencia xs =
  eliminaciones xs == eliminaciones2 xs
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

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>

Ternas crecientes de primos con el mayor igual a la suma de los menores

Definir la función

   ternasPrimas :: [(Integer,Integer,Integer)]

tal que sus elementos son las ternas crecientes de primos con el mayor igual a la suma de los menores. Por ejemplo,

   ternasPrimas  ==  (2,3,5)
   ternasPrimas !! 34567  ==  (2,5393909,5393911)

Soluciones

import Data.Numbers.Primes (primes)
 
ternasPrimas :: [(Integer,Integer,Integer)]
ternasPrimas = [(2,a,b) | (a,b) <- zip (primes) (tail (primes)),
                          a + 2 == b]

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>