Ir al contenido principal

Mayor producto de las ramas de un árbol


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

mayorProducto :: (Ord a, Num a) => Arbol a -> a

tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,

λ> mayorProducto (N 1 [N 2 [], N  3 []])
3
λ> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
12
λ> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
12
λ> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
90
λ> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])
0
λ> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]
λ> mayorProducto a
84

Leer más…

Número de pares de elementos adyacentes iguales en una matriz


Una matriz se puede representar mediante una lista de listas. Por ejemplo, la matriz

|2 1 5|
|4 3 7|

se puede representar mediante la lista

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

Definir la función

numeroParesAdyacentesIguales :: Eq a => [[a]] -> Int

tal que (numeroParesAdyacentesIguales xss) es el número de pares de elementos consecutivos (en la misma fila o columna) iguales de la matriz xss. Por ejemplo,

numeroParesAdyacentesIguales [[0,1],[0,2]]              ==  1
numeroParesAdyacentesIguales [[0,0],[1,2]]              ==  1
numeroParesAdyacentesIguales [[0,1],[0,0]]              ==  2
numeroParesAdyacentesIguales [[1,2],[1,4],[4,4]]        ==  3
numeroParesAdyacentesIguales ["ab","aa"]                ==  2
numeroParesAdyacentesIguales [[0,0,0],[0,0,0],[0,0,0]]  ==  12
numeroParesAdyacentesIguales [[0,0,0],[0,1,0],[0,0,0]]  ==  8

Leer más…

Elemento más repetido de manera consecutiva


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 mayor de dichos elementos. Por ejemplo,

masRepetido [1,1,4,4,1]  ==  (4,2)
masRepetido [4,4,1,1,5]  ==  (4,2)
masRepetido "aadda"      ==  ('d',2)
masRepetido "ddaab"      ==  ('d',2)
masRepetido (show (product [1..5*10^4]))  ==  ('0',12499)

Leer más…

Regiones determinadas por n rectas del plano


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 1     ==  2
regiones 2     ==  4
regiones 3     ==  7
regiones 100   ==  5051
regiones 1000  ==  500501
regiones 10000 ==  50005001
length (show (regiones (10^(10^5)))) ==  200000
length (show (regiones (10^(10^6)))) ==  2000000
length (show (regiones (10^(10^7)))) ==  20000000

Leer más…

Ampliación de matrices por columnas


Las matrices enteras se pueden representar mediante tablas con índices enteros:

type Matriz = Array (Int,Int) Int

Definir la función

ampliaColumnas :: Matriz -> Matriz -> Matriz

tal que (ampliaColumnas p q) es la matriz construida añadiendo las columnas de la matriz q a continuación de las de p (se supone que tienen el mismo número de filas). Por ejemplo, si p y q representa las dos primeras matrices, entonces (ampliaColumnas p q) es la tercera

|0 1|    |4 5 6|    |0 1 4 5 6|
|2 3|    |7 8 9|    |2 3 7 8 9|

En Haskell, se definen las dos primeras matrices se definen por

ej1 = listArray ((1,1),(2,2)) [0..3]
ej2 = listArray ((1,1),(2,3)) [4..9]

y el cálculo de la tercera es

λ> ampliaColumnas ej1 ej2
array ((1,1),(2,5)) [((1,1),0),((1,2),1),((1,3),4),((1,4),5),((1,5),6),
                     ((2,1),2),((2,2),3),((2,3),7),((2,4),8),((2,5),9)]
λ> elems (ampliaColumnas ej1 ej2)
[0,1,4,5,6,2,3,7,8,9]

Leer más…

Emparejamiento binario


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 [(<), (==), (==)] "coloca" "lobo"  == [True,True,False]

Leer más…

Ordenación de estructuras


Las notas de los dos primeros exámenes se pueden representar mediante el siguiente tipo de dato

data Notas = Notas String Int Int
  deriving (Read, Show, Eq)

Por ejemplo, (Notas "Juan" 6 5) representar las notas de un alumno cuyo nombre es Juan, la nota del primer examen es 6 y la del segundo es 5.

Definir la función

ordenadas :: [Notas] -> [Notas]

tal que (ordenadas ns) es la lista de las notas ns ordenadas considerando primero la nota del examen 2, a continuación la del examen 1 y finalmente el nombre. Por ejemplo,

λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 3 7]
[Notas "Juan" 6 5,Notas "Luis" 3 7]
λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 3 4]
[Notas "Luis" 3 4,Notas "Juan" 6 5]
λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 7 4]
[Notas "Luis" 7 4,Notas "Juan" 6 5]
λ> ordenadas [Notas "Juan" 6 4, Notas "Luis" 7 4]
[Notas "Juan" 6 4,Notas "Luis" 7 4]
λ> ordenadas [Notas "Juan" 6 4, Notas "Luis" 5 4]
[Notas "Luis" 5 4,Notas "Juan" 6 4]
λ> ordenadas [Notas "Juan" 5 4, Notas "Luis" 5 4]
[Notas "Juan" 5 4,Notas "Luis" 5 4]
λ> ordenadas [Notas "Juan" 5 4, Notas "Eva" 5 4]
[Notas "Eva" 5 4,Notas "Juan" 5 4]

Leer más…

Numeración de las ternas de números naturales


Las ternas de números naturales se pueden ordenar como sigue

(0,0,0),
(0,0,1),(0,1,0),(1,0,0),
(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),
(0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...
...

Definir la función

posicion :: (Int,Int,Int) -> Int

tal que posicion (x,y,z) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,

posicion (0,1,0)  ==  2
posicion (0,0,2)  ==  4
posicion (0,1,1)  ==  5

Comprobar con QuickCheck que

  • la posición de (x,0,0) es x(x²+6x+11)/6
  • la posición de (0,y,0) es y(y²+3y+ 8)/6
  • la posición de (0,0,z) es z(z²+3z+ 2)/6
  • la posición de (x,x,x) es x(9x²+14x+7)/2

Leer más…

Alfabeto comenzando en un carácter


Definir la función

alfabetoDesde :: Char -> String

tal que (alfabetoDesde c) es el alfabeto, en minúscula, comenzando en el carácter c, si c es una letra minúscula y comenzando en 'a', en caso contrario. Por ejemplo,

alfabetoDesde 'e'  ==  "efghijklmnopqrstuvwxyzabcd"
alfabetoDesde 'a'  ==  "abcdefghijklmnopqrstuvwxyz"
alfabetoDesde '7'  ==  "abcdefghijklmnopqrstuvwxyz"
alfabetoDesde '{'  ==  "abcdefghijklmnopqrstuvwxyz"
alfabetoDesde 'B'  ==  "abcdefghijklmnopqrstuvwxyz"

Leer más…

Ramas de un árbol


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]]

Leer más…

Valores de polinomios representados con vectores


Los polinomios se pueden representar mediante vectores usando la librería Data.Array. En primer lugar, se define el tipo de los polinomios (con coeficientes de tipo a) mediante

type Polinomio a = Array Int a

Como ejemplos, definimos el polinomio

ej_pol1 :: Array Int Int
ej_pol1 = array (0,4) [(1,2),(2,-5),(4,7),(0,6),(3,0)]

que representa a \(2x - 5x^2 + 7x^4 + 6\) y el polinomio

ej_pol2 :: Array Int Double
ej_pol2 = array (0,4) [(1,2),(2,-5.2),(4,7),(0,6.5),(3,0)]

que representa a \(2x - 5.2x^2 + 7x^4 + 6.5\).

Definir la función

valor :: Num a => Polinomio a -> a -> a

tal que (valor p b) es el valor del polinomio p en el punto b. Por ejemplo,

valor ej_pol1 0  ==  6
valor ej_pol1 1  ==  10
valor ej_pol1 2  ==  102
valor ej_pol2 0  ==  6.5
valor ej_pol2 1  ==  10.3
valor ej_pol2 3  ==  532.7

Leer más…

Lista cuadrada


Definir la función

listaCuadrada :: Int -> a -> [a] -> [[a]]

tal que (listaCuadrada n x xs) es una lista de n listas de longitud n formadas con los elementos de xs completada con x, si no xs no tiene suficientes elementos. Por ejemplo,

listaCuadrada 3 7 [0,3,5,2,4]  ==  [[0,3,5],[2,4,7],[7,7,7]]
listaCuadrada 3 7 [0..]        ==  [[0,1,2],[3,4,5],[6,7,8]]
listaCuadrada 2 'p' "eva"      ==  ["ev","ap"]
listaCuadrada 2 'p' ['a'..]    ==  ["ab","cd"]

Leer más…

Máximos locales


Un máximo local de una lista es un elemento de la lista que es que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

maximosLocales :: Ord a => [a] -> [a]

tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,

maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
maximosLocales [1..100]             ==  []
maximosLocales "adbpmqexyz"         ==  "dpq"

Leer más…

Matrices de Toepliz


Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

|2 5 1 6|       |2 5 1 6|
|4 2 5 1|       |4 2 6 1|
|7 4 2 5|       |7 4 2 5|
|9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,

esToeplitz ej1  ==  True
esToeplitz ej2  ==  False

Leer más…

Primos equidistantes


Definir la función

primosEquidistantes :: Integer -> [(Integer,Integer)]

tal que (primosEquidistantes k) es la lista de los pares de primos cuya diferencia es k. Por ejemplo,

take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]

Leer más…

29-Anagramas


Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, mora y roma son anagramas de amor.

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Leer más…

Mastermind


El Mastermind es un juego que consiste en deducir un numérico formado por una lista de números distintos. Cada vez que se empieza una partida, el programa debe elegir un código, que será lo que el jugador debe adivinar en la menor cantidad de intentos posibles. Cada intento consiste en una propuesta de un código posible que propone el jugador, y una respuesta del programa. Las respuestas le darán pistas al jugador para que pueda deducir el código.

Estas pistas indican cuán cerca estuvo el número propuesto de solución a través de dos valores: la cantidad de aciertos es la cantidad de dígitos que propuso el jugador que también están en el código en la misma posición. La cantidad de coincidencias es la cantidad de digitos que propuso el jugador que también están en el código pero en una posición distinta.

Por ejemplo, si el código que eligió el programa es el [2,6,0,7], el jugador propone el [1,4,0,6], el programa le debe responder acierto (el 0, que está en el código original en el mismo lugar, tercero), y una coincidencia (el 6, que también está en el original, pero en la segunda posición, no en el cuarto como fue propuesto). Si el jugador hubiera propuesto el [3,5,9,1], habría obtenido como respuesta ningún acierto y ninguna coincidencia, ya que no hay números en común con el código original, y si se obtienen cuatro aciertos es porque el jugador adivinó el código y ganó el juego.

Definir la función

mastermind :: [Int] -> [Int] -> (Int,Int)

tal que (mastermind xs ys) es el par formado por los números de aciertos y de coincidencias entre xs e ys. Por ejemplo,

mastermind [2,6,0,7] [1,4,0,6]  ==  (1,1)
mastermind [2,6,0,7] [3,5,9,1]  ==  (0,0)
mastermind [2,6,0,7] [1,6,0,4]  ==  (2,0)
mastermind [2,6,0,7] [2,6,0,7]  ==  (4,0)

Leer más…

La bandera tricolor


El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista ys que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.

Definir el tipo de dato Color para representar los colores con los constructores R, A y M correspondientes al rojo, azul y morado y la función

banderaTricolor :: [Color] -> [Color]

tal que (banderaTricolor xs) es la bandera tricolor formada con los elementos de xs. Por ejemplo,

bandera [M,R,A,A,R,R,A,M,M]  ==  [R,R,R,A,A,A,M,M,M]
bandera [M,R,A,R,R,A]        ==  [R,R,R,A,A,M]

Leer más…

Ejercicios del curso 2013-14

Como se comenta en la presentación del blog, su objetivo es complementar el curso de Informática proponiendo un ejercicio diario teniendo en cuenta lo que se ha estudiado hasta ese momento.

Para situar los ejercicios en su contexto se debe de tener presente

  • la página del curso en la que se encuentra los temas, las relaciones de ejercicios y los exámenes;
  • el diario de clases en la que se resume el contenido de cada clase.

El cronograma de las clases es el siguiente, donde los temas se representan con T y las relaciones de problemas con R. Por ejemplo,

  • T2 representa que se ha estudiado el tema 2.
  • R1 representa que se ha estudiado la relación 1.
  • T4[1,14] representa que se ha estudiado el tema 4 desde la transparencia 1 a la 24.
  • R2[9,12] representa que se ha estudiado la relación 2 desde la el ejercicio 9 al 12.
Día Contenido
M-24-Sep-13 T2: Introducción a la programación con Haskell.
V-27-Sep-13 R1: Definiciones por composición con aritmética.
M-01-Oct-13 R2[1,8]: Definiciones por composición con listas.
  T4[1,14]: Definiciones de funciones.
V-04-Oct-13 R2[9,12]: Definiciones por composición con listas.
  R3[1,5]: Definiciones con condicionales.
M-08-Oct-13 T5[1,13]: Definiciones por comprensión.
  R3[6,19]: Definiciones con condicionales.
11-Oct-13 R4[1,7]: Definiciones por comprensión.
15-Oct-13 R4[8,14]: Definiciones por comprensión.
  Introducción a las gráficas con gnuplot.
18-Oct-13 R4[15,19]: Definiciones por comprensión.
22-Oct-13 T5[14,29]: Código César.
25-Oct-13 R4[20,21]: Definiciones por comprensión.
  R5[1,7]: Definiciones por comprensión.
29-Oct-13 T3: Tipos y clases.
05-Nov-13 Examen 1
08-Nov-13 R5[8,14.1]: Definiciones por comprensión.
12-Nov-13 T6[1,10]: Definiciones por recursión.
19-Nov-13 T6[11,24]: Definiciones por comprensión.
22-Nov-13 R7+R8[1,3]: Definiciones por recursión.
26-Nov-13 R9: Ordenación por mezclas y QuickCheck.
29-Nov-13 R8[4,8]: Definiciones por recursión.
  R10[1,5.3]: Definiciones por comprensión y recursión.
03-Dic-13 R10[6,17]: Definiciones por comprensión y recursión.
  R11[1,5]: Definiciones por comprensión y recursión.
10-Dic-13 T7[1,23]: Funciones de orden superior.
13-Dic-13 R12[1,5]: Funciones de orden superior.
17-Dic-13 Examen 2
20-Dic-13 R12[6,11]: Funciones de orden superior.
07-Ene-14 T10: Evaluación perezosa.
  T7[23,27]: Cambio de base.
10-Ene-14 R13: Funciones de orden superior (2).
  R14: Funciones sobre cadenas.
14-Ene-14 T7[28,36]: Codificación binaria y transmisión de cadenas.
  R15[1,3.2]: Evaluación perezosa y listas infinitas (1).
17-Ene-14 R15[4,7.5]: Evaluación perezosa y listas infinitas (2).
  R16[1,4.2]: Evaluación perezosa y listas infinitas (3).
-Ene-14 Examen 3
11-Feb-14 T9[1,26]: Declaraciones de tipos y clases.
15-Feb-14 R17[1,2.5]: Evaluación perezosa y listas infinitas.
18-Feb-14 T11: Aplicaciones de la programación funcional.
22-Feb-14 R18+R19[1,6]: Tipos de datos algebraicos.
25-Feb-14 R20: Cálculo numérico.
  R19[7,10]: Árboles binarios.
  R17[3,3]: Triángulo de Pascal.
04-Mar-14 T21[1,41]: El TAD de los polinomios.
07-Mar-14 R22: Combinatoria.
11-Mar-14 T21[41,55]: Operaciones con polinomios.
  R17[6.1,6.13]: El triángulo de Floyd.
14-Mar-14 R22+R23: Operaciones con polinomios.
18-Mar-14 R17[4,5]: Codificación por longitud y autocontadora.
21-Mar-14 Examen 4
25-Mar-14 T18[1,18]: La librería de las tablas.
28-Mar-14 R26[1,10]: Vectores y matrices.
01-Abr-14 T18[19,19]: El TAD de las tablas.
04-Abr-14 R26[11,24]: Vectores y matrices (2).
08-Abr-14 T22[1,39]: Grafos.
11-Abr-14 R26: Implementación de grafos con listas.
22-Abr-14 T17[1,29]: El TAD de los conjuntos.
  R27[1,4]: Ejercicios sobre grafos.
25-Abr-14 R27[5,22]: Ejercicios sobre grafos.
29-Abr-14 Exercitium: Ejercicios del 21 al 25 de abril.
13-May-14 R28: Operaciones con conjuntos.
  R29: Relaciones binarias.
16-May-14 Examen 5
20-May-14 Programación de dibujos con Gloss
27-May-14 Programación de fractales.
03-Jun-14 Programación de fractales.
06-Jun-14 Relación con dibujos y fractales.

Exercitium (Un reto diario de programación)

La programación informática, como cualquier disciplina creativa, requiere estudio y práctica constantes. Este blog publica ejercicios de programación diariamente para que los programadores, independientemente de su nivel de experiencia, puedan mantener y perfeccionar sus habilidades, explorando soluciones más allá de sus zonas de confort habituales.

Objetivo y enfoque

Estos ejercicios no constituyen un concurso. Fueron originalmente diseñados para los estudiantes de la asignatura de Informática de 1º del Grado en Matemáticas. No se otorgan puntuaciones ni se mantiene un registro de quienes los completan. La verdadera recompensa es el conocimiento adquirido y la mejora de tus habilidades como programador.

Cada ejercicio está concebido para resolverse en aproximadamente quince minutos, aunque el tiempo real puede variar desde unos pocos minutos hasta varias horas, dependiendo de la experiencia individual, la creatividad y los recursos disponibles.

Antes de consultar las soluciones propuestas, te recomendamos intentar resolver el ejercicio por tu cuenta. Una vez completado, podrás comparar tu enfoque con las soluciones sugeridas.

Múltiples soluciones y enfoques

No existe una única solución "correcta" o perfecta para ejercicios. De hecho, te animamos a explorar diferentes enfoques una vez completado un ejercicio: puedes intentarlo con un algoritmo distinto o utilizando otro lenguaje de programación. También puedes compartir y discutir tus soluciones en Mastodon o en Bluesky.

La mayoría de las soluciones propuestas están implementadas en Haskell. Sin embargo, estos ejercicios son una excelente oportunidad para:

  • Perfeccionar tus habilidades en tu lenguaje de programación habitual
  • Aprender un nuevo lenguaje de programación
  • Comparar implementaciones en diferentes lenguajes

Recursos adicionales

Si eres estudiante principiante, especialmente si estás aprendiendo Haskell como primer lenguaje, te recomendamos consultar Programación funcional con Haskell. Este material ha sido la base del primer curso de informática en el Grado en Matemáticas de la Universidad de Sevilla durante muchos años.

Todas las soluciones están disponibles en GitHub como un proyecto con Stack, lo que evita problemas de compatibilidad entre diferentes versiones de las bibliotecas utilizadas.

Puedes suscribirte al canal RSS de este blog en https://jaalonso.github.io/exercitium/rss.xml.