Los árboles binarios con datos en los nodos se definen por

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Eq, Show)

Por ejemplo, el árbol

       3
      / \
     /   \
    0     5
   / \   / \
  5   4 0   3
 / \
2   0

se representa por

ejArbol :: Arbol Int
ejArbol = N 3
            (N 0
               (N 5
                  (N 2 H H)
                  (N 4 H H))
               (N 0 H H))
            (N 5
               (N 0 H H)
               (N 3 H H))

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 4 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

data Movimiento = I | D deriving (Show, Eq)
type Posicion   = [Movimiento]

Definir la función

posiciones :: Eq b => b -> Arbol b -> [Posicion]

tal que (posiciones n a) es la lista de las posiciones del elemento n en el árbol a. Por ejemplo,

posiciones 0 ejArbol  ==  [[I],[I,D],[D,I]]
posiciones 2 ejArbol  ==  [[I,I,I]]
posiciones 3 ejArbol  ==  [[],[D,D]]
posiciones 4 ejArbol  ==  [[I,I,D]]
posiciones 5 ejArbol  ==  [[I,I],[D]]
posiciones 1 ejArbol  ==  []

Leer más…

Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

        1
       /  \
      /    \
     /      \
    2        3
   / \      / \
  4   5    6   7
 / \
8   9

Los árboles binarios se puede representar mediante el siguiente tipo

data Arbol = H
           | N Int Arbol Arbol
  deriving (Show, Eq)

Definir la función

arbolBinarioCompleto :: Int -> Arbol

tal que (arbolBinarioCompleto n) es el árbol binario completo con n nodos. Por ejemplo,

λ> arbolBinarioCompleto 4
N 1 (N 2 (N 4 H H) H) (N 3 H H)
λ> arbolBinarioCompleto 9
N 1
  (N 2
     (N 4
        (N 8 H H)
        (N 9 H H))
     (N 5 H H))
  (N 3
     (N 6 H H)
     (N 7 H H))

Leer más…

Un número x es un cubo si existe un y tal que x = y^3. Por ejemplo, 8 es un cubo porque 8 = 2^3.

Definir la función

raizCubicaEntera :: Integer -> Maybe Integer.

tal que (raizCubicaEntera x n) es justo la raíz cúbica del número natural x, si x es un cubo y Nothing en caso contrario. Por ejemplo,

raizCubicaEntera 8             ==  Just 2
raizCubicaEntera 9             ==  Nothing
raizCubicaEntera 27            ==  Just 3
raizCubicaEntera 64            ==  Just 4
raizCubicaEntera (2^30)        ==  Just 1024
raizCubicaEntera (10^9000)     ==  Just (10^3000)
raizCubicaEntera (5 + 10^9000) ==  Nothing

Leer más…

Se dice que un número natural n es una colina si su primer dígito es igual a su último dígito, los primeros dígitos son estrictamente creciente hasta llegar al máximo, el máximo se puede repetir y los dígitos desde el máximo al final son estrictamente decrecientes.

Definir la función

esColina :: Integer -> Bool

tal que (esColina n) se verifica si n es un número colina. Por ejemplo,

esColina 12377731  ==  True
esColina 1237731   ==  True
esColina 123731    ==  True
esColina 12377730  ==  False
esColina 12377730  ==  False
esColina 10377731  ==  False
esColina 12377701  ==  False
esColina 33333333  ==  True

Leer más…

Definir la función

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

tal que (solitario xs) es el único elemento que ocurre una vez en la lista xs (se supone que la lista xs tiene al menos 3 elementos y todos son iguales menos uno que es el solitario). Por ejemplo,

solitario [2,2,7,2]  ==  7
solitario [2,2,2,7]  ==  7
solitario [7,2,2,2]  ==  7
solitario (replicate (2*10^7) 1 ++ [2])  ==  2

Leer más…

Esta semana se ha publicado en Twitter una demostración visual de la suma de inversos de potencias de 4:

1/4 + 1/4² + 1/4³ + ... = 1/3

Definir las funciones

sumaInversosPotenciasDeCuatro :: [Double]
aproximacion :: Double -> Int

tales que

• sumaInversosPotenciasDeCuatro es la lista de las suma de la serie de los inversos de las potencias de cuatro. Por ejemplo,

λ> take 6 sumaInversosPotenciasDeCuatro
[0.25,0.3125,0.328125,0.33203125,0.3330078125,0.333251953125]

• (aproximacion e) es el menor número de términos de la serie anterior que hay que sumar para que el valor absoluto de su diferencia con 1/3 sea menor que e. Por ejemplo,

aproximacion 0.001  ==  4
aproximacion 1e-3   ==  4
aproximacion 1e-6   ==  9
aproximacion 1e-20  ==  26
sumaInversosPotenciasDeCuatro !! 26  ==  0.3333333333333333

Leer más…

Definir las funciones

esPrimoSumaDeDosPrimos :: Integer -> Bool

primosSumaDeDosPrimos :: [Integer] tales que

• (esPrimoSumaDeDosPrimos x) se verifica si x es un número primo que se puede escribir como la suma de dos números primos. Por ejemplo,

esPrimoSumaDeDosPrimos 19  ==  True
esPrimoSumaDeDosPrimos 20  ==  False
esPrimoSumaDeDosPrimos 23  ==  False

• primosSumaDeDosPrimos es la lista de los números primos que se pueden escribir como la suma de dos números primos. Por ejemplo,

λ> take 17 primosSumaDeDosPrimos
[5,7,13,19,31,43,61,73,103,109,139,151,181,193,199,229,241]
λ> primosSumaDeDosPrimos !! (10^5)
18409543

Leer más…

Definir la función

cerosDelFactorial :: Integer -> Integer

tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,

cerosDelFactorial 24                           ==  4
cerosDelFactorial 25                           ==  6
length (show (cerosDelFactorial (1234^5678)))  ==  17552

Leer más…

Dos elementos están relacionados por una partición xss si pertenecen al mismo elemento de xss.

Definir la función

relacionados :: Eq a => [[a]] -> a -> a -> Bool

tal que (relacionados xss y z) se verifica si los elementos y y z están relacionados por la partición xss. Por ejemplo,

relacionados [[1,3],[2],[9,5,7]] 7 9  ==  True
relacionados [[1,3],[2],[9,5,7]] 3 9  ==  False
relacionados [[1,3],[2],[9,5,7]] 4 9  ==  False

Leer más…

Definir la función

nParejas :: Ord a => [a] -> Int

tal que (nParejas xs) es el número de parejas de elementos iguales en xs. Por ejemplo,

nParejas [1,2,2,1,1,3,5,1,2]        ==  3
nParejas [1,2,1,2,1,3,2]            ==  2
nParejas [1..2*10^6]                ==  0
nParejas2 ([1..10^6] ++ [1..10^6])  ==  1000000

En el primer ejemplos las parejas son (1,1), (1,1) y (2,2). En el segundo ejemplo, las parejas son (1,1) y (2,2).

Comprobar con QuickCheck que para toda lista de enteros xs, el número de parejas de xs es igual que el número de parejas de la inversa de xs.

Leer más…

Un número n es autodescriptivo cuando para cada posición k de n (empezando a contar las posiciones a partir de 0), el dígito en la posición k es igual al número de veces que ocurre k en n. Por ejemplo, 1210 es autodescriptivo porque tiene 1 dígito igual a "0", 2 dígitos iguales a "1", 1 dígito igual a "2" y ningún dígito igual a "3".

Definir la función

autodescriptivo :: Integer -> Bool

tal que (autodescriptivo n) se verifica si n es autodescriptivo. Por ejemplo,

λ> autodescriptivo 1210
True
λ> [x | x <- [1..100000], autodescriptivo x]
[1210,2020,21200]
λ> autodescriptivo 9210000001000
True

Nota: se puede usar la función genericLength.

Leer más…

Leer más…

Un número entero positivo es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

libreDeCuadrados :: Integer -> Bool

tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,

libreDeCuadrados 70                    ==  True
libreDeCuadrados 40                    ==  False
libreDeCuadrados 510510                ==  True
libreDeCuadrados (((10^10)^10)^10)     ==  False

Leer más…

La diferencia simétrica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica de {2,5,3} y {4,2,3,7} es {4,5,7}.

Definir la función

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

tal que (diferenciaSimetrica xs ys) es la diferencia simétrica de xs e ys. Por ejemplo,

diferenciaSimetrica [2,5,3] [4,2,3,7]    ==  [4,5,7]
diferenciaSimetrica [2,5,3] [5,2,3]      ==  []
diferenciaSimetrica [2,5,2] [4,2,3,7]    ==  [3,4,5,7]
diferenciaSimetrica [2,5,2] [4,2,4,7]    ==  [4,5,7]
diferenciaSimetrica [2,5,2,4] [4,2,4,7]  ==  [5,7]

Leer más…

El factorial de 7 es

7! = 1·2·3·4·5·6·7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

ultimoNoNuloFactorial  7  == 4
ultimoNoNuloFactorial 10  == 8
ultimoNoNuloFactorial 12  == 6
ultimoNoNuloFactorial 97  == 2
ultimoNoNuloFactorial  0  == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Leer más…

La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).

Definir la función

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

tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,

distancia "romano" "comino"  ==  2
distancia "romano" "camino"  ==  3
distancia "roma"   "comino"  ==  2
distancia "roma"   "camino"  ==  3
distancia "romano" "ron"     ==  1
distancia "romano" "cama"    ==  2
distancia "romano" "rama"    ==  1

Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad

distancia(xs,ys) = 0 si, y sólo si, xs = ys

y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.

Leer más…

Una lista de números naturales es equidigital si todos sus elementos tienen el mismo número de dígitos.

Definir la función

equidigital :: [Int] -> Bool

tal que (equidigital xs) se verifica si xs es una lista equidigital. Por ejemplo,

equidigital [343,225,777,943]   ==  True
equidigital [343,225,777,94,3]  ==  False

Leer más…

Un número medio es número natural que es igual a la media aritmética de las permutaciones de sus dígitos. Por ejemplo, 370 es un número medio ya que las permutaciones de sus dígitos es 073, 037, 307, 370, 703 y 730 cuya media es 2220/6 que es igual a 370.

Definir las siguientes funciones

numeroMedio                :: Integer -> Bool
densidadesNumeroMedio      :: [Double]
graficaDensidadNumeroMedio :: Int -> IO ()

tales que

• (numeroMedio n) se verifica si n es un número medio. Por ejemplo,

λ> numeroMedio 370
True
λ> numeroMedio 371
False
λ> numeroMedio 485596707818930041152263374
True
λ> filter numeroMedio [100..600]
[111,222,333,370,407,444,481,518,555,592]
λ> filter numeroMedio [3*10^5..6*10^5]
[333333,370370,407407,444444,481481,518518,555555,592592]

• densidades es la lista cuyo elemento n-ésimo (empezando a contar en 1) es la densidad de números medios en el intervalo [1,n]; es decir, la cantidad de números medios menores o iguales que n dividida por n. Por ejemplo,

λ> mapM_ print (take 30 densidades)
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.9
0.9090909090909091
0.8333333333333334
0.7692307692307693
0.7142857142857143
0.6666666666666666
0.625
0.5882352941176471
0.5555555555555556
0.5263157894736842
0.5
0.47619047619047616
0.5
0.4782608695652174
0.4583333333333333
0.44
0.4230769230769231
0.4074074074074074
0.39285714285714285
0.3793103448275862
0.36666666666666664

• (graficaDensidadNumeroMedio n) dibuja la gráfica de las densidades de los intervalos [1,k] para k desde 1 hasta n. Por ejemplo, (graficaDensidadNumeroMedio 100) dibuja

y (graficaDensidadNumeroMedio 1000) dibuja

Leer más…

Si n es el número natural cuya expansión decimal es abc... , el tren de potencias de n es a^bc^d... donde el último exponente es 1, si n tiene un número impar de dígitos. Por ejemplo

trenDePotencias 2453  = 2^4*5^3     = 2000
trenDePotencias 24536 = 2^4*5^3*6^1 = 12000

Definir las funciones

trenDePotencias            :: Integer -> Integer
esPuntoFijoTrenDePotencias :: Integer -> Bool
puntosFijosTrenDePotencias :: [Integer]
tablaTrenDePotencias       :: Integer -> Integer -> IO ()

tales que

• (trenDePotencias n) es el tren de potencia de n. Por ejemplo.

trenDePotencias 20   ==  1
trenDePotencias 21   ==  2
trenDePotencias 24   ==  16
trenDePotencias 39   ==  19683
trenDePotencias 623  ==  108

• (esPuntoFijoTrenDePotencias n) se verifica si n es un punto fijo de trenDePotencias; es decir, (trenDePotencias n) es igual a n. Por ejemplo,

esPuntoFijoTrenDePotencias 2592                        ==  True
esPuntoFijoTrenDePotencias 24547284284866560000000000  ==  True

• puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,

take 10 puntosFijosTrenDePotencias  ==  [1,2,3,4,5,6,7,8,9,2592]

• (tablaTrenDePotencias a b) es la tabla de los trenes de potencias de los números entre a y b. Por ejemplo,

λ> tablaTrenDePotencias 20 39
| 20 |     1 |
| 21 |     2 |
| 22 |     4 |
| 23 |     8 |
| 24 |    16 |
| 25 |    32 |
| 26 |    64 |
| 27 |   128 |
| 28 |   256 |
| 29 |   512 |
| 30 |     1 |
| 31 |     3 |
| 32 |     9 |
| 33 |    27 |
| 34 |    81 |
| 35 |   243 |
| 36 |   729 |
| 37 |  2187 |
| 38 |  6561 |
| 39 | 19683 |
λ> tablaTrenDePotencias 2340 2359
| 2340 |        8 |
| 2341 |       32 |
| 2342 |      128 |
| 2343 |      512 |
| 2344 |     2048 |
| 2345 |     8192 |
| 2346 |    32768 |
| 2347 |   131072 |
| 2348 |   524288 |
| 2349 |  2097152 |
| 2350 |        8 |
| 2351 |       40 |
| 2352 |      200 |
| 2353 |     1000 |
| 2354 |     5000 |
| 2355 |    25000 |
| 2356 |   125000 |
| 2357 |   625000 |
| 2358 |  3125000 |
| 2359 | 15625000 |

Comprobar con QuickCheck que entre 2593 y 24547284284866559999999999 la función trenDePotencias no tiene puntos fijos.

Leer más…

Leer más…

La cadena infinita "1234321234321234321...", formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la serie de los números naturales, como se observa a continuación:

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ...
1, 2, 3, 4,  5,   6,  7,    8,   9,   10,    11, ...

Definir la lista

reloj :: [Integer]

cuyos elementos son los términos de la sucesión anterior. Por ejemplo,

λ> take 11 reloj
[1,2,3,4,32,123,43,2123,432,1234,32123]

Leer más…

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

type Punto = (Int,Int)
type Mapa  = Array Punto Int

mapa1, mapa2 :: Mapa
mapa1 = listArray ((1,1),(3,4))
                  [1,1,0,0,
                   0,1,0,0,
                   1,0,0,0]
mapa2 = listArray ((1,1),(10,20))
                  [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
                   0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

Definir las funciones

alcanzables :: Mapa -> Punto -> [Punto]
esAlcanzable :: Mapa -> Punto -> Punto -> Bool

tales que

• (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,

alcanzables mapa1 (1,1)  ==  [(2,2),(1,2),(1,1)]
alcanzables mapa1 (1,2)  ==  [(2,2),(1,1),(1,2)]
alcanzables mapa1 (1,3)  ==  [(3,2),(3,4),(3,3),(2,3),(2,4),(1,4),(1,3)]
alcanzables mapa1 (3,1)  ==  [(3,1)]

• (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,

esAlcanzable mapa1 (1,4) (3,2)    ==  True
esAlcanzable mapa1 (1,4) (3,1)    ==  False
esAlcanzable mapa2 (2,3) (8,16)   ==  True
esAlcanzable mapa2 (8,1) (7,3)    ==  True
esAlcanzable mapa2 (1,1) (10,20)  ==  False

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Leer más…

El recorrido en ZigZag de una matriz consiste en pasar de la primera fila hasta la última, de izquierda a derecha en las filas impares y de derecha a izquierda en las filas pares, como se indica en la figura.

/             \
| 1 -> 2 -> 3 |
|           | |
|           v |
| 4 <- 5 <- 6 |   =>  Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]
| |           |
| v           |
| 7 -> 8 -> 9 |
\             /

Definir la función

recorridoZigZag :: Matrix a -> [a]

tal que (recorridoZigZag m) es la lista con los elementos de la matriz m cuando se recorre esta en ZigZag. Por ejemplo,

λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])
[1,2,3,6,5,4,7,8,9]
λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])
[1,2,4,3,5,6,8,7]
λ> recorridoZigZag (fromLists [[1,2,3,4],[5,6,7,8],[9,10,11,12]])
[1,2,3,4,8,7,6,5,9,10,11,12]
λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")
"Cadasap o es al meta"
λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")
"Cada  osapes laatem "
λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")
"Caad psao se l ameat"
λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")
"Cada paso atem al se"

Leer más…

Definir la función

sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

λ> sinDobleCero 2
[[1,0],[1,1],[0,1]]
λ> sinDobleCero 3
[[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
λ> sinDobleCero 4
[[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
 [0,1,1,0],[0,1,1,1],[0,1,0,1]]

Leer más…

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

( 0 1 0 )
( 1 0 0 )
( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

torres  :: Int -> [Matrix Int]
nTorres :: Int -> Integer

tales que + (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

λ> torres 3
[( 1 0 0 )
( 0 1 0 )
( 0 0 1 )
,( 1 0 0 )
( 0 0 1 )
( 0 1 0 )
,( 0 1 0 )
( 1 0 0 )
( 0 0 1 )
,( 0 1 0 )
( 0 0 1 )
( 1 0 0 )
,( 0 0 1 )
( 1 0 0 )
( 0 1 0 )
,( 0 0 1 )
( 0 1 0 )
( 1 0 0 )
]

• (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,

λ> nTorres 3
6
λ> length (show (nTorres (10^4)))
35660

Leer más…

Las expresiones aritméticas construidas con una variables, los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Exp definido por

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
           deriving Show

Por ejemplo, la expresión 3+5x^2 se puede representar por

exp1 :: Exp
exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

Por su parte, los polinomios se pueden representar por la lista de sus coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede representar por [3,0,5].

Definir las funciones

valorE :: Exp -> Int -> Int
expresion :: [Int] -> Exp
valorP :: [Int] -> Int -> Int

tales que

• (valorE e n) es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,

λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2
23

• (expresion p) es una expresión aritmética equivalente al polinomio p. Por ejemplo,

λ> expresion [3,0,5]
Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))

• (valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,

λ> valorP [3,0,5] 2
23

Comprobar con QuickCheck que, para todo polinomio p y todo entero n,

valorP p n == valorE (expresion p) n

Leer más…

El tipo de los árboles binarios se define por

data Arbol = H Int
           | N Int Arbol Arbol

Por ejemplo, el árbol

     5
    / \
   /   \
  3     7
 / \   / \
1   4 6   9

se define por

ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

Un árbol ordenado es un árbol binario tal que para cada nodo, los elementos de su subárbol izquierdo son menores y los de su subárbol derecho son mayores. El árbol anterior es un árbol ordenado.

Los ancestros de un nodo x son los nodos y tales que x está en alguna de las ramas de x. Por ejemplo, en el árbol anterior los ancestros de 9 son 5 y 7.

El ancestro común más bajo de dos elementos x e y de un árbol a es el ancestro de x e y de menor profundidad. Por ejemplo, en el árbol anterior el ancestro común más bajo de 6 y 9 es 7.

Definir la función

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

tal que (ancestroComunMasBajo a x y) es el ancestro de menor profundidad de los nodos x e y en el árbol ordenado a, donde x e y son dos elementos distintos del árbol a. Por ejemplo,

ancestroComunMasBajo ejArbol 4 1  ==  3
ancestroComunMasBajo ejArbol 1 6  ==  5
ancestroComunMasBajo ejArbol 6 9  ==  7

Leer más…

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Leer más…

Los polinomios pueden representarse mediante listas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -7. Llamando C(p) al número de cambios de signo en la lista de coeficientes del polinomio p(x), tendríamos entonces que en este caso C(p)=3.

La regla de los signos de Descartes dice que el número de raíces reales positivas de una ecuación polinómica con coeficientes reales igualada a cero es, como mucho, igual al número de cambios de signo que se produzcan entre sus coeficientes (obviando los ceros). Por ejemplo, en el caso anterior la ecuación tendría como mucho tres soluciones reales positivas, ya que C(p)=3.

Además, si la cota C(p) no se alcanza, entonces el número de raíces positivas de la ecuación difiere de ella un múltiplo de dos. En el ejemplo anterior esto significa que la ecuación puede tener tres raíces positivas o tener solamente una, pero no podría ocurrir que tuviera dos o que no tuviera ninguna.

Definir las funciones

cambios :: [Int] -> [(Int,Int)]
nRaicesPositivas :: [Int] -> [Int]

tales que

• (cambios xs) es la lista de los pares de elementos de xs con signos distintos, obviando los ceros. Por ejemplo,

cambios [1,3,0,-5,1,-7]  ==  [(3,-5),(-5,1),(1,-7)]

• (nRaicesPositivas p) es la lista de los posibles números de raíces positivas del polinomio p (representado mediante una lista) según la regla de los signos de Descartes. Por ejemplo,

nRaicesPositivas [1,3,0,-5,1,-7]  ==  [3,1]

que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 raíz positiva.

Leer más…

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

taxicab  :: [Integer]
taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

take 5 taxicab   ==  [1729,4104,13832,20683,32832]
take 2 taxicab2  ==  [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Leer más…

Los números naturales pueden definirse de forma alternativa empleando los números de Church. Podemos representar un número natural n como una función que toma una función f como parámetro y devuelve n veces f.

Definimos por tanto los números naturales como

Type Nat = forall a. (a -> a) -> a -> a

De esta forma, para representar el número uno, repetir una vez una función es lo mismo que solamente aplicarla.

uno :: Nat
uno f x = f x

De manera similar, dos debe aplicar f dos veces a su argumento.

dos :: Nat
dos f x = f (f x)

Definir cero equivale por tanto a devolver el argumento sin modificar.

cero :: Nat
cero f x = x

Definir las funciones

cero    :: Nat
uno     :: Nat
dos     :: Nat
tres    :: Nat
nat2Int :: Nat -> Int
succ    :: Nat -> Nat
suma    :: Nat -> Nat -> Nat
mult    :: Nat -> Nat -> Nat
exp     :: Nat -> Nat -> Nat

tales que

• cero, uno y dos son definiciones alternativas a las ya dadas y tres es el número natural 3 con esta representación.
• (nat2Int n) es el número entero correspondiente al número natuaral n. Por ejemplo,

nat2Int cero == 0
nat2Int uno  == 1
nat2Int dos  == 2
nat2Int tres == 3

• (succ n) es el sucesor del número n. Por ejemplo,

nat2Int (succ dos)   ==  3
nat2Int (succ tres)  ==  4

• (suma n m) es la suma de n y m. Por ejemplo,

nat2Int (suma dos tres)         ==  5
nat2Int (suma dos (succ tres))  ==  6

• (mult n m) es el producto de n y m. Por ejemplo,

nat2Int (mult dos tres)         ==  6
nat2Int (mult dos (succ tres))  ==  8

• (exp n m) es la potencia m-ésima de n. Por ejemplo,

nat2Int (exp dos tres)   ==  8
nat2Int (exp tres dos)   ==  9
nat2Int (exp tres cero)  ==  1
nat2Int (exp cero tres)  ==  0

Comprobar con QuickCheck las siguientes propiedades. Para ello importar la librería Test.QuickCheck.Function y seguir el siguiente ejemplo:

prop_Succ1 :: Fun Int Int -> Int -> Bool
prop_Succ1 (Fun _ f) x = succ cero f x == uno f x

succ uno                   = dos
succ dos                   = tres
suma cero uno              = uno
suma dos tres              = suma tres dos
suma (suma dos dos) tres   = suma uno (suma tres tres)
mult uno uno               = uno
mult cero (suma tres tres) = cero
mult dos tres              = suma tres tres
exp dos dos                = suma dos dos
exp tres dos               = suma (mult dos (mult dos dos)) uno
exp tres cero              = uno

Nota 1: Añadir al inicio del archivo del ejercicio los pragmas

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TemplateHaskell #-}

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Leer más…

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]

Leer más…

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 3
5 = 1 + 3 + 1
5 = 3 + 1 + 1
5 = 1 + 4
5 = 4 + 1

Definir las funciones

descomposiciones  :: Integer -> [[Integer]]
nDescomposiciones :: Integer -> Integer

tales que

• (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

λ> descomposiciones1 4
[[4],[3,1],[1,3],[1,1,1,1]]
λ> descomposiciones1 5
[[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]]
λ> descomposiciones1 6
[[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1],
[1,1,1,3],[1,1,1,1,1,1]]

• (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

nDescomposiciones 5                       ==  6
nDescomposiciones 10                      ==  64
nDescomposiciones 20                      ==  7921
nDescomposiciones 30                      ==  974169
length (show (nDescomposiciones (10^5)))  ==  20899

Nota: Se puede usar programación dinámica.

Leer más…

En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).

Definir las funciones

solucionesTresJarras :: Problema -> [[Estado]]
tresJarras :: Problema -> Maybe [Estado]

tales que

• (solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,

λ> mapM_ print (solucionesTresJarras (4,2,1))
[(4,0,0),(2,2,0)]
[(4,0,0),(3,0,1),(1,2,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]
λ> mapM_ print (solucionesTresJarras (8,6,2))
[(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
λ> length (solucionesTresJarras (8,5,3))
16
λ> head (solucionesTresJarras (8,5,3))
[(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> length (solucionesTresJarras (8,6,5))
0

• (tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> tresJarras (4,2,1)
Just [(4,0,0),(2,2,0)]
λ> tresJarras (8,6,2)
Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
λ> tresJarras (8,5,3)
Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> tresJarras (8,6,5)
Nothing

Leer más…

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

1 ----- 2
| \     |
|  3    |
| /     |
4 ----- 5

se puede representar por la matriz de adyacencia

|0 1 1 1 0|
|1 0 0 0 1|
|1 0 0 1 0|
|1 0 1 0 1|
|0 1 0 1 0|

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

matrizAlista :: Matrix Int -> [(Int,[Int])]
listaAmatriz :: [(Int,[Int])] -> Matrix Int

tales que

• (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por

ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
[1,0,0,0,1],
[1,0,0,1,0],
[1,0,1,0,1],
[0,1,0,1,0]]

se tiene que

λ> matrizAlista ejMatriz
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

• (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,

λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
( 0 1 1 1 0 )
( 1 0 0 0 1 )
( 1 0 0 1 0 )
( 1 0 1 0 1 )
( 0 1 0 1 0 )
λ> matrizAlista it
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

Leer más…

La sucesión de polinomios de Fibonacci se define por

p(0) = 0
p(1) = 1
p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

p(2) = x
p(3) = x^2 + 1
p(4) = x^3 + 2*x
p(5) = x^4 + 3*x^2 + 1

Definir la lista

sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

λ> take 7 sucPolFib
[0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
λ> sum (map grado (take 3000 sucPolFib2))
4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, ...

Nota. Limitar la búsqueda a ejemplos pequeños usando

quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Leer más…

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

• (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

• (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601