Recursión

Filtro booleano

PorJosé A. Alonso 23-junio-201426-marzo-2022

Enunciado

-- Definir la función
--    filtroBooleano :: [Bool] -> [a] -> [Maybe a]
-- tal que (filtroBooleano xs ys) es la lista de los elementos de ys
-- tales que el elemento de xs en la misma posición es verdadero. Por
-- ejemplo, 
--    ghci> filtroBooleano [True,False,True] "Sevilla"
--    [Just 'S',Nothing,Just 'v']
--    ghci> filtroBooleano (repeat True) "abc"
--    [Just 'a',Just 'b',Just 'c']
--    ghci> take 3 (filtroBooleano (repeat True) [1..])
--    [Just 1,Just 2,Just 3]
--    ghci> take 3 (filtroBooleano (repeat False) [1..])
--    [Nothing,Nothing,Nothing]
--    ghci> take 3 (filtroBooleano (cycle [True,False]) [1..])
--    [Just 1,Nothing,Just 3]

-- Definir la función

-- filtroBooleano :: [Bool] -> [a] -> [Maybe a]

-- tal que (filtroBooleano xs ys) es la lista de los elementos de ys

-- tales que el elemento de xs en la misma posición es verdadero. Por

-- ejemplo,

-- ghci> filtroBooleano [True,False,True] "Sevilla"

-- [Just 'S',Nothing,Just 'v']

-- ghci> filtroBooleano (repeat True) "abc"

-- [Just 'a',Just 'b',Just 'c']

-- ghci> take 3 (filtroBooleano (repeat True) [1..])

-- [Just 1,Just 2,Just 3]

-- ghci> take 3 (filtroBooleano (repeat False) [1..])

-- [Nothing,Nothing,Nothing]

-- ghci> take 3 (filtroBooleano (cycle [True,False]) [1..])

-- [Just 1,Nothing,Just 3]

Soluciones

-- 1ª solución (por comprensión):
filtroBooleano1 :: [Bool] -> [a] -> [Maybe a]
filtroBooleano1 xs ys = [f (x,y) | (x,y) <- zip xs ys]
    where f (x,y) | x         = Just y
                  | otherwise = Nothing

-- 2ª solución (con zipWith):
filtroBooleano2 :: [Bool] -> [a] -> [Maybe a]
filtroBooleano2 = zipWith f
    where f x y  | x         = Just y
                 | otherwise = Nothing

-- 3ª solución (con zipWith y lambda):
filtroBooleano3 :: [Bool] -> [a] -> [Maybe a]
filtroBooleano3 = zipWith (\x y -> if x then Just y else Nothing)

-- 4ª solución (por recursión):
filtroBooleano4 :: [Bool] -> [a] -> [Maybe a]
filtroBooleano4 (x:xs) (y:ys) | x         = Just y : filtroBooleano4 xs ys
                              | otherwise = Nothing : filtroBooleano4 xs ys
filtroBooleano4 _ _                       = []

-- 1ª solución (por comprensión):

filtroBooleano1 :: [Bool] -> [a] -> [Maybe a]

filtroBooleano1 xs ys = [f (x,y) | (x,y) <- zip xs ys]

where f (x,y) | x = Just y

| otherwise = Nothing

-- 2ª solución (con zipWith):

filtroBooleano2 :: [Bool] -> [a] -> [Maybe a]

filtroBooleano2 = zipWith f

where f x y | x = Just y

| otherwise = Nothing

-- 3ª solución (con zipWith y lambda):

filtroBooleano3 :: [Bool] -> [a] -> [Maybe a]

filtroBooleano3 = zipWith (\x y -> if x then Just y else Nothing)

-- 4ª solución (por recursión):

filtroBooleano4 :: [Bool] -> [a] -> [Maybe a]

filtroBooleano4 (x:xs) (y:ys) | x = Just y : filtroBooleano4 xs ys

| otherwise = Nothing : filtroBooleano4 xs ys

filtroBooleano4 _ _ = []

Mayor sucesión del problema 3n+1

PorJosé A. Alonso 20-junio-20141-mayo-2016

Enunciado

-- La sucesión 3n+1 generada por un número entero positivo x es la
-- sucesión generada por el siguiente algoritmo: Se empieza con el
-- número x. Si x es par, se divide entre 2. Si x es impar, se
-- multiplica por 3 y se le suma 1. El  proceso se repite con el número
-- obtenido hasta que se alcanza el valor 1. Por ejemplo, la sucesión de
-- números generadas cuando se empieza en 22 es
--    22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
-- Se ha conjeturado (aunque no demostrado) que este algoritmo siempre
-- alcanza el 1 empezando en cualquier entero positivo.
-- 
-- Definir la función
--    mayorLongitud :: Integer -> Integer -> Integer
-- tal que (mayorLongitud i j) es el máximo de las longitudes de las
-- sucesiones 3n+1 para todos los números comprendidos entre i y j,
-- ambos inclusives. Por ejemplo,
--    mayorLongitud   1   10  ==  20
--    mayorLongitud 100  200  ==  125
--    mayorLongitud 201  210  ==  89
--    mayorLongitud 900 1000  ==  174

-- La sucesión 3n+1 generada por un número entero positivo x es la

-- sucesión generada por el siguiente algoritmo: Se empieza con el

-- número x. Si x es par, se divide entre 2. Si x es impar, se

-- multiplica por 3 y se le suma 1. El proceso se repite con el número

-- obtenido hasta que se alcanza el valor 1. Por ejemplo, la sucesión de

-- números generadas cuando se empieza en 22 es

-- 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

-- Se ha conjeturado (aunque no demostrado) que este algoritmo siempre

-- alcanza el 1 empezando en cualquier entero positivo.

-- Definir la función

-- mayorLongitud :: Integer -> Integer -> Integer

-- tal que (mayorLongitud i j) es el máximo de las longitudes de las

-- sucesiones 3n+1 para todos los números comprendidos entre i y j,

-- ambos inclusives. Por ejemplo,

-- mayorLongitud 1 10 == 20

-- mayorLongitud 100 200 == 125

-- mayorLongitud 201 210 == 89

-- mayorLongitud 900 1000 == 174

Soluciones

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

mayorLongitud1 :: Int -> Int -> Int
mayorLongitud1 i j = maximum [length (sucesion k) | k <- [i..j]]

-- (sucesion n) es la sucesión 3n+1 generada por n. Por ejemplo, 
--    sucesion 22  ==  [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
sucesion :: Int -> [Int]
sucesion 1 = [1]
sucesion n | even n    = n : sucesion (n `div` 2)
           | otherwise = n : sucesion (3*n+1)

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

mayorLongitud2 :: Int -> Int -> Int
mayorLongitud2 i j = maximum [longitud k | k <- [i..j]]

-- (longitud n) es la longitud de la sucesión 3n+1 generada por n. Por
-- ejemplo, 
--    longitud 22  ==  16
longitud :: Int -> Int
longitud 1 = 1
longitud n | even n    = 1 + longitud (n `div` 2)
           | otherwise = 1 + longitud (3*n+1)

-- 3ª solución (con iterate)
-- =========================

mayorLongitud3 :: Int -> Int -> Int
mayorLongitud3 i j = maximum [length (sucesion2 k) | k <- [i..j]]

-- (sucesion2 n) es la sucesión 3n+1 generada por n. Por ejemplo, 
--    sucesion2 22  ==  [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
sucesion2 :: Int -> [Int]
sucesion2 n = takeWhile (/=1) (iterate f n) ++ [1]
    where f x | even x    = x `div` 2
              | otherwise = 3*x+1

-- 1ª solución

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

mayorLongitud1 :: Int -> Int -> Int

mayorLongitud1 i j = maximum [length (sucesion k) | k <- [i..j]]

-- (sucesion n) es la sucesión 3n+1 generada por n. Por ejemplo,

-- sucesion 22 == [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

sucesion :: Int -> [Int]

sucesion 1 = [1]

sucesion n | even n = n : sucesion (n `div` 2)

| otherwise = n : sucesion (3*n+1)

-- 2ª solución

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

mayorLongitud2 :: Int -> Int -> Int

mayorLongitud2 i j = maximum [longitud k | k <- [i..j]]

-- (longitud n) es la longitud de la sucesión 3n+1 generada por n. Por

-- ejemplo,

-- longitud 22 == 16

longitud :: Int -> Int

longitud 1 = 1

longitud n | even n = 1 + longitud (n `div` 2)

| otherwise = 1 + longitud (3*n+1)

-- 3ª solución (con iterate)

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

mayorLongitud3 :: Int -> Int -> Int

mayorLongitud3 i j = maximum [length (sucesion2 k) | k <- [i..j]]

-- (sucesion2 n) es la sucesión 3n+1 generada por n. Por ejemplo,

-- sucesion2 22 == [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

sucesion2 :: Int -> [Int]

sucesion2 n = takeWhile (/=1) (iterate f n) ++ [1]

where f x | even x = x `div` 2

| otherwise = 3*x+1

Referencia

El ejercicio está basado en The 3n + 1 problem de UVa Online Judge.

Selección hasta el primero que falla inclusive

PorJosé A. Alonso 18-junio-201429-noviembre-2014

Enunciado

-- Definir la función
--    seleccionConFallo :: (a -> Bool) -> [a] -> [a]
-- tal que (seleccionConFallo p xs) es la lista de los elementos de xs
-- que cumplen el predicado p hasta el primero que no lo cumple
-- inclusive. Por ejemplo,
--    seleccionConFallo (<5) [3,2,5,7,1,0]  ==  [3,2,5]
--    seleccionConFallo odd [1..4]          ==  [1,2]
--    seleccionConFallo odd [1,3,5]         ==  [1,3,5]
--    seleccionConFallo (<5) [10..20]       ==  [10]

-- Definir la función

-- seleccionConFallo :: (a -> Bool) -> [a] -> [a]

-- tal que (seleccionConFallo p xs) es la lista de los elementos de xs

-- que cumplen el predicado p hasta el primero que no lo cumple

-- inclusive. Por ejemplo,

-- seleccionConFallo (<5) [3,2,5,7,1,0] == [3,2,5]

-- seleccionConFallo odd [1..4] == [1,2]

-- seleccionConFallo odd [1,3,5] == [1,3,5]

-- seleccionConFallo (<5) [10..20] == [10]

Soluciones

-- 1ª solución (por recursión):
seleccionConFallo1 :: (a -> Bool) -> [a] -> [a]
seleccionConFallo1 p []                 = []
seleccionConFallo1 p (x:xs) | p x       = x : seleccionConFallo1 p xs
                            | otherwise = [x]

-- 2ª solución (con span):
seleccionConFallo2 :: (a -> Bool) -> [a] -> [a]
seleccionConFallo2 p xs = ys ++ take 1 zs
    where (ys,zs) = span p xs

-- 1ª solución (por recursión):

seleccionConFallo1 :: (a -> Bool) -> [a] -> [a]

seleccionConFallo1 p [] = []

seleccionConFallo1 p (x:xs) | p x = x : seleccionConFallo1 p xs

| otherwise = [x]

-- 2ª solución (con span):

seleccionConFallo2 :: (a -> Bool) -> [a] -> [a]

seleccionConFallo2 p xs = ys ++ take 1 zs

where (ys,zs) = span p xs

Referencia

El ejercicio está basado en el problema del 29 de abril de 1HaskellADay.

Descomposiciones como sumas de n sumandos

PorJosé A. Alonso 17-junio-201429-noviembre-2014

Enunciado

-- Definir la función
--    sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]
-- tal que (sumas n ys x) es la lista de las descomposiciones de x como
-- sumas de n sumandos en la lista ns. Por ejemplo,
--    sumas 2 [1,2] 3    ==  [[1,2],[2,1]]
--    sumas 2 [1,2] 4    ==  [[2,2]]
--    sumas 2 [1,2] 5    ==  []
--    sumas 3 [1,2] 5    ==  [[1,2,2],[2,1,2],[2,2,1]]
--    sumas 3 [1,2] 6    ==  [[2,2,2]]
--    sumas 2 [1,2,5] 6  ==  [[1,5],[5,1]]

-- Definir la función

-- sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]

-- tal que (sumas n ys x) es la lista de las descomposiciones de x como

-- sumas de n sumandos en la lista ns. Por ejemplo,

-- sumas 2 [1,2] 3 == [[1,2],[2,1]]

-- sumas 2 [1,2] 4 == [[2,2]]

-- sumas 2 [1,2] 5 == []

-- sumas 3 [1,2] 5 == [[1,2,2],[2,1,2],[2,2,1]]

-- sumas 3 [1,2] 6 == [[2,2,2]]

-- sumas 2 [1,2,5] 6 == [[1,5],[5,1]]

Soluciones

sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]
sumas 1 ys x | x `elem` ys = [[x]]
             | otherwise   = []
sumas n ys x = 
    concat [[y:zs | zs <- sumas (n-1) ys (x-y)] | y <- ys, y <= x]

sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]

sumas 1 ys x | x `elem` ys = [[x]]

| otherwise = []

sumas n ys x =

concat [[y:zs | zs <- sumas (n-1) ys (x-y)] | y <- ys, y <= x]

Referencia

El ejercicio está basado en el problema del 11 de junio de 1HaskellADay.

Órbita prima

PorJosé A. Alonso 13-junio-20141-mayo-2016

Enunciado

-- La órbita prima de un número n es la sucesión construida de la
-- siguiente forma: 
--    * si n es compuesto su órbita no tiene elementos 
--    * si n es primo, entonces n está en su órbita; además, sumamos n y
--      sus dígitos, si el resultado es un número primo repetimos el
--      proceso hasta obtener un número compuesto. 
-- Por ejemplo, con el 11 podemos repetir el proceso dos veces
--    13 = 11+1+1
--    17 = 13+1+3
-- Así, la órbita prima de 11 es 11, 13, 17. 
-- 
-- Definir la función
--    orbita :: Integer -> [Integer]
-- tal que (orbita n) es la órbita prima de n. Por ejemplo,
--    orbita 11 == [11,13,17]
--    orbita 59 == [59,73,83]
-- Calcular el menor número cuya órbita prima tiene más de 3 elementos.

-- La órbita prima de un número n es la sucesión construida de la

-- siguiente forma:

-- * si n es compuesto su órbita no tiene elementos

-- * si n es primo, entonces n está en su órbita; además, sumamos n y

-- sus dígitos, si el resultado es un número primo repetimos el

-- proceso hasta obtener un número compuesto.

-- Por ejemplo, con el 11 podemos repetir el proceso dos veces

-- 13 = 11+1+1

-- 17 = 13+1+3

-- Así, la órbita prima de 11 es 11, 13, 17.

-- Definir la función

-- orbita :: Integer -> [Integer]

-- tal que (orbita n) es la órbita prima de n. Por ejemplo,

-- orbita 11 == [11,13,17]

-- orbita 59 == [59,73,83]

-- Calcular el menor número cuya órbita prima tiene más de 3 elementos.

Soluciones

-- 1ª definición (por recursión)
-- =============================

orbita1 :: Integer -> [Integer]
orbita1 n | not (esPrimo n) = []
          | otherwise       = n : orbita1 (n + sum (cifras n))

esPrimo :: Integer -> Bool
esPrimo n = [x | x <- [1..n], n `rem` x == 0] == [1,n] 

cifras :: Integer -> [Integer]
cifras n = [read [x]| x <- show n]

-- El cálculo es
--    ghci> head [x | x <- [1,3..], length (orbita x) > 3]
--    277
-- 
--    ghci> orbita 277
--    [277,293,307,317]

-- 2ª definición (con iterate)
-- ===========================

orbita2 :: Integer -> [Integer]
orbita2 n = takeWhile esPrimo (iterate f n)
    where f x = x + sum (cifras x)

-- 1ª definición (por recursión)

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

orbita1 :: Integer -> [Integer]

orbita1 n | not (esPrimo n) = []

| otherwise = n : orbita1 (n + sum (cifras n))

esPrimo :: Integer -> Bool

esPrimo n = [x | x <- [1..n], n `rem` x == 0] == [1,n]

cifras :: Integer -> [Integer]

cifras n = [read [x]| x <- show n]

-- El cálculo es

-- ghci> head [x | x <- [1,3..], length (orbita x) > 3]

-- 277

-- ghci> orbita 277

-- [277,293,307,317]

-- 2ª definición (con iterate)

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

orbita2 :: Integer -> [Integer]

orbita2 n = takeWhile esPrimo (iterate f n)

where f x = x + sum (cifras x)

Filtro booleano

Enunciado

Soluciones

Mayor sucesión del problema 3n+1

Enunciado

Soluciones

Referencia

Selección hasta el primero que falla inclusive

Enunciado

Soluciones

Referencia

Descomposiciones como sumas de n sumandos

Enunciado

Soluciones

Referencia

Órbita prima

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico