Exercitium

Inserción en árboles binarios de búsqueda

PorJosé A. Alonso 17-julio-20141-mayo-2015

-- Un árbol binario de búsqueda (ABB) es un árbol binario tal que el de
-- cada nodo es mayor que los valores de su subárbol izquierdo y es
-- menor que los valores de su subárbol derecho y, además, ambos
-- subárboles son árboles binarios de búsqueda. Por ejemplo, al
-- almacenar los valores de [8,4,2,6,3] en un ABB se puede obtener el
-- siguiente ABB:
-- 
--       5 
--      / \
--     /   \ 
--    2     6 
--         / \ 
--        4   8 
-- 
-- Los ABB se pueden representar como tipo de dato algebraico:
--    data ABB = V
--             | N Int ABB ABB
--             deriving (Eq, Show)
-- Por ejemplo, la definición del ABB anteriore es
--    ej :: ABB
--    ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))
--
-- Definir la función 
--    inserta :: Int -> ABB -> ABB
-- tal que (inserta v a) es el árbol binario de búsqueda 
-- obtenido añadiendo el valor v al ABB a, si no es uno 
-- de sus valores. Por ejemplo, 
--    ghci>  inserta 5 ej
--    N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))
--    ghci>  inserta 1 ej
--    N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))
--    ghci>  inserta 2 ej
--    N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

-- Un árbol binario de búsqueda (ABB) es un árbol binario tal que el de

-- cada nodo es mayor que los valores de su subárbol izquierdo y es

-- menor que los valores de su subárbol derecho y, además, ambos

-- subárboles son árboles binarios de búsqueda. Por ejemplo, al

-- almacenar los valores de [8,4,2,6,3] en un ABB se puede obtener el

-- siguiente ABB:

-- 5

-- / \

-- 2 6

-- / \

-- 4 8

-- Los ABB se pueden representar como tipo de dato algebraico:

-- data ABB = V

-- | N Int ABB ABB

-- deriving (Eq, Show)

-- Por ejemplo, la definición del ABB anteriore es

-- ej :: ABB

-- ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

-- Definir la función

-- inserta :: Int -> ABB -> ABB

-- tal que (inserta v a) es el árbol binario de búsqueda

-- obtenido añadiendo el valor v al ABB a, si no es uno

-- de sus valores. Por ejemplo,

-- ghci> inserta 5 ej

-- N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))

-- ghci> inserta 1 ej

-- N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))

-- ghci> inserta 2 ej

-- N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

Soluciones

data ABB = V
         | N Int ABB ABB
         deriving (Eq, Show)

ej :: ABB 
ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

inserta :: Int -> ABB -> ABB
inserta v1 V = N v1 V V
inserta v1 (N v i d) 
    | v1 == v   = N v i d
    | v1 < v    = N v (inserta v1 i) d
    | otherwise = N v i (inserta v1 d)

data ABB = V

| N Int ABB ABB

deriving (Eq, Show)

ej :: ABB

ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

inserta :: Int -> ABB -> ABB

inserta v1 V = N v1 V V

inserta v1 (N v i d)

| v1 == v = N v i d

| v1 < v = N v (inserta v1 i) d

| otherwise = N v i (inserta v1 d)

Producto de matrices como listas de listas

PorJosé A. Alonso 16-julio-20141-mayo-2015

-- Las matrices pueden representarse mediante una lista de listas donde
-- cada una de las lista representa una fila  de la matriz. Por ejemplo,
-- la matriz
--    |1 0 -2|
--    |0 3 -1|
-- puede representarse por [[1,0,-2],[0,3,-1]]. 
-- 
-- Definir la función
--    producto :: Num a => [[a]] -> [[a]] -> [[a]]
-- tal que (producto p q) es el producto de las matrices p y q. Por
-- ejemplo, 
--    ghci> producto [[1,0,-2],[0,3,-1]] [[0,3],[-2,-1],[0,4]]
--    [[0,-5],[-6,-7]]

-- Las matrices pueden representarse mediante una lista de listas donde

-- cada una de las lista representa una fila de la matriz. Por ejemplo,

-- la matriz

-- |1 0 -2|

-- |0 3 -1|

-- puede representarse por [[1,0,-2],[0,3,-1]].

-- Definir la función

-- producto :: Num a => [[a]] -> [[a]] -> [[a]]

-- tal que (producto p q) es el producto de las matrices p y q. Por

-- ejemplo,

-- ghci> producto [[1,0,-2],[0,3,-1]] [[0,3],[-2,-1],[0,4]]

-- [[0,-5],[-6,-7]]

Soluciones

import Data.List (transpose)

producto :: Num a => [[a]] -> [[a]] -> [[a]]
producto p q = 
    [[sum [x*y | (x,y) <- zip fil col] | col <- transpose q] | fil <- p]

import Data.List (transpose)

producto :: Num a => [[a]] -> [[a]] -> [[a]]

producto p q =

[[sum [x*y | (x,y) <- zip fil col] | col <- transpose q] | fil <- p]

Sucesiones pucelanas

PorJosé A. Alonso 15-julio-20141-mayo-2015

Introducción

En la Olimpiada de Matemática del 2010 se planteó el siguiente problema:

Una sucesión pucelana es una sucesión creciente de 16 números impares positivos consecutivos, cuya suma es un cubo perfecto. ¿Cuántas sucesiones pucelanas tienen solamente números de tres cifras?

Para resolverlo se propone el siguiente ejercicio.

Enunciado

-- Definir la función
--    pucelanasConNcifras :: Int -> [[Int]]
-- tal que (pucelanasConNcifras n) es la lista de las sucesiones
-- pucelanas que tienen solamente números de n cifras. Por ejemplo,
--    ghci> pucelanasConNcifras 2
--    [[17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47]]
-- Calcular cuántas sucesiones pucelanas tienen solamente números de
-- tres cifras.

-- Definir la función

-- pucelanasConNcifras :: Int -> [[Int]]

-- tal que (pucelanasConNcifras n) es la lista de las sucesiones

-- pucelanas que tienen solamente números de n cifras. Por ejemplo,

-- ghci> pucelanasConNcifras 2

-- [[17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47]]

-- Calcular cuántas sucesiones pucelanas tienen solamente números de

-- tres cifras.

Soluciones

pucelanasConNcifras :: Int -> [[Int]]
pucelanasConNcifras n = 
    [[x,x+2..x+30] | x <- [10^(n-1)+1..10^n-31],
                     esCubo (sum [x,x+2..x+30])]

-- (esCubo n) se verifica si n es un cubo. Por ejemplo,
--    esCubo 27  ==  True
--    esCubo 28  ==  False
esCubo x = y^3 == x
    where y = ceiling (fromIntegral x ** (1/3))

-- El cálculo es
--    ghci> length (pucelanasConNcifras 3)
--    3

pucelanasConNcifras :: Int -> [[Int]]

pucelanasConNcifras n =

[[x,x+2..x+30] | x <- [10^(n-1)+1..10^n-31],

esCubo (sum [x,x+2..x+30])]

-- (esCubo n) se verifica si n es un cubo. Por ejemplo,

-- esCubo 27 == True

-- esCubo 28 == False

esCubo x = y^3 == x

where y = ceiling (fromIntegral x ** (1/3))

-- El cálculo es

-- ghci> length (pucelanasConNcifras 3)

-- 3

Todas tienen par

PorJosé A. Alonso 14-julio-20141-mayo-2015

-- Definir el predicado
--    todasTienenPar :: [[Int]] -> Bool
-- tal que (todasTienenPar xss) se verifica si cada elemento de
-- la lista de listas xss contiene algún número par. Por ejemplo, 
--    todasTienenPar [[1,2],[3,4,5],[8]]  ==  True
--    todasTienenPar [[1,2],[3,5]]        ==  False

-- Definir el predicado

-- todasTienenPar :: [[Int]] -> Bool

-- tal que (todasTienenPar xss) se verifica si cada elemento de

-- la lista de listas xss contiene algún número par. Por ejemplo,

-- todasTienenPar [[1,2],[3,4,5],[8]] == True

-- todasTienenPar [[1,2],[3,5]] == False

Soluciones

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

todasTienenPar :: [[Int]] -> Bool
todasTienenPar xss = and [or [even x | x <- xs] | xs <- xss]

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

todasTienenPar2 :: [[Int]] -> Bool
todasTienenPar2 []       = True
todasTienenPar2 (xs:xss) = tienePar xs && todasTienenPar2 xss

-- (tienePar xs) se verifica si xs contiene algún número par. 
tienePar  :: [Int] -> Bool
tienePar []     = False
tienePar (x:xs) = even x || tienePar xs

-- 3ª definición (por plegado)
-- ===========================

todasTienenPar3 :: [[Int]] -> Bool
todasTienenPar3 = foldr ((&&) . tienePar3) True 

-- (tienePar3 xs) se verifica si xs contiene algún número par. 
tienePar3  :: [Int] -> Bool
tienePar3 = foldr ((||) . even) False 

-- 4ª definición (con cuantificadores)
-- ===================================

todasTienenPar4 :: [[Int]] -> Bool
todasTienenPar4 = all (any even)

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

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

todasTienenPar :: [[Int]] -> Bool

todasTienenPar xss = and [or [even x | x <- xs] | xs <- xss]

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

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

todasTienenPar2 :: [[Int]] -> Bool

todasTienenPar2 [] = True

todasTienenPar2 (xs:xss) = tienePar xs && todasTienenPar2 xss

-- (tienePar xs) se verifica si xs contiene algún número par.

tienePar :: [Int] -> Bool

tienePar [] = False

tienePar (x:xs) = even x || tienePar xs

-- 3ª definición (por plegado)

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

todasTienenPar3 :: [[Int]] -> Bool

todasTienenPar3 = foldr ((&&) . tienePar3) True

-- (tienePar3 xs) se verifica si xs contiene algún número par.

tienePar3 :: [Int] -> Bool

tienePar3 = foldr ((||) . even) False

-- 4ª definición (con cuantificadores)

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

todasTienenPar4 :: [[Int]] -> Bool

todasTienenPar4 = all (any even)

Código Morse

PorJosé A. Alonso 10-julio-201427-diciembre-2014

El código Morse es un sistema de representación de letras y números mediante señales emitidas de forma intermitente.

A los signos (letras mayúsculas o dígitos) se le asigna un código como se muestra a continuación

    +---+-------+---+-------+---+-------+---+-------+
    | A | .-    | J | .---  | S | ...   | 1 | ..--- |
    | B | -...  | K | -.-   | T | -     | 2 | ...-- |
    | C | -.-.  | L | .-..  | U | ..-   | 3 | ....- |
    | D | -..   | M | --    | V | ...-  | 4 | ..... |
    | E | .     | N | -.    | W | .--   | 5 | -.... |
    | F | ..-.  | O | ---   | X | -..-  | 6 | --... |
    | G | --.   | P | .--.  | Y | -.--  | 7 | ---.. |
    | H | ....  | Q | --.-  | Z | --..  | 8 | ----. |
    | I | ..    | R | .-.   | 0 | .---- | 9 | ----- |
    +---+-------+---+-------+---+-------+---+-------+

+---+-------+---+-------+---+-------+---+-------+

| A | .- | J | .--- | S | ... | 1 | ..--- |

| B | -... | K | -.- | T | - | 2 | ...-- |

| C | -.-. | L | .-.. | U | ..- | 3 | ....- |

| D | -.. | M | -- | V | ...- | 4 | ..... |

| E | . | N | -. | W | .-- | 5 | -.... |

| F | ..-. | O | --- | X | -..- | 6 | --... |

| G | --. | P | .--. | Y | -.-- | 7 | ---.. |

| H | .... | Q | --.- | Z | --.. | 8 | ----. |

| I | .. | R | .-. | 0 | .---- | 9 | ----- |

+---+-------+---+-------+---+-------+---+-------+

El código Morse de las palabras se obtiene a partir del de sus caracteres insertando un espacio entre cada uno. Por ejemplo, el código de "todo" es "- --- -.. ---"

El código Morse de las frases se obtiene a partir del de sus palabras insertando dos espacios entre cada uno. Por ejemplo, el código de "todo o nada" es "- --- -.. --- --- -. .- -.. .-"

Enunciado

-- Definir las funciones
--    fraseAmorse :: String -> String
--    morseAfrase :: String -> String
-- tales que
-- * (fraseAmorse cs) es la traducción de la frase cs a Morse. Por
--   ejemplo, 
--      ghci> fraseAmorse "En todo la medida"
--      ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
-- * (morseAfrase cs) es la frase cuya traducción a Morse es cs. Por 
--   ejemplo, 
--      ghci> morseAfrase ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
--      "EN TODO LA MEDIDA"
--
-- Nota: La lista de los códigos Morse de A, B, ..., Z, 0, 1, ..., 9 es
--    [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",
--     "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
--     "..-","...-",".--","-..-","-.--","--..",".----","..---","...--",
--     "....-",".....","-....","--...","---..","----.","-----"]

-- Definir las funciones

-- fraseAmorse :: String -> String

-- morseAfrase :: String -> String

-- tales que

-- * (fraseAmorse cs) es la traducción de la frase cs a Morse. Por

-- ejemplo,

-- ghci> fraseAmorse "En todo la medida"

-- ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

-- * (morseAfrase cs) es la frase cuya traducción a Morse es cs. Por

-- ejemplo,

-- ghci> morseAfrase ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

-- "EN TODO LA MEDIDA"

-- Nota: La lista de los códigos Morse de A, B, ..., Z, 0, 1, ..., 9 es

-- [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",

-- "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",

-- "..-","...-",".--","-..-","-.--","--..",".----","..---","...--",

-- "....-",".....","-....","--...","---..","----.","-----"]

Ayuda: Se puede usar la función splitOn de la librería Data.List.Split.

Soluciones

import Data.Char (toUpper)
import Data.List (intercalate)
import Data.List.Split (splitOn)

-- caracteres es la lista ordenada de las caracteres (letras mayúsculas
-- y dígitos) que se usan en los mensajes Morse.
caracteres :: [Char]
caracteres = ['A'..'Z'] ++ ['0'..'9']

-- morse es la lista de los códigos Morse correspondientes a la lista
-- de caracteres.
morse :: [String]
morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",
         "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
         "..-","...-",".--","-..-","-.--","--..",".----","..---","...--",
         "....-",".....","-....","--...","---..","----.","-----"]

-- (correspondiente xs ys x) es el elemento de ys en la misma posición
-- que x en xs. Por ejemplo,
--    correspondiente [1..10] [2,4..20] 3  ==  6
correspondiente :: Ord a => [a] -> [b] -> a -> b
correspondiente xs ys x = head [y | (z,y) <- zip xs ys, z == x]

-- (caracterAmorse x) es el código Morse correspondiente al carácter
-- x. Por ejemplo, 
--    caracterAmorse 'A'  ==  ".-"
--    caracterAmorse 'B'  ==  "-..."
--    caracterAmorse '1'  ==  "..---"
--    caracterAmorse 'a'  ==  ".-"
caracterAmorse :: Char -> String
caracterAmorse = correspondiente caracteres morse . toUpper

-- (morseAcaracter x) es el carácter cuyo código Morse es x. Por
-- ejemplo,  
--    morseAcaracter ".-"     ==  'A'
--    morseAcaracter "-..."   ==  'B'
--    morseAcaracter "..---"  ==  '1'
morseAcaracter :: String -> Char
morseAcaracter = correspondiente morse caracteres

-- (palabraAmorse cs) es el código Morse correspondiente a la palabra
-- cs. Por ejemplo,
--    palabraAmorse "En"  ==  ". -."
palabraAmorse :: [Char] -> String
palabraAmorse = unwords . map caracterAmorse

-- (morseApalabra cs) es la palabra cuyo traducción a Morse es cs. Por
-- ejemplo, 
--    morseApalabra ". -."  ==  "EN"
morseApalabra :: String -> [Char]
morseApalabra = map morseAcaracter . words

-- (fraseAmorse cs) es la traducción de la frase cs a Morse. Por ejemplo,
--    ghci> fraseAmorse "En todo la medida"
--    ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
fraseAmorse :: String -> String
fraseAmorse = intercalate "  " . map palabraAmorse . words

-- Ejemplo de cálculo
--    fraseAmorse "En todo la medida"
--    = (intercalate "  " . map palabraAmorse . words)
--      "En todo la medida"
--    = (intercalate "  " . map palabraAmorse)
--      ["En","todo","la","medida"]
--    = intercalate "  " [". -.","- --- -.. ---",".-.. .-","-- . -.. .. -.. .-"]
--    = ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
  
-- (morseAfrase cs) es la frase cuya traducción a Morse es cs. Por
-- ejemplo, 
--    ghci> morseAfrase ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
--    "EN TODO LA MEDIDA"
morseAfrase :: String -> String
morseAfrase = unwords . map morseApalabra . splitOn "  "

-- Ejemplo de cálculo
--    morseAfrase ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
--    = (unwords . map morseApalabra)
--      ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
--    = (unwords . map morseApalabra)
--      [". -.","- --- -.. ---",".-.. .-","-- . -.. .. -.. .-"]
--    = unwords ["EN","TODO","LA","MEDIDA"]
--    = "EN TODO LA MEDIDA"

import Data.Char (toUpper)

import Data.List (intercalate)

import Data.List.Split (splitOn)

-- caracteres es la lista ordenada de las caracteres (letras mayúsculas

-- y dígitos) que se usan en los mensajes Morse.

caracteres :: [Char]

caracteres = ['A'..'Z'] ++ ['0'..'9']

-- morse es la lista de los códigos Morse correspondientes a la lista

-- de caracteres.

morse :: [String]

morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",

"-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",

"..-","...-",".--","-..-","-.--","--..",".----","..---","...--",

"....-",".....","-....","--...","---..","----.","-----"]

-- (correspondiente xs ys x) es el elemento de ys en la misma posición

-- que x en xs. Por ejemplo,

-- correspondiente [1..10] [2,4..20] 3 == 6

correspondiente :: Ord a => [a] -> [b] -> a -> b

correspondiente xs ys x = head [y | (z,y) <- zip xs ys, z == x]

-- (caracterAmorse x) es el código Morse correspondiente al carácter

-- x. Por ejemplo,

-- caracterAmorse 'A' == ".-"

-- caracterAmorse 'B' == "-..."

-- caracterAmorse '1' == "..---"

-- caracterAmorse 'a' == ".-"

caracterAmorse :: Char -> String

caracterAmorse = correspondiente caracteres morse . toUpper

-- (morseAcaracter x) es el carácter cuyo código Morse es x. Por

-- ejemplo,

-- morseAcaracter ".-" == 'A'

-- morseAcaracter "-..." == 'B'

-- morseAcaracter "..---" == '1'

morseAcaracter :: String -> Char

morseAcaracter = correspondiente morse caracteres

-- (palabraAmorse cs) es el código Morse correspondiente a la palabra

-- cs. Por ejemplo,

-- palabraAmorse "En" == ". -."

palabraAmorse :: [Char] -> String

palabraAmorse = unwords . map caracterAmorse

-- (morseApalabra cs) es la palabra cuyo traducción a Morse es cs. Por

-- ejemplo,

-- morseApalabra ". -." == "EN"

morseApalabra :: String -> [Char]

morseApalabra = map morseAcaracter . words

-- (fraseAmorse cs) es la traducción de la frase cs a Morse. Por ejemplo,

-- ghci> fraseAmorse "En todo la medida"

-- ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

fraseAmorse :: String -> String

fraseAmorse = intercalate " " . map palabraAmorse . words

-- Ejemplo de cálculo

-- fraseAmorse "En todo la medida"

-- = (intercalate " " . map palabraAmorse . words)

-- "En todo la medida"

-- = (intercalate " " . map palabraAmorse)

-- ["En","todo","la","medida"]

-- = intercalate " " [". -.","- --- -.. ---",".-.. .-","-- . -.. .. -.. .-"]

-- = ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

-- (morseAfrase cs) es la frase cuya traducción a Morse es cs. Por

-- ejemplo,

-- ghci> morseAfrase ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

-- "EN TODO LA MEDIDA"

morseAfrase :: String -> String

morseAfrase = unwords . map morseApalabra . splitOn " "

-- Ejemplo de cálculo

-- morseAfrase ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

-- = (unwords . map morseApalabra)

-- ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"

-- = (unwords . map morseApalabra)

-- [". -.","- --- -.. ---",".-.. .-","-- . -.. .. -.. .-"]

-- = unwords ["EN","TODO","LA","MEDIDA"]

-- = "EN TODO LA MEDIDA"

Inserción en árboles binarios de búsqueda

Soluciones

Producto de matrices como listas de listas

Soluciones

Sucesiones pucelanas

Introducción

Enunciado

Soluciones

Todas tienen par

Soluciones

Código Morse

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico