Orden superior – Exercitium

Caminos reducidos

José A. Alonso-5-junio-2020-Medio-4 Comentarios

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

   data Direccion = N | S | E | O deriving (Show, Eq)
   type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

   reducido []                              ==  []
   reducido [N]                             ==  [N]
   reducido [N,O]                           ==  [N,O]
   reducido [N,O,E]                         ==  [N]
   reducido [N,O,E,S]                       ==  [] 
   reducido [N,O,S,E]                       ==  [N,O,S,E]
   reducido [S,S,S,N,N,N]                   ==  []
   reducido [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

       [N,S,S,E,O,N,O]  
   --> [S,E,O,N,O]  
   --> [S,N,O]  
   --> [O]

Soluciones

data Direccion = N | S | E | O deriving (Show, Eq)
 
type Camino = [Direccion]
 
-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido1 ds
 
opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E
 
-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
    where aux N (S:xs) = xs
          aux S (N:xs) = xs
          aux E (O:xs) = xs
          aux O (E:xs) = xs
          aux x xs     = x:xs
 
-- 3ª solución 
reducido3 :: Camino -> Camino
reducido3 []       = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido3 ds
 
-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where 
    aux (N:xs, S:ys) = aux (xs,ys)
    aux (S:xs, N:ys) = aux (xs,ys)
    aux (E:xs, O:ys) = aux (xs,ys)
    aux (O:xs, E:ys) = aux (xs,ys)
    aux (  xs, y:ys) = aux (y:xs,ys)
    aux (  xs,   []) = xs
 
-- Comparación de eficiencia
--    ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (3.87 secs, 460160736 bytes)
--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (1.16 secs, 216582880 bytes)
--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.58 secs, 98561872 bytes)
--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.64 secs, 176154640 bytes)
--    
--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (5.43 secs, 962694784 bytes)
--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (9.29 secs, 1722601528 bytes)
-- 
--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (4.52 secs, 547004960 bytes)
--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    
--    ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)
--    []
--    (7.35 secs, 537797096 bytes)
--    ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)
--    []
--    (2.30 secs, 244553404 bytes)
--    ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)
--    []
--    (8.08 secs, 545043608 bytes)
--    ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)
--    []
--    (1.96 secs, 205552240 bytes)

data Direccion = N | S | E | O deriving (Show, Eq) type Camino = [Direccion] -- 1ª solución (por recursión): reducido1 :: Camino -> Camino reducido1 [] = [] reducido1 (d:ds) | null ds' = [d] | d == opuesta (head ds') = tail ds' | otherwise = d:ds' where ds' = reducido1 ds opuesta :: Direccion -> Direccion opuesta N = S opuesta S = N opuesta E = O opuesta O = E -- 2ª solución (por plegado) reducido2 :: Camino -> Camino reducido2 = foldr aux [] where aux N (S:xs) = xs aux S (N:xs) = xs aux E (O:xs) = xs aux O (E:xs) = xs aux x xs = x:xs -- 3ª solución reducido3 :: Camino -> Camino reducido3 [] = [] reducido3 (N:S:ds) = reducido3 ds reducido3 (S:N:ds) = reducido3 ds reducido3 (E:O:ds) = reducido3 ds reducido3 (O:E:ds) = reducido3 ds reducido3 (d:ds) | null ds' = [d] | d == opuesta (head ds') = tail ds' | otherwise = d:ds' where ds' = reducido3 ds -- 4ª solución reducido4 :: Camino -> Camino reducido4 ds = reverse (aux ([],ds)) where aux (N:xs, S:ys) = aux (xs,ys) aux (S:xs, N:ys) = aux (xs,ys) aux (E:xs, O:ys) = aux (xs,ys) aux (O:xs, E:ys) = aux (xs,ys) aux ( xs, y:ys) = aux (y:xs,ys) aux ( xs, []) = xs -- Comparación de eficiencia -- ghci> reducido1 (take (10^6) (cycle [N,E,O,S])) -- [] -- (3.87 secs, 460160736 bytes) -- ghci> reducido2 (take (10^6) (cycle [N,E,O,S])) -- [] -- (1.16 secs, 216582880 bytes) -- ghci> reducido3 (take (10^6) (cycle [N,E,O,S])) -- [] -- (0.58 secs, 98561872 bytes) -- ghci> reducido4 (take (10^6) (cycle [N,E,O,S])) -- [] -- (0.64 secs, 176154640 bytes) -- -- ghci> reducido3 (take (10^7) (cycle [N,E,O,S])) -- [] -- (5.43 secs, 962694784 bytes) -- ghci> reducido4 (take (10^7) (cycle [N,E,O,S])) -- [] -- (9.29 secs, 1722601528 bytes) -- -- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S]) -- 400002 -- (4.52 secs, 547004960 bytes) -- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S]) -- 400002 -- -- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S) -- [] -- (7.35 secs, 537797096 bytes) -- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S) -- [] -- (2.30 secs, 244553404 bytes) -- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S) -- [] -- (8.08 secs, 545043608 bytes) -- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S) -- [] -- (1.96 secs, 205552240 bytes)

Seguir leyendo →

Número como suma de sus dígitos

José A. Alonso-3-junio-2020-Inicial-2 Comentarios

El número 23 se puede escribir de 4 formas como suma de sus dígitos

   2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
   2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
   2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
   2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

   minimoSumandosDigitos        :: Integer -> Integer
   graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

(minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,

     minimoSumandosDigitos 23    ==  8
     minimoSumandosDigitos 232   ==  78
     minimoSumandosDigitos 2323  ==  775
     map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10]

(graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Soluciones

import Test.QuickCheck
import Graphics.Gnuplot.Simple
import Data.List (nub, genericLength, sort)
import Data.Array (array, (!))
 
minimoSumandosDigitos :: Integer -> Integer
minimoSumandosDigitos n =
  minimoSumandos (digitos n) n
 
-- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo,
--    digitos 2032  ==  [2,3]
digitos :: Integer -> [Integer]
digitos n =
  nub [read [c] | c <- show n, c /= '0']
 
-- (minimoSumandos xs n) es el menor número de elementos de la lista de
-- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por
-- ejemplo, 
--    minimoSumandos [7,2,4] 11  ==  2
minimoSumandos :: [Integer] -> Integer -> Integer
minimoSumandos xs n =
  minimum (map genericLength (sumas xs n))
 
-- (sumas xs n) es la lista de elementos de la lista de enteros
-- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo,  
--    sumas [7,2,4] 11  ==  [[7,2,2],[7,4]]
sumas :: [Integer] -> Integer -> [[Integer]]
sumas [] 0 = [[]]
sumas [] _ = []
sumas (x:xs) n
  | x <= n    = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n
  | otherwise = sumas xs n
 
-- 2ª solución
-- ===========
 
minimoSumandosDigitos2 :: Integer -> Integer
minimoSumandosDigitos2 n = aux n 
  where
    aux 0 = 0
    aux k = 1 + minimo [aux (k - x) | x <- ds,  k >= x]
    ds    = digitos n
    infinito = 10^100
    minimo xs | null xs   = infinito
              | otherwise = minimum xs
 
-- 3ª solución
-- ===========
 
minimoSumandosDigitos3 :: Integer -> Integer
minimoSumandosDigitos3 n = v ! n
  where
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = 1 + minimo [v ! (k - x) | x <- ds, k >= x]
    ds       = digitos n
    infinito = 10^100
    minimo xs | null xs   = infinito
              | otherwise = minimum xs
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_minimoSumandosDigitos :: Positive Integer -> Bool
prop_minimoSumandosDigitos (Positive n) =
  r1 == r2 && r2 == r3
  where
    r1 = minimoSumandosDigitos n
    r2 = minimoSumandosDigitos n
    r3 = minimoSumandosDigitos n
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=9}) prop_minimoSumandosDigitos
--    +++ OK, passed 100 tests.
 
-- Definición de graficaMinimoSumandosDigitos
-- ==========================================
 
graficaMinimoSumandosDigitos :: Integer -> IO ()
graficaMinimoSumandosDigitos n =
  plotList [ Key Nothing
           -- , PNG "Numero_como_suma_de_sus_digitos.png"
           ]
           [minimoSumandosDigitos k | k <- [0..n-1]]

import Test.QuickCheck import Graphics.Gnuplot.Simple import Data.List (nub, genericLength, sort) import Data.Array (array, (!)) minimoSumandosDigitos :: Integer -> Integer minimoSumandosDigitos n = minimoSumandos (digitos n) n -- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo, -- digitos 2032 == [2,3] digitos :: Integer -> [Integer] digitos n = nub [read [c] | c <- show n, c /= '0'] -- (minimoSumandos xs n) es el menor número de elementos de la lista de -- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por -- ejemplo, -- minimoSumandos [7,2,4] 11 == 2 minimoSumandos :: [Integer] -> Integer -> Integer minimoSumandos xs n = minimum (map genericLength (sumas xs n)) -- (sumas xs n) es la lista de elementos de la lista de enteros -- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo, -- sumas [7,2,4] 11 == [[7,2,2],[7,4]] sumas :: [Integer] -> Integer -> [[Integer]] sumas [] 0 = [[]] sumas [] _ = [] sumas (x:xs) n | x <= n = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n | otherwise = sumas xs n -- 2ª solución -- =========== minimoSumandosDigitos2 :: Integer -> Integer minimoSumandosDigitos2 n = aux n where aux 0 = 0 aux k = 1 + minimo [aux (k - x) | x <- ds, k >= x] ds = digitos n infinito = 10^100 minimo xs | null xs = infinito | otherwise = minimum xs -- 3ª solución -- =========== minimoSumandosDigitos3 :: Integer -> Integer minimoSumandosDigitos3 n = v ! n where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = 1 + minimo [v ! (k - x) | x <- ds, k >= x] ds = digitos n infinito = 10^100 minimo xs | null xs = infinito | otherwise = minimum xs -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_minimoSumandosDigitos :: Positive Integer -> Bool prop_minimoSumandosDigitos (Positive n) = r1 == r2 && r2 == r3 where r1 = minimoSumandosDigitos n r2 = minimoSumandosDigitos n r3 = minimoSumandosDigitos n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=9}) prop_minimoSumandosDigitos -- +++ OK, passed 100 tests. -- Definición de graficaMinimoSumandosDigitos -- ========================================== graficaMinimoSumandosDigitos :: Integer -> IO () graficaMinimoSumandosDigitos n = plotList [ Key Nothing -- , PNG "Numero_como_suma_de_sus_digitos.png" ] [minimoSumandosDigitos k | k <- [0..n-1]]

Seguir leyendo →

Cambio con el menor número de monedas

José A. Alonso-2-junio-2020-Avanzado-2 Comentarios

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

   1, 1, 1, 1, 1, 1
   1, 1, 1, 3
   1, 1, 4
   3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

   monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

   monedas [1,3,4]  6                    ==  Just 2
   monedas [2,5,10] 3                    ==  Nothing
   monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

Soluciones

import Data.Array ((!), array)
 
-- 1ª solución
-- ===========
 
monedas :: [Int] -> Int -> Maybe Int
monedas ms x
  | null cs   = Nothing
  | otherwise = Just (minimum (map length cs))
  where cs = cambios ms x
 
-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas
-- de ms. Por ejemplo,
--   λ> cambios [1,5,10] 12
--   [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]
--   λ> cambios [2,5,10] 3
--   []
--   λ> cambios [1,3,4] 6
--   [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]
cambios :: [Int] -> Int -> [[Int]]
cambios _      0 = [[]]
cambios []     _ = []
cambios (k:ks) m
  | m < k     = []
  | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++
                cambios ks m
 
-- 2ª solución
-- ===========
 
monedas2 :: [Int] -> Int -> Maybe Int
monedas2 ms n
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = aux n
    aux 0 = 0
    aux k = siguiente (minimo [aux (k - x) | x <- ms,  k >= x])
 
infinito :: Int
infinito = 10^30
 
minimo :: [Int] -> Int
minimo [] = infinito
minimo xs = minimum xs
 
siguiente :: Int -> Int
siguiente x | x == infinito = infinito
            | otherwise     = 1 + x
 
-- 3ª solución
-- ===========
 
monedas3 :: [Int] -> Int -> Maybe Int
monedas3 ms n  
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = v ! n
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])
 
-- Comparación de eficiencia
-- =========================
 
--    λ> monedas [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.02 secs, 871,144 bytes)
--    λ> monedas2 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (15.44 secs, 1,866,519,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.01 secs, 157,232 bytes)
--    
--    λ> monedas [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (14.20 secs, 1,845,293,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (0.01 secs, 623,376 bytes)

import Data.Array ((!), array) -- 1ª solución -- =========== monedas :: [Int] -> Int -> Maybe Int monedas ms x | null cs = Nothing | otherwise = Just (minimum (map length cs)) where cs = cambios ms x -- (cambios ms x) es la lista de las foemas de obtener x sumando monedas -- de ms. Por ejemplo, -- λ> cambios [1,5,10] 12 -- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]] -- λ> cambios [2,5,10] 3 -- [] -- λ> cambios [1,3,4] 6 -- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]] cambios :: [Int] -> Int -> [[Int]] cambios _ 0 = [[]] cambios [] _ = [] cambios (k:ks) m | m < k = [] | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++ cambios ks m -- 2ª solución -- =========== monedas2 :: [Int] -> Int -> Maybe Int monedas2 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = aux n aux 0 = 0 aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x]) infinito :: Int infinito = 10^30 minimo :: [Int] -> Int minimo [] = infinito minimo xs = minimum xs siguiente :: Int -> Int siguiente x | x == infinito = infinito | otherwise = 1 + x -- 3ª solución -- =========== monedas3 :: [Int] -> Int -> Maybe Int monedas3 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = v ! n v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x]) -- Comparación de eficiencia -- ========================= -- λ> monedas [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.02 secs, 871,144 bytes) -- λ> monedas2 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (15.44 secs, 1,866,519,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.01 secs, 157,232 bytes) -- -- λ> monedas [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (14.20 secs, 1,845,293,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (0.01 secs, 623,376 bytes)

Seguir leyendo →

Operaciones con series de potencias

José A. Alonso-29-mayo-2020-Medio-5 Comentarios

Una serie de potencias es una serie de la forma

   a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

   e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

   type Serie a = [a]

Definir las siguientes funciones

   opuesta      :: Num a => Serie a -> Serie a
   suma         :: Num a => Serie a -> Serie a -> Serie a
   resta        :: Num a => Serie a -> Serie a -> Serie a
   producto     :: Num a => Serie a -> Serie a -> Serie a
   cociente     :: Fractional a => Serie a -> Serie a -> Serie a
   derivada     :: (Num a, Enum a) => Serie a -> Serie a
   integral     :: (Fractional a, Enum a) => Serie a -> Serie a
   expx         :: Serie Rational

tales que

(opuesta xs) es la opuesta de la serie xs. Por ejemplo,

     λ> take 7 (opuesta [-6,-4..])
     [6,4,2,0,-2,-4,-6]

(suma xs ys) es la suma de las series xs e ys. Por ejemplo,

     λ> take 7 (suma [1,3..] [2,4..])
     [3,7,11,15,19,23,27]

(resta xs ys) es la resta de las series xs es ys. Por ejemplo,

     λ> take 7 (resta [3,5..] [2,4..])
     [1,1,1,1,1,1,1]
     λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
     [2,4,6,8,10,12,14]

(producto xs ys) es el producto de las series xs e ys. Por ejemplo,

     λ> take 7 (producto [3,5..] [2,4..])
     [6,22,52,100,170,266,392]

(cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

     λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
     [2.0,4.0,6.0,8.0,10.0,12.0,14.0]

(derivada xs) es la derivada de la serie xs. Por ejemplo,

     λ> take 7 (derivada [2,4..])
     [4,12,24,40,60,84,112]

(integral xs) es la integral de la serie xs. Por ejemplo,

     λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
     [0.0,4.0,6.0,8.0,10.0,12.0,14.0]

expx es la serie de la función exponencial. Por ejemplo,

     λ> take 8 expx
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (derivada expx)
     [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
     λ> take 8 (integral expx)
     [0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Soluciones

type Serie a = [a] 
 
opuesta :: Num a => Serie a -> Serie a
opuesta = map negate
 
suma :: Num a => Serie a -> Serie a -> Serie a
suma = zipWith (+)
 
resta :: Num a => Serie a -> Serie a -> Serie a
resta xs ys = suma xs (opuesta ys)
 
producto :: Num a => Serie a -> Serie a -> Serie a
producto (x:xs) zs@(y:ys) = 
    x*y : suma (producto xs zs) (map (x*) ys)
 
cociente :: Fractional a => Serie a -> Serie a -> Serie a
cociente (x:xs) (y:ys) = zs 
    where zs = x/y : map (/y) (resta xs (producto zs ys))  
 
derivada :: (Num a, Enum a) => Serie a -> Serie a
derivada (_:xs) = zipWith (*) xs [1..]
 
integral :: (Fractional a, Enum a) => Serie a -> Serie a
integral xs = 0 : zipWith (/) xs [1..]
 
expx :: Serie Rational
expx = map (1/) (map fromIntegral factoriales)
 
-- factoriales es la lista de los factoriales. Por ejemplo, 
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

Seguir leyendo →

Sucesión duplicadora

José A. Alonso-26-mayo-2020-Inicial-5 Comentarios

Para cada entero positivo n, existe una única sucesión que empieza en 1, termina en n y en la que cada uno de sus elementos es el doble de su anterior o el doble más uno. Dicha sucesión se llama la sucesión duplicadora de n. Por ejemplo, la sucesión duplicadora de 13 es [1, 3, 6, 13], ya que

    3 = 2*1 +1
    6 = 2*3
   13 = 2*6 +1

Definir la función

   duplicadora :: Integer -> [Integer]

tal que (duplicadora n) es la sucesión duplicadora de n. Por ejemplo,

   duplicadora 13                   ==  [1,3,6,13]
   duplicadora 17                   ==  [1,2,4,8,17]
   length (duplicadora (10^40000))  ==  132878

Soluciones

-- 1ª definición
duplicadora :: Integer -> [Integer]
duplicadora x =
  reverse (takeWhile (>=1) (iterate (`div` 2) x))
 
-- 2ª definición
duplicadora2 :: Integer -> [Integer]
duplicadora2  =
  reverse . takeWhile (>=1) . iterate (`div` 2)

Seguir leyendo →

Alejandro García Alcaide en Números superabundantes
Joaquín Infante Rodríguez en Números superabundantes
Alejandro García Alcaide en Máxima suma de dos cuadrados condicionados
Joaquín Infante Rodríguez en Productos de elementos de dos conjuntos
Alejandro Garcia Alcaide en Productos de elementos de dos conjuntos
Joaquín Infante Rodríguez en Potencias con mismos finales
Alejandro García Alcaide en Múltiplos sin ceros

Etiqueta: Orden superior

Caminos reducidos

Soluciones

Número como suma de sus dígitos

Soluciones

Cambio con el menor número de monedas

Soluciones

Operaciones con series de potencias

Soluciones

Sucesión duplicadora

Soluciones

Etiquetas

Entradas recientes

Comentarios recientes

Buscar

Correo electrónico

Meta

agosto 2021
L	M	X	J	V	S	D
« Jun
						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