Menu Close

Etiqueta: Recursión

Definición por recursión

Elemento más repetido de manera consecutiva

Enunciado

-- Definir la función
--    masRepetido :: Ord a => [a] -> (a,Int)
-- tal que (masRepetido xs) es el elemento de xs que aparece más veces
-- de manera consecutiva en la lista junto con el número de sus
-- apariciones consecutivas; en caso de empate, se devuelve el último de
-- dichos elementos. Por ejemplo, 
--    masRepetido [1,1,4,4,1]  ==  (4,2)
--    masRepetido "aadda"      ==  ('d',2)

Soluciones

import Data.List (group)
import Data.Tuple (swap)
 
-- 1ª definición (por recursión):
masRepetido1 :: Ord a => [a] -> (a,Int)
masRepetido1 [x] = (x,1)
masRepetido1 (x:y:zs) | m > n     = (x,m)
                      | otherwise = (u,n)
    where (u,n) = masRepetido1 (y:zs)
          m     = length (takeWhile (==x) (x:y:zs))
 
-- 2ª definición (con group y maximum):
masRepetido2 :: Ord a => [a] -> (a,Int)
masRepetido2 xs = (n,z)
    where (z,n) = maximum [(length ys,y) | (y:ys) <- group xs]
 
-- 3ª definición (con group, maximum y swap):
masRepetidoP8 :: Ord a => [a] -> (a,Int)
masRepetidoP8 xs = 
    swap (maximum [(length ys,y) | (y:ys) <- group xs])

Regiones en el plano

Enunciado

-- En los siguientes dibujos se observa que el número máximo de regiones
-- en el plano generadas con 1, 2 ó 3 líneas son 2, 4 ó 7,
-- respectivamente. 
-- 
--                       \  |
--                        \5|
--                         \|
--                          \
--                          |\
--                          | \
--                |         |  \ 
--     1        1 | 3     1 | 3 \  6
--    ------   ---|---   ---|----\---
--     2        2 | 4     2 | 4   \ 7
--                |         |      \
-- 
-- Definir la función
--    regiones :: Integer -> Integer  
-- tal que (regiones n) es el número máximo de regiones en el plano
-- generadas con n líneas. Por ejemplo,
--    regiones 3    ==  7  
--    regiones 100  ==  5051

Soluciones

-- 1ª definición (por recursión):
regiones1 :: Integer -> Integer  
regiones1 0 = 1
regiones1 n = regiones1 (n-1) + n  
 
-- 2ª definición (por la fórmula):
regiones2 :: Integer -> Integer
regiones2 n = n*(n+1) `div` 2 + 1

Emparejamiento binario

Enunciado

-- Definir la función
--    zipBinario :: [a -> b -> c] -> [a] -> [b] -> [c]
-- tal que (zipBinario fs xs ys) es la lista obtenida aplicando cada una
-- de las operaciones binarias de fs a los correspondientes elementos de
-- xs e ys. Por ejemplo, 
--    zipBinario [(+), (*), (*)] [2,2,2] [4,4,4]     ==  [6,8,8]
--    zipBinario [(+)] [2,2,2] [4,4,4]               ==  [6]
--    zipBinario (cycle [(+), (*)]) [1 .. 4] [2..5]  ==  [3,6,7,20]

Soluciones

-- 1ª definición (por recursión):
zipBinario :: [a -> b -> c] -> [a] -> [b] -> [c]
zipBinario (f:fs) (x:xs) (y:ys) = f x y : zipBinario fs xs ys
zipBinario _ _ _                = []
 
-- 2ª definición (con zip):
zipBinario2 :: [a -> b -> c] -> [a] -> [b] -> [c]
zipBinario2 fs xs ys = [f x y | (f,(x,y)) <- zip fs (zip xs ys)]
 
-- 3ª definición (con zip3):
zipBinario3 :: [a -> b -> c] -> [a] -> [b] -> [c]
zipBinario3 fs xs ys = [f x y | (f,x,y) <- zip3 fs xs ys]
 
-- Nota. La definición anterior usa la función zip3 que agrupa
-- ternas. Por ejemplo,
--    zip3 [1..3] [4..7] [8..11]  ==  [(1,4,8),(2,5,9),(3,6,10)]
--    zip3 [1..3] [4,5] [8..11]   ==  [(1,4,8),(2,5,9)]
--    zip3 [1..3] [4,5] [8]       ==  [(1,4,8)]
 
-- 4ª definición (con zipWith3):
zipBinario4 :: [a -> b -> c] -> [a] -> [b] -> [c]
zipBinario4 = zipWith3 id 
 
-- Nota. En la definición anterior se usa la función zipwith3 tal que
-- (zipwith3 g fs xs ys) es la lista obtenida aplicando 
--    zipwith3 (\x y z -> x+y+z) [7,8] [1..3] [4..6]  ==  [12,15]
--    zipwith3 id [(+),(*)] [1..3] [4..6]             ==  [5,10]

Ramas de un árbol

Enunciado

-- Los árboles se pueden representar mediante el siguiente tipo de datos
--    data Arbol a = N a [Arbol a]
--                   deriving Show
-- Por ejemplo, los árboles
--      1               3
--     / \             /|\ 
--    2   3           / | \
--        |          5  4  7
--        4          |     /\ 
--                   6    2  1
-- se representan por
--    ej1, ej2 :: Arbol Int
--    ej1 = N 1 [N 2 [],N 3 [N 4 []]]
--    ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]
-- 
-- Definir la función 
--    ramas :: Arbol b -> [[b]]
-- tal que (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
--    ramas ej1  ==  [[1,2],[1,3,4]]
--    ramas ej2  ==  [[3,5,6],[3,4],[3,7,2],[3,7,1]]

Soluciones

data Arbol a = N a [Arbol a]
               deriving Show
 
-- 1ª solución:
ramas1 :: Arbol b -> [[b]]
ramas1 (N x []) = [[x]]
ramas1 (N x as) = [x : xs | a <- as, xs <- ramas1 a]
 
-- 2ª solución:
ramas2 :: Arbol b -> [[b]]
ramas2 (N x []) = [[x]]
ramas2 (N x as) = concat (map (map (x:)) (map ramas2 as))
 
-- 3ª solución:
ramas3 :: Arbol b -> [[b]]
ramas3 (N x []) = [[x]]
ramas3 (N x as) = concatMap (map (x:)) (map ramas3 as)

Segmentos maximales con elementos consecutivos

Enunciado

-- Definir la función
--    segmentos :: (Enum a, Eq a) => [a] -> [[a]]
-- tal que (segmentos xss) es la lista de los segmentos maximales de xss
-- formados por elementos consecutivos. Por ejemplo,
--    segmentos [1,2,5,6,4]     ==  [[1,2],[5,6],[4]]
--    segmentos [1,2,3,4,7,8,9] ==  [[1,2,3,4],[7,8,9]]
--    segmentos "abbccddeeebc"  ==  ["ab","bc","cd","de","e","e","bc"]
-- Nota: Se puede usar la función succ tal que (succ x) es el sucesor de
-- x. Por ejemplo,
--    succ 3    ==  4
--    succ 'c'  ==  'd'

Soluciones

-- 1ª definición (por recursión):
segmentos1 :: (Enum a, Eq a) => [a] -> [[a]]
segmentos1 []  = []
segmentos1 [x] = [[x]]
segmentos1 (x:xs) | y == succ x = (x:y:ys):zs
                 | otherwise   = [x] : (y:ys):zs
    where ((y:ys):zs) = segmentos1 xs
 
-- 2ª definición.
segmentos2 :: (Enum a, Eq a) => [a] -> [[a]]
segmentos2 []  = []
segmentos2 xs = ys : segmentos2 zs
    where ys = inicial xs
          n  = length ys
          zs = drop n xs
 
-- (inicial xs) es el segmento inicial de xs formado por elementos
-- consecutivos. Por ejemplo,
--    inicial [1,2,5,6,4]  ==  [1,2]
--    inicial "abccddeeebc"  ==  "abc"
inicial :: (Enum a, Eq a) => [a] -> [a]
inicial [] = []
inicial (x:xs) = 
    [y | (y,z) <- takeWhile (\(u,v) -> u == v) (zip (x:xs) [x..])]