Ir al contenido principal

El problema 3SUM

Misceláneas

El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se puede elegir los elementos 7, -9 y 2 que suman 0.

Definir las funciones

sols3Sum :: [Int] -> [[Int]]
pb3Sum :: [Int] -> Bool

tales que

  • (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,
sols3Sum [8,10,-10,-7,2,-3]   ==  [[-10,2,8],[-7,-3,10]]
sols3Sum [-2..3]              ==  [[-2,-1,3],[-2,0,2],[-1,0,1]]
sols3Sum [1,-2]               ==  []
sols3Sum [-2,1]               ==  []
sols3Sum [1,-2,1]             ==  [[-2,1,1]]
length (sols3Sum [-100..100]) ==  5000
  • (pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,
pb3Sum [8,10,-10,-7,2,-3]  ==  True
pb3Sum [1,-2]              ==  False
pb3Sum [-2,1]              ==  False
pb3Sum [1,-2,1]            ==  True
pb3Sum [1..400]            ==  False

Leer más…

De hexadecimal a decimal

Misceláneas

El sistema hexadecimal es el sistema de numeración posicional que tiene como base el 16.

En principio, dado que el sistema usual de numeración es de base decimal y, por ello, sólo se dispone de diez dígitos, se adoptó la convención de usar las seis primeras letras del alfabeto latino para suplir los dígitos que nos faltan. El conjunto de símbolos es el siguiente: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. En ocasiones se emplean letras minúsculas en lugar de mayúsculas. Se debe notar que A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15.

Como en cualquier sistema de numeración posicional, el valor numérico de cada dígito es alterado dependiendo de su posición en la cadena de dígitos, quedando multiplicado por una cierta potencia de la base del sistema, que en este caso es 16. Por ejemplo, el valor decimal del número hexadecimal 3E0A es

  3×16^3 + E×16^2 + 0×16^1 + A×16^0
= 3×4096 + 14×256 + 0×16   + 10×1
= 15882

Definir la función

hexAdec :: String -> Int

tal que (hexAdec cs) es el valor decimal del número hexadecimal representado meiante la cadena cs. Por ejemplo,

hexAdec "3E0A"   == 15882
hexAdec "ABCDEF" == 11259375
hexAdec "FEDCBA" == 16702650

Leer más…

Ordenación según una cadena

Misceláneas

Dada una lista xs y una cadena cs de la misma longitud, la ordenación de xs según cs consiste en emparejar los elementos de cs con los de xs (de forma que al menor elemento de cs le corresponde el menor de xs, al segundo de cs el segundo de xs, etc.) y ordenar los elementos de xs en el mismo orden que sus correspondientes elementos de cs. Por ejemplo, si xs es [6,4,2] y cs es "CAB" entonces a 'A' le corresponde el 2, a 'B' el 4 y a 'C' el 6; luego la ordenación es [6,2,4].

Definir la función

ordenacion :: Ord a => [a] -> String -> [a]

tal que (ordenacion xs ys) es la ordenación de la lista xs según la cadena cs. Por ejemplo,

ordenacion [6,4,2] "CAB"     ==  [6,2,4]
ordenacion [1,5,3] "ABC"     ==  [1,3,5]
ordenacion [1,5,3,7] "ABEC"  ==  [1,3,7,5]

Leer más…

Factorial módulo

Misceláneas

Definir la función

factorialMod :: Integer -> Integer -> Integer

tal que (factorialMod n x) es el factorial de x módulo n. Por ejemplo,

factorialMod (7+10^9) 100       ==  437918130
factorialMod (7+10^9) (5*10^6)  ==  974067448

Leer más…

Recorrido por niveles de árboles binarios

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

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

se pueden representar por

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

Definir la función

recorrido :: Arbol t -> [t]

tal que (recorrido a) es el recorrido del árbol a por niveles desde la raíz a las hojas y de izquierda a derecha. Por ejemplo,

λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
[1,2,3,4,5,6,7,8,9]
λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9))))
[1,3,2,6,7,4,5,8,9]
λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5)))
[1,3,2,6,7,4,5]
λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))
[1,2,3,4,5,6,7]
λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3))
[1,2,3,4,5]
λ> recorrido (N 1 (H 4) (H 3))
[1,4,3]
λ> recorrido (H 3)
[3]

Leer más…

Sucesión de raíces enteras de los números primos

Misceláneas

Definir las siguientes funciones

raicesEnterasPrimos :: [Integer]
posiciones :: Integer -> (Int,Int)
frecuencia :: Integer -> Int
grafica_raicesEnterasPrimos :: Int -> IO ()
grafica_posicionesIniciales :: Integer -> IO ()
grafica_frecuencias :: Integer -> IO ()

tales que

  • raicesEnterasPrimos es la sucesión de las raíces enteras (por defecto) de los números primos. Por ejemplo,
λ> take 20 raicesEnterasPrimos
[1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8]
λ> raicesEnterasPrimos !! 2500000
6415
  • (posiciones x) es el par formado por la menor y la mayor posición de x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
posiciones 2     ==  (2,3)
posiciones 4     ==  (6,8)
posiciones 2017  ==  (287671,287931)
posiciones 2018  ==  (287932,288208)
  • (frecuencia x) es el número de veces que aparece x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
frecuencia 2     ==  2
frecuencia 4     ==  3
frecuencia 2017  ==  261
frecuencia 2018  ==  277
  • (grafica_raicesEnterasPrimos n) dibuja la gráfica de los n primeros términos de la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_raicesEnterasPrimos 200) dibuja

Sucesión de raíces enteras de los números primos

  • (grafica_posicionesIniciales n) dibuja la gráfica de las menores posiciones de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_posicionesIniciales 200) dibuja

Sucesión de raíces enteras de los números primos

  • (grafica_frecuencia n) dibuja la gráfica de las frecuencia de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_frecuencia 200) dibuja

Sucesión de raíces enteras de los números primos

Leer más…

Posiciones de las mayúsculas

Misceláneas

Definir la función

posicionesMayusculas :: String -> [Int]

tal que (posicionesMayusculas cs) es la lista de las posiciones de las mayúsculas de la cadena cs. Por ejemplo,

posicionesMayusculas "SeViLLa"  == [0,2,4,5]
posicionesMayusculas "aAbB"     == [1,3]
posicionesMayusculas "ABCDEF"   == [0,1,2,3,4,5]
posicionesMayusculas "4ysdf4"   == []
posicionesMayusculas ""         == []

Leer más…

Rotaciones divisibles por 8

Misceláneas

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816 de las que 3 son divisibles por 8 (928160, 160928 y 92816).

Definir la función

nRotacionesDivisiblesPor8 :: Integer -> Int

tal que (nRotacionesDivisiblesPor8 x) es el número de rotaciones de x divisibles por 8. Por ejemplo,

nRotacionesDivisiblesPor8 928160       ==  3
nRotacionesDivisiblesPor8 43262488612  ==  4
nRotacionesDivisiblesPor8 (read (take (10^4) (cycle "248")))  ==  6666

Leer más…

Sumable sin vecinos

Misceláneas

En la lista [3,2,5,7,4] el número 12 se puede escribir como una suma de elementos de la lista sin incluir sus vecinos (ya que es la suma de 3, 5 y 4); en cambio, 14 no lo es (porque es la suma de 3, 7 y 4, pero 7 y 4 son vecinos).

Definir la función

esSumableSinVecinos :: [Int] -> Int -> Bool

tal que (esSumableSinVecinos xs n) se verifica si n se puede escribir como una suma de elementos de xs que no incluye a ninguno de sus vecinos. Por ejemplo,

esSumableSinVecinos [3,2,5,7,4] 12  ==  True
esSumableSinVecinos [3,2,5,7,4] 9   ==  True
esSumableSinVecinos [3,2,5,7,4] 6   ==  True
esSumableSinVecinos [3,2,5,7,4] 14  ==  False
esSumableSinVecinos [3,2,5,7,4] 1   ==  False

Leer más…

Suma de las hojas de mínimo nivel

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

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

se pueden representar por

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

En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.

Definir la función

suma :: Num t => Arbol t -> t

tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,

suma ejArbol                                    ==  17
suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))  ==  22
suma (N 1 (H 2) (N 3 (H 6) (H 7)))              ==  2
suma (N 1 (H 2) (H 3))                          ==  5
suma (H 2)                                      ==  2

Leer más…

Vecino en lista circular

Misceláneas

En la lista circular [3,2,5,7,9]

  • el vecino izquierdo de 5 es 2 y su vecino derecho es 7,
  • el vecino izquierdo de 9 es 7 y su vecino derecho es 3,
  • el vecino izquierdo de 3 es 9 y su vecino derecho es 2,
  • el elemento 4 no tiene vecinos (porque no está en la lista).

Para indicar las direcciones se define el tipo de datos

data Direccion = I | D deriving Eq

Definir la función

vecino :: Eq a => Direccion -> [a] -> a -> Maybe a

tal que (vecino d xs x) es el vecino de x en la lista de elementos distintos xs según la dirección d. Por ejemplo,

vecino I [3,2,5,7,9] 5  ==  Just 2
vecino D [3,2,5,7,9] 5  ==  Just 7
vecino I [3,2,5,7,9] 9  ==  Just 7
vecino D [3,2,5,7,9] 9  ==  Just 3
vecino I [3,2,5,7,9] 3  ==  Just 9
vecino D [3,2,5,7,9] 3  ==  Just 2
vecino I [3,2,5,7,9] 4  ==  Nothing
vecino D [3,2,5,7,9] 4  ==  Nothing

Leer más…

Cadenas opuestas

Misceláneas

La opuesta de una cadena de letras es la cadena obtenida cambiando las minúsculas por mayúsculas y las minúsculas por mayúsculas. Por ejemplo, la opuesta de "SeViLLa" es "sEvIllA".

Definir la función

esOpuesta :: String -> String -> Bool

tal que (esOpuesta s1 s2) se verifica si las cadenas de letras s1 y s2 son opuestas. Por ejemplo,

esOpuesta "ab" "AB"      `== True
esOpuesta "aB" "Ab"      `== True
esOpuesta "aBcd" "AbCD"  `== True
esOpuesta "aBcde" "AbCD" `== False
esOpuesta "AB" "Ab"      `== False
esOpuesta "" ""          `== True

Leer más…

Menor con suma de dígitos dada

Misceláneas

Definir la función

minSumDig :: Integer -> Integer

tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,

minSumDig 1   ==  1
minSumDig 12  ==  39
minSumDig 21  ==  399
(length . show . minSumDig) (3*10^5)  ==  33334
(length . show . minSumDig) (3*10^6)  ==  333334
(length . show . minSumDig) (3*10^7)  ==  3333334
(length . show . minSumDig) (4*10^7)  ==  4444445
(length . show . minSumDig) (5*10^7)  ==  5555556

Leer más…

Aplicaciones biyectivas

Misceláneas

Definir las funciones

biyectivas  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

  • (biyectivas xs ys) es el conjunto de las aplicaciones biyectivas del conjunto xs en el conjunto ys. Por ejemplo,
λ> biyectivas [1,3] [2,4]
[[(1,2),(3,4)],[(1,4),(3,2)]]
λ> biyectivas [1,3,5] [2,4,6]
[[(1,2),(3,4),(5,6)],[(1,4),(3,2),(5,6)],[(1,6),(3,4),(5,2)],
 [(1,4),(3,6),(5,2)],[(1,6),(3,2),(5,4)],[(1,2),(3,6),(5,4)]]
λ> biyectivas [1,3] [2,4,6]
[]
  • (nBiyectivas xs ys) es el número de aplicaciones biyectivas del conjunto xs en el conjunto ys. Por ejemplo,
nBiyectivas [1,3] [2,4]      ==  2
nBiyectivas [1,3,5] [2,4,6]  ==  6
λ> nBiyectivas [1,3] [2,4,6] ==  0
length (show (nBiyectivas2 [1..2*10^4] [1..2*10^4]))  ==  77338

Nota: En este ejercicio los conjuntos se representan mediante listas ordenadas de elementos distintos.

Leer más…

Bosque de recorridos del autobús

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []]
ejArbol2 = Node 8 [Node 4 []]

También se pueden definir bosques. Por ejemplo,

ejBosque = [ejArbol1, ejArbol2]

Se pueden dibujar los bosques con la función drawForest. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) ejBosque))
3
|
+- 5
|  |
|  `- 9
|
`- 7

8
|
`- 4

Usando la notación de los ejercicios anteriores para las subidas y bajadas en el autobús, definir la función

bosqueRecorridos :: Int -> Int -> Forest (Int,Int)

tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autobús de capacidad n y usando m paradas. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))
(0,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (2,0)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   `- (0,2)

(1,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
`- (1,1)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   +- (1,0)
   |
   `- (1,1)

(2,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (0,2)
   |
   +- (0,0)
   |
   +- (1,0)
   |
   `- (2,0)

en donde la última rama representa el recorrido [(2,0),(0,2),(2,0)].

Leer más…

Reconocimiento de recorridos correctos

Misceláneas

Se usará la misma representación del ejercicio anterior para las subidas y bajadas en el autobús; es decir, una lista de pares donde los primeros elementos es el número de viajeros que suben y los segundo es el de los que bajan.

Un recorrido es correcto si en cada bajada tanto el número de viajeros que suben como los que bajan son positivos, el número de viajeros en el autobús no puede ser mayor que su capacidad y el número de viajeros que bajan no puede ser mayor que el número de viajeros en el autobús. Se supone que en la primera parada el autobús no tiene viajeros.

Definir la función

recorridoCorrecto :: Int -> [(Int,Int)] -> Bool

tal que (recorridoCorrecto n ps) se verifica si ps es un recorrido correcto en un autobús cuya capacidad es n. Por ejemplo,

recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  True
recorridoCorrecto 15 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  False
recorridoCorrecto 15 [(3,2),(9,1),(4,10),(12,2),(6,1)]  ==  False
recorridoCorrecto 15 [(3,0),(2,7),(4,10),(12,2),(6,1)]  ==  False

el segundo ejemplo es incorrecto porque en la última para se supera la capacidad del autobús; el tercero, porque en la primera para no hay viajeros en el autobús que se puedan bajar y el cuarto, porque en la 2ª parada el autobús tiene 3 viajeros por lo que es imposible que se bajen 7.

Leer más…

Número de viajeros en el autobús

Misceláneas

Un autobús inicia su recorrido con 0 viajeros. El número de viajeros que se suben y bajan en cada parada se representa por un par (x,y) donde x es el número de las que suben e y el de las que bajan. Un recorrido del autobús se representa por una lista de pares representando los números de viajeros que suben o bajan en cada parada.

Definir la función

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

tal que (nViajerosEnBus ps) es el número de viajeros en el autobús tras el recorrido ps. Por ejemplo,

nViajerosEnBus []                                        ==  0
nViajerosEnBus [(10,0),(3,5),(5,8)]                      ==  5
nViajerosEnBus [(3,0),(9,1),(4,10),(12,2),(6,1),(7,10)]  ==  17
nViajerosEnBus [(3,0),(9,1),(4,8),(12,2),(6,1),(7,8)]    ==  21

Leer más…

Ordenación valle

Misceláneas

La ordenación valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutación de la primera y cumple las siguientes condiciones

  • se compone de una parte decreciente ([79,35,25]), un elemento mínimo (12) y una parte creciente ([19,35,54]);
  • las dos partes tienen el mismo número de elementos;
  • cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 ≥ 54, 35 ≥ 35 y 25 ≥ 19;
  • además, la diferencia entre dichos elementos es la menor posible.

En el caso, de que la longitud de la lista sea par, la división tiene sólo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].

Definir la función

valle :: [Int] -> [Int]

tal que (valle xs) es la ordenación valle de la lista xs. Por ejemplo,

valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]
valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]
valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]
valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]
valle [14,14,14,14,14]             ==  [14,14,14,14,14]
valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]

En el último ejemplo se muestra cómo la última condición descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] también sea solución ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la solución; por ejemplo, 17 - 7 > 17 - 17.

Leer más…

Caminos minimales en un arbol numérico

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

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

Definir las siguientes funciones

mayoresDivisores :: Int -> [Int]
arbol            :: Int -> Tree Int
caminos          :: Int -> [[Int]]
caminosMinimales :: Int -> [[Int]]

tales que

  • (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,
mayoresDivisores 24  ==  [12,8,6]
mayoresDivisores 16  ==  [8,4]
mayoresDivisores 10  ==  [5]
mayoresDivisores 17  ==  []
  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> putStrLn (drawTree (fmap show (arbol 6)))
6
|
+- 5
|  |
|  `- 4
|     |
|     +- 3
|     |  |
|     |  `- 2
|     |     |
|     |     `- 1
|     |
|     `- 2
|        |
|        `- 1
|
`- 3
|
`- 2
|
`- 1
  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> caminos 6
[[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> caminosMinimales 6
[[6,3,2,1]]
λ> caminosMinimales 17
[[17,16,4,2,1]]
λ> caminosMinimales 50
[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Leer más…

Máximo de las rotaciones restringidas

Misceláneas

Rotar un número a la iquierda significa pasar su primer dígito al final. Por ejemplo, rotando a la izquierda el 56789 se obtiene 67895.

Las rotaciones restringidas del número 56789 se obtienen como se indica a continución:

  • Se inicia con el propio número: 56789
  • El anterior se rota a la izquierda y se obtiene el 67895.
  • Del anterior se fija el primer dígito y se rota a la iquierda los otros. Se obtiene 68957.
  • Del anterior se fijan los 2 primeros dígito y se rota a la iquierda los otros. Se obtiene 68579.
  • Del anterior se fijan los 3 primeros dígito y se rota a la iquierda los otros. Se obtiene 68597.

El proceso ha terminado ya que conservando los cuatro primeros queda sólo un dígito que al girar es él mismo. Por tanto, la sucesión de las rotaciones restringidas de 56789 es

56789 -> 67895 -> 68957 -> 68579 -> 68597

y su mayor elemento es 68957.

Definir la función

maxRotaciones :: Integer -> Integer

tal que (maxRotaciones n) es el máximo de las rotaciones restringidas del número n. Por ejemplo,

maxRotaciones 56789       ==  68957
maxRotaciones 1347902468  ==  3790246814
maxRotaciones 6           ==  6
maxRotaciones 2017        ==  2017

Leer más…

Aplicación de lista de funciones a lista de elementos

Misceláneas

Definir la función

aplicaLista :: [a -> b] -> [a] -> [b]

tal que (aplicaLista fs xs) es la lista de los valores de las funciones de fs aplicadas a los correspondientes elementos de xs. Por ejemplo,

aplicaLista [(+2),(`div` 3),(*5)] [4,6,2]    ==  [6,2,10]
aplicaLista [(+2),(`div` 3),(*5)] [4,6,2,8]  ==  [6,2,10]
aplicaLista [(>2),(==3),(<5)]     [4,6,2,9]  ==  [True,False,True]

Leer más…

Mayúsculas y minúsculas alternadas

Misceláneas

Definir la función

alternadas :: String -> (String,String)

tal que (alternadas cs) es el par de cadenas (xs,ys) donde xs es la cadena obtenida escribiendo alternativamente en mayuscula o minúscula las letras de la palabra cs (que se supone que es una cadena de letras minúsculas) e ys se obtiene análogamente pero empezando en minúscula. Por ejemplo,

λ> alternadas "salamandra"
("SaLaMaNdRa","sAlAmAnDrA")
λ> alternadas "solosequenosenada"
("SoLoSeQuEnOsEnAdA","sOlOsEqUeNoSeNaDa")
λ> alternadas (replicate 30 'a')
("AaAaAaAaAaAaAaAaAaAaAaAaAaAaAa","aAaAaAaAaAaAaAaAaAaAaAaAaAaAaA")

Leer más…

Conjunto de funciones entre dos conjuntos

Misceláneas

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

  • [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
  • [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
  • [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir las funciones

funciones  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

  • (funciones xs ys) es el conjunto de las funciones del conjunto xs en el conjunto ys. Por ejemplo,
λ> funciones [1] [2]
[[(1,2)]]
λ> funciones [1] [2,4]
[[(1,2)],[(1,4)]]
λ> funciones [1,3] [2]
[[(1,2),(3,2)]]
λ> funciones [1,3] [2,4]
[[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]
λ> funciones [1,3] [2,4,6]
[[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],
[(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],
[(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]
λ> funciones [1,3,5] [2,4]
[[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],
[(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],
[(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]
λ> funciones [] []
[[]]
λ> funciones [] [2]
[[]]
λ> funciones [1] []
[]
  • (nFunciones xs ys) es el número de funciones del conjunto xs en el conjunto ys. Por ejemplo,
nFunciones [1,3] [2,4,6]  ==  9
nFunciones [1,3,5] [2,4]  ==  8
length (show (nFunciones2 [1..10^6] [1..10^3]))  ==  3000001

Leer más…

Expresiones equilibradas

Misceláneas

Una cadena de paréntesis abiertos y cerrados está equilibrada si a cada paréntesis abierto le corresponde uno cerrado y los restantes están equilibrados. Por ejemplo, "(()())" está equilibrada, pero "())(()" no lo está.

Definir la función

equilibrada :: String -> Bool

tal que (equilibrada cs) se verifica si la cadena cs está equilibrada. Por ejemplo,

equilibrada "(()())"          ==  True
equilibrada "())(()"          ==  False
equilibrada "()"              ==  True
equilibrada ")(()))"          ==  False
equilibrada "("               ==  False
equilibrada "(())((()())())"  == True

Leer más…

Reconocimiento de relaciones funcionales entre dos conjuntos

Misceláneas

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Una relación R entre A y B es funcional si cada elemento de A está relacionado mediante R como máximo con un elemento de B. Por ejemplo, [(2,4),(1,5),(3,4)] es funcional, pero [(3,4),(1,4),(1,2),(3,4)] no lo es.

Definir la función

esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool

tal que (esFuncional r) r se verifica si la relación r es funcional. Por ejemplo,

esFuncional [(2,4),(1,5),(3,4)]        ==  True
esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False

Leer más…

Menor x tal que los x múltiplos de n contienen todos los dígitos

Misceláneas

Definir la función

menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, ... y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

92                                    contiene  [2,9]
92 y 92×2                             contienen [1,2,4,8,9]
92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

menorX 92          ==  6
menorX 2967        ==  3
menorX 266         ==  4
menorX 18          ==  5
menorX 2           ==  45
menorX 125         ==  72
menorX 1234567890  ==  1
maximum [menorX n | n <- [1..3000]]  ==  72
minimum [menorX n | n <- [1..3000]]  ==  3

Leer más…

Conjunto de relaciones binarias entre dos conjuntos

Misceláneas

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Definir las funciones

relaciones  :: [a] -> [b] -> [[(a,b)]]
nRelaciones :: [a] -> [b] -> Integer

tales que

  • (relaciones xs ys) es el conjunto de las relaciones del conjunto xs en el conjunto ys. Por ejemplo,
λ> relaciones [1] [2]
[[],[(1,2)]]
λ> relaciones [1] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)]]
λ> relaciones [1,3] [2]
[[],[(1,2)],[(3,2)],[(1,2),(3,2)]]
λ> relaciones [1,3] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],
 [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],
 [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],
 [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],
 [(1,2),(1,4),(3,2),(3,4)]]
λ> relaciones [] []
[[]]
λ> relaciones [] [2]
[[]]
λ> relaciones [1] []
[[]]
  • (nRelaciones xs ys) es el número de relaciones del conjunto xs en el conjunto ys. Por ejemplo,
nRelaciones [1,2] [4,5]    ==  16
nRelaciones [1,2] [4,5,6]  ==  64
nRelaciones [0..9] [0..9]  ==  1267650600228229401496703205376

Leer más…

Sumas de dos cuadrados

Misceláneas

Definir la función

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

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

sumasDe2Cuadrados 25                ==  [(5,0),(4,3)]
sumasDe2Cuadrados 32                ==  [(4,4)]
sumasDe2Cuadrados 55                ==  []
sumasDe2Cuadrados 850               ==  [(29,3),(27,11),(25,15)]
length (sumasDe2Cuadrados (10^12))  ==  7

Leer más…

Mayor producto de las ramas de un árbol

Misceláneas

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…

Sucesión contadora

Misceláneas

Definir las siguientes funciones

numeroContado           :: Integer -> Integer
contadora               :: Integer -> [Integer]
lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

tales que

  • (numeroContado n) es el número obtenido al contar las repeticiones de cada una de las cifras de n. Por ejemplo,
numeroContado 1                 == 11
numeroContado 114213            == 31121314
numeroContado 1111111111111111  == 161
  • (contadora n) es la sucesión cuyo primer elemento es n y los restantes se obtienen contando el número anterior de la sucesión. Por ejemplo,
λ> take 14 (contadora 1)
[1,11,21,1112,3112,211213,312213,212223,114213,31121314,41122314,
31221324,21322314,21322314]
λ> take 14 (contadora 5)
[5,15,1115,3115,211315,31121315,41122315,3122131415,4122231415,
3132132415,3122331415,3122331415,3122331415,3122331415]
  • (lugarPuntoFijoContadora n k) es el menor i <= k tal que son iguales los elementos en las posiciones i e i+1 de la sucesión contadora que cominza con n. Por ejemplo,
λ> lugarPuntoFijoContadora 1 100
Just 12
λ> contadora 1 !! 11
31221324
λ> contadora 1 !! 12
21322314
λ> contadora 1 !! 13
21322314
λ> lugarPuntoFijoContadora 1 10
Nothing
λ> lugarPuntoFijoContadora 5 20
Just 10
λ> lugarPuntoFijoContadora 40 200
Nothing

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

Leer más…

Punto de inflexión

Misceláneas

Definir la función

inflexion :: Ord a => [a] -> Maybe a

tal que (inflexion xs) es el primer elemento de la lista en donde se cambia de creciente a decreciente o de decreciente a creciente y Nothing si no se cambia. Por ejemplo,

inflexion [2,2,3,5,4,6]    ==  Just 4
inflexion [9,8,6,7,10,10]  ==  Just 7
inflexion [2,2,3,5]        ==  Nothing
inflexion [5,3,2,2]        ==  Nothing

Leer más…

Número de divisores

Misceláneas

Definir la función

numeroDivisores :: Integer -> Integer

tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,

numeroDivisores 12  ==  6
numeroDivisores 25  ==  3
length (show (numeroDivisores (product (take 20000 primes)))) == 6021

Leer más…

Cadenas de sumas de factoriales de los dígitos

Misceláneas

Dado un número n se considera la sucesión cuyo primer término es n y los restantes se obtienen sumando los factoriales de los dígitos del anterior. Por ejemplo, la sucesión que empieza en 69 es

    69
363600  (porque 6! + 9! = 363600)
  1454  (porque 3! + 6! + 3! + 6! + 0! + 0! = 1454)
   169  (porque 1! + 4! + 5! + 4! = 169)
363601  (porque 1! + 6! + 9! = 363601)
  1454  (porque 3! + 6! + 3! + 6! + 0! + 1! = 1454)
......

La cadena correspondiente a un número n son los términos de la sucesión que empieza en n hasta la primera repetición de un elemento en la sucesión. Por ejemplo, la cadena de 69 es

[69,363600,1454,169,363601,1454]

Consta de una parte no periódica ([69,363600]) y de una periódica ([1454,169,363601]).

Definir las funciones

cadena  :: Integer -> [Integer]
periodo :: Integer -> [Integer]

tales que

  • (cadena n es la cadena correspondiente al número n. Por ejemplo,
cadena 69    ==  [69,363600,1454,169,363601,1454]
cadena 145   ==  [145,145]
cadena 78    ==  [78,45360,871,45361,871]
cadena 569   ==  [569,363720,5775,10320,11,2,2]
cadena 3888  ==  [3888,120966,364324,782,45362,872,45362]
maximum [length (cadena n) | n <- [1..5000]]  ==  61
length (cadena 1479)                          ==  61
  • (periodo n) es la parte periódica de la cadena de n. Por ejemplo,
periodo 69    ==  [169,363601,1454]
periodo 145   ==  [145]
periodo 78    ==  [45361,871]
periodo 569   ==  [2]
periodo 3888  ==  [872,45362]
maximum [length (periodo n) | n <- [1..5000]]  ==  3
length (periodo 1479)                          ==  3

Leer más…

Suma de divisores

Misceláneas

Definir las funciones

divisores     :: Integer -> [Integer]
sumaDivisores :: Integer -> Integer

tales que

  • (divisores x) es la lista de los divisores de x. Por ejemplo,
divisores 12  ==  [1,2,3,4,6,12]
divisores 25  ==  [1,5,25]
length (divisores (product [1..12]))  ==  792
length (divisores 131535436245601)    ==  32
  • (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
sumaDivisores 12  ==  28
sumaDivisores 25  ==  31
sumaDivisores (product [1..12])  ==  2217441408
sumaDivisores 131535436245601    ==  132534784471040

Leer más…

Números dígito potenciales

Misceláneas

Un número entero x es dígito potencial de orden n si x es la suma de los dígitos de x elevados a n. Por ejemplo,

  • 153 es un dígito potencial de orden 3 ya que 153 = 1^3+5^3+3^3
  • 4150 es un dígito potencial de orden 5 ya que 4150 = 4^5+1^5+5^5+0^5

Un número x es dígito auto potencial si es un dígito potencial de orden n, donde n es el número de dígitos de n. Por ejemplo, 153 es un número dígito auto potencial.

Definir las funciones

digitosPotencialesOrden :: Integer -> [Integer]
digitosAutoPotenciales  :: [Integer]

tales que

  • (digitosPotencialesOrden n) es la lista de los números dígito potenciales de orden n. Por ejemplo,
take 6 (digitosPotencialesOrden 3)  ==  [0,1,153,370,371,407]
take 5 (digitosPotencialesOrden 4)  ==  [0,1,1634,8208,9474]
take 8 (digitosPotencialesOrden 5)  ==  [0,1,4150,4151,54748,92727,93084,194979]
take 3 (digitosPotencialesOrden 6)  ==  [0,1,548834]
  • digitosAutoPotenciales es la lista de los números dígito auto potenciales. Por ejemplo,
λ> take 20 digitosAutoPotenciales
[0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

Leer más…

Mayor número equidigital

Misceláneas

Definir la función

mayorEquidigital :: Integer -> Integer

tal que (mayorEquidigital x) es el mayor número que se puede contruir con los dígitos de x. Por ejemplo,

mayorEquidigital 13112017  ==  73211110
mayorEquidigital2 (2^100)  ==  9987776666655443322222211000000

Leer más…

Números oblongos

Misceláneas

Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.

Definir las funciones

esOblongo :: Integer -> Bool
oblongos  :: [Integer]

tales que

  • (esOblongo n) se verifica si n es oblongo. Por ejemplo,
esOblongo 42               ==  True
esOblongo 40               ==  False
esOblongo 100000010000000  ==  True
  • oblongos es la suceción de los números oblongos. Por ejemplo,
take 15 oblongos   == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210]
oblongos !! 50     == 2550
oblongos !! (10^7) == 100000010000000

Leer más…

Pares definidos por su MCD y su MCM

Misceláneas

Definir las siguientes funciones

pares  :: Integer -> Integer -> [(Integer,Integer)]
nPares :: Integer -> Integer -> Integer

tales que

  • (pares a b) es la lista de los pares de números enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
pares 3 3  == [(3,3)]
pares 4 12 == [(4,12),(12,4)]
pares 2 12 == [(2,12),(4,6),(6,4),(12,2)]
pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]
pares 2 7  == []
pares 12 3 == []
length (pares 3 (product [3,5..91]))  ==  8388608
  • (nPares a b) es el número de pares de enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
nPares 3 3   ==  1
nPares 4 12  ==  2
nPares 2 12  ==  4
nPares 2 60  ==  8
nPares 2 7   ==  0
nPares 12 3  ==  0
nPares 3 (product [3..3*10^4]) `mod` (10^12)  ==  477999992832
length (show (nPares 3 (product [3..3*10^4])))  ==  977

Leer más…

Biparticiones de un número

Misceláneas

Definir la función

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

tal que (biparticiones n) es la lista de pares de números formados por las primeras cifras de n y las restantes. Por ejemplo,

biparticiones  2025  ==  [(202,5),(20,25),(2,25)]
biparticiones 10000  ==  [(1000,0),(100,0),(10,0),(1,0)]

Leer más…

Producto cartesiano de una familia de conjuntos

Misceláneas

Definir la función

producto :: [[a]] -> [[a]]

tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,

λ> producto [[1,3],[2,5]]
[[1,2],[1,5],[3,2],[3,5]]
λ> producto [[1,3],[2,5],[6,4]]
[[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
λ> producto [[1,3,5],[2,4]]
[[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]]
λ> producto []
[[]]

Comprobar con QuickCheck que para toda lista de listas de números enteros, xss, se verifica que el número de elementos de (producto xss) es igual al producto de los números de elementos de cada una de las listas de xss.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

quickCheckWith (stdArgs {maxSize=9}) prop_producto

Leer más…

Primos equidistantes

Misceláneas

Definir la función

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

tal que (primosEquidistantes k) es la lista de los pares de primos consecutivos 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)]
(primosEquidistantes 30) !! 14000  ==  (6557303,6557333)

Leer más…

Números completos

Misceláneas

Las descomposiciones de un número n son las parejas de números (x,y) tales que x >= y y la suma de las cuatro operaciones básicas (suma, producto, resta (el mayor menos el menor) y cociente (el mayor entre el menor)) es el número n. Por ejemplo, (8,2) es una descomposición de 36 ya que

(8 + 2) + (8 - 2) + (8 * 2) + (8 / 2) = 36

Un número es completo si tiene alguna descomposición como las anteriores. Por ejemplo, el 36 es completo pero el 21 no lo es.

Definir las siguientes funciones

descomposiciones :: Integer -> [(Integer,Integer)]
completos        :: [Integer]

tales que

  • (descomposiciones n) es la lista de las descomposiones de n. Por ejemplo,
descomposiciones 12   ==  [(3,1)]
descomposiciones 16   ==  [(3,3),(4,1)]
descomposiciones 36   ==  [(5,5),(8,2),(9,1)]
descomposiciones 288  ==  [(22,11),(40,5),(54,3),(64,2),(72,1)]
descomposiciones 21   ==  []
  • completos es la lista de los números completos. Por ejemplo,
take 15 completos  ==  [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44]
completos !! 100   ==  261

Leer más…

Números libres de cuadrados

Misceláneas

Un número entero positivo es libre de cuadrados si no es divisible 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

Otro ejemplo,

λ> filter (not . libreDeCuadrados) [1..50]
[4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50]

Leer más…

Ancestro común más bajo

Misceláneas

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…

La regla de los signos de Descartes

Misceláneas

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…

Valores de polinomios y de expresiones

Misceláneas

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…

Suma de los cuadrados de los divisores

Misceláneas

Dado un entero positivo n, consideremos la suma de los cuadrados de sus divisores. Por ejemplo,

f(10) = 1 + 4 + 25 + 100 = 130
f(42) = 1 + 4 +  9 +  36 + 49 + 196 + 441 + 1764 = 2500

Decimos que n es especial si f(n) es un cuadrado perfecto. En los ejemplos anteriores, 42 es especial y 10 no lo es.

Definir la función

especial:: Int -> Bool

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

especial 42  ==  True
especial 10  ==  False

Calcular todos los números especiales de tres cifras.

Nota: El ejercicio está basado en el Problema 211 del proyecto Euler.

Leer más…

Mayores sublistas crecientes

Misceláneas

Definir las funciones

mayoresCrecientes :: Ord a => [a] -> [[a]]
longitudMayorSublistaCreciente :: Ord a => [a] -> Int

tales que

  • (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,
λ> mayoresCrecientes [3,2,6,4,5,1]
[[3,4,5],[2,4,5]]
λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
[[10,22,33,50,60,80],[10,22,33,41,60,80]]
λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
[[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
λ> length (head (mayoresCrecientes (show (2^70))))
5
  • (longitudMayorSublistaCreciente xs) es el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,
λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
3
λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
6
λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
6
λ> longitudMayorSublistaCreciente [1..2000]
2000
λ> longitudMayorSublistaCreciente [2000,1999..1]
1

Leer más…

Sin ceros consecutivos

Misceláneas

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…

Extremos locales

Misceláneas

Un mínimo local de una lista es un elemento de la lista que es menor que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un mínimo local de [8,2,1,3,7,6,4,0,5] ya que es menor que 2 (su predecesor) y que 3 (su sucesor).

Análogamente se definen los máximos locales. Por ejemplo, 7 es un máximo local de [8,2,1,3,7,6,4,0,5] ya que es mayor que 7 (su predecesor) y que 6 (su sucesor).

Los extremos locales están formados por los mínimos y máximos locales. Por ejemplo, los extremos locales de [8,2,1,3,7,6,4,0,5] son el 1, el 7 y el 0.

Definir la función

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

tal que (extremos xs) es la lista de los extremos locales de la lista xs. Por ejemplo,

extremos [8,2,1,3,7,6,4,0,5]  ==  [1,7,0]
extremos [8,2,1,3,7,7,4,0,5]  ==  [1,7,0]

Leer más…

Subexpresiones aritméticas

Misceláneas

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…

Representaciones de grafos

Misceláneas

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…

Polinomios de Fibonacci

Misceláneas

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…

El pasatiempo de Ulises

Misceláneas

Ulises, en sus ratos libres, juega a un pasatiempo que consiste en, dada una serie de números naturales positivos en una cola, sacar un elemento y, si es distinto de 1, volver a meter el mayor de sus divisores propios. Si el número que saca es el 1, entonces lo deja fuera y no mete ningún otro. El pasatiempo continúa hasta que la cola queda vacía.

Por ejemplo, a partir de una cola con los números 10, 20 y 30, el pasatiempo se desarrollaría como sigue:

C [30,20,10]
C [20,10,15]
C [10,15,10]
C [15,10,5]
C [10,5,5]
C [5,5,5]
C [5,5,1]
C [5,1,1]
C [1,1,1]
C [1,1]
C [1]
C []

Definir la función

numeroPasos :: Cola Int -> Int

tal que (numeroPasos c) es el número de veces que Ulises saca algún número de la cola c al utilizarla en su pasatiempo. Por ejemplo,

numeroPasos (foldr inserta vacia [30])        ==  4
numeroPasos (foldr inserta vacia [20])        ==  4
numeroPasos (foldr inserta vacia [10])        ==  3
numeroPasos (foldr inserta vacia [10,20,30])  ==  11

Leer más…

Caminos reducidos

Misceláneas

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…

Descomposiciones de N como sumas de 1, 3 ó 4.

Misceláneas

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…

Caminos en un grafo

Misceláneas

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

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo).

Leer más…

Problema del dominó

Misceláneas

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir la función

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

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

λ> domino [(1,2),(2,3),(1,4)]
[[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]
λ> domino [(1,2),(1,1),(1,4)]
[[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]
λ> domino [(1,2),(3,4),(2,3)]
[[(1,2),(2,3),(3,4)]]
λ> domino [(1,2),(2,3),(5,4)]
[]
λ> domino [(x,y) | x <- [1..2], y <- [x..2]]
[[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]
λ> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])
[(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]
[(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]
[(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]
[(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]
[(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]
[(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]
[(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]
[(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]
[(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]
λ> length (domino [(x,y) | x <- [1..3], y <- [x..3]])
9
λ> length (domino [(x,y) | x <- [1..4], y <- [x..4]])
0
λ> length (domino [(x,y) | x <- [1..5], y <- [x..5]])
84480

Leer más…

El algoritmo de Damm

Misceláneas

El algoritmo de Damm se usa en la detección de errores en códigos numéricos. Es un procedimiento para obtener un dígito de control, usando la siguiente matriz, como describimos en los ejemplos

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

Ejemplo 1: cálculo del dígito de control de 572

  • se comienza con la fila 0 y columna 5 de la matriz -> 9
  • a continuación, la fila 9 y columna 7 de la matriz -> 7
  • a continuación, la fila 7 y columna 2 de la matriz -> 4

con lo que se llega al final del proceso. Entonces, el dígito de control de 572 es 4.

Ejemplo 2: cálculo del dígito de control de 57260

  • se comienza con la fila 0 y columna 5 de la matriz -> 9
  • a continuación, la fila 9 y columna 7 de la matriz -> 7
  • a continuación, la fila 9 y columna 2 de la matriz -> 4
  • a continuación, la fila 6 y columna 4 de la matriz -> 5
  • a continuación, la fila 5 y columna 0 de la matriz -> 3

con lo que se llega al final del proceso. Entonces, el dígito de control de 57260 es 3.

Representamos las matrices como tablas cuyos índices son pares de números naturales.

type Matriz a = Array (Int,Int) a

Definimos la matriz:

mDamm :: Matriz Int
mDamm = listArray ((0,0),(9,9)) [0,3,1,7,5,9,8,6,4,2,
                                 7,0,9,2,1,5,4,8,6,3,
                                 4,2,0,6,8,7,1,3,5,9,
                                 1,7,5,0,9,8,3,4,2,6,
                                 6,1,2,3,0,4,5,9,7,8,
                                 3,6,7,4,2,0,9,5,8,1,
                                 5,8,6,9,7,2,0,1,3,4,
                                 8,9,4,5,3,6,2,0,1,7,
                                 9,4,3,8,6,1,7,2,0,5,
                                 2,5,8,1,4,3,6,7,9,0]

Definir la función

digitoControl :: Int -> Int

tal que (digitoControl n) es el dígito de control de n. Por ejemplo:

digitoControl 572          == 4
digitoControl 57260        == 3
digitoControl 12345689012  == 6
digitoControl 5724         == 0
digitoControl 572603       == 0
digitoControl 123456890126 == 0

Comprobar con QuickCheck que si añadimos al final de un número n su dígito de control, el dígito de control del número que resulta siempre es 0.

Leer más…

El problema de la bicicleta de Turing

Misceláneas

Cuentan que Alan Turing tenía una bicicleta vieja, que tenía una cadena con un eslabón débil y además uno de los radios de la rueda estaba doblado. Cuando el radio doblado coincidía con el eslabón débil, entonces la cadena se rompía.

La bicicleta se identifica por los parámetros (i,d,n) donde

  • i es el número del eslabón que coincide con el radio doblado al empezar a andar,
  • d es el número de eslabones que se desplaza la cadena en cada vuelta de la rueda y
  • n es el número de eslabones de la cadena (el número n es el débil).

Si i = 2, d = 7 y n = 25, entonces la lista con el número de eslabón que toca el radio doblado en cada vuelta es

[2,9,16,23,5,12,19,1,8,15,22,4,11,18,0,7,14,21,3,10,17,24,6,...

Con lo que la cadena se rompe en la vuelta número 14.

Definir las funciones

eslabones :: Int -> Int -> Int -> [Int]
numeroVueltas :: Int -> Int -> Int -> Int

tales que

  • (eslabones i d n) es la lista con los números de eslabones que tocan el radio doblado en cada vuelta en una bicicleta de tipo (i,d,n). Por ejemplo,
take 10 (eslabones 2 7 25)  ==  [2,9,16,23,5,12,19,1,8,15]
  • (numeroVueltas i d n) es el número de vueltas que pasarán hasta que la cadena se rompa en una bicicleta de tipo (i,d,n). Por ejemplo,
numeroVueltas 2 7 25  ==  14

Leer más…

Grafo de divisibilidad

Misceláneas

El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x y el coste de cada arista es el cociente entre su mayos y menor elemento.

Definir las siguientes funciones:

grafoDivisibilidad :: Int -> Grafo Int Int
coste :: Int -> Int

tales que

  • (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
λ> grafoDivisibilidad 12
G ND (array (1,12)
            [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),
                 (8,8),(9,9),(10,10),(11,11),(12,12)]),
             (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),
             (3,[(1,3),(6,2),(9,3),(12,4)]),
             (4,[(1,4),(2,2),(8,2),(12,3)]),
             (5,[(1,5),(10,2)]),
             (6,[(1,6),(2,3),(3,2),(12,2)]),
             (7,[(1,7)]),
             (8,[(1,8),(2,4),(4,2)]),
             (9,[(1,9),(3,3)]),
             (10,[(1,10),(2,5),(5,2)]),
             (11,[(1,11)]),
             (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])
  • (coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,
coste 12    ==  41
coste 3000  ==  605305

Leer más…

Grafo complemenario

Misceláneas

El complementario del grafo G es un grafo G' del mismo tipo que G (dirigido o no dirigido), con el mismo conjunto de nodos y tal que dos nodos de G' son adyacentes si y sólo si no son adyacentes en G. Los pesos de todas las aristas del complementario es igual a 0.

Definir la función

complementario :: Grafo Int Int -> Grafo Int Int

tal que (complementario g) es el complementario de g. Por ejemplo,

λ> complementario (creaGrafo D (1,3) [(1,3,0),(3,2,0),(2,2,0),(2,1,0)])
G D (array (1,3) [(1,[(1,0),(2,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])])
λ> complementario (creaGrafo D (1,3) [(3,2,0),(2,2,0),(2,1,0)])
G D (array (1,3) [(1,[(1,0),(2,0),(3,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])])

Nota: Se usa el módulo Grafo de la librería de I1M.

Leer más…

El problema de las celebridades

Misceláneas

La celebridad de una reunión es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reunión hay tres personas tales que la 1 conoce a la 3 y la 2 conoce a la 1 y a la 3, entonces la celebridad de la reunión es la 3.

La relación de conocimiento se puede representar mediante una lista de pares (x,y) indicando que x conoce a y. Por ejemplo, ka reunioń anterior se puede representar por [(1,3),(2,1),(2,3)].

Definir la función

celebridad :: Ord a => [(a,a)] -> Maybe a

tal que (celebridad r) es el justo la celebridad de r, si en r hay una celebridad y Nothing, en caso contrario. Por ejemplo,

celebridad [(1,3),(2,1),(2,3)]            ==  Just 3
celebridad [(1,3),(2,1),(3,2)]            ==  Nothing
celebridad [(1,3),(2,1),(2,3),(3,1)]      ==  Nothing
celebridad [(x,1) | x <- [2..10^6]]       ==  Just 1
celebridad [(x,10^6) | x <- [1..10^6-1]]  ==  Just 1000000

Leer más…

Pares a distancia dada

Misceláneas

Definir la función

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

tal que (pares xs k) es la lista de pares de elementos de xs que están a distancia k (se supone que los elementos de xs son distintos). Por ejemplo,

pares [1,5,3,4,2,8] 2       ==  [(1,3),(3,5),(2,4)]
length (pares [1..10^6] 3)  ==  999997

Leer más…

Problema de las 3 jarras

Misceláneas

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…

Suma de árboles por niveles

Misceláneas

Los árboles binarios con valores enteros se pueden representar con el de tipo de dato algebraico

data Arbol = H
           | N a Arbol Arbol

Por ejemplo, los árboles

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

se representan por

ej1, ej2 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))

Definir la función

suma :: Arbol -> Int

tal que (suma a) es la suma de todos los nodos a una distancia par de la raíz del árbol a menos la suma de todos los nodos a una distancia impar de la raíz. Por ejemplo,

suma ej1  ==  6
suma ej2  ==  4

ya que

(3 + 1+3+5) - (2+4)        = 6
(7 + 6+4+10) - (5+8 + 9+1) = 4

Leer más…

Normalización de expresiones aritméticas

Misceláneas

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

data Expr = Var String
          | S Expr Expr
          | P Expr Expre
          deriving (Eq, Show)

Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z) y x+(y*z) están en forma normal; pero x*(y+z) y (x+y)*(x+z) no lo están.

Definir la función

esTermino :: Expr -> Bool
esTermino :: Expr -> Bool
normal    :: Expr -> Expr

tales que

  • (esTermino a) se verifica si a es un término. Por ejemplo,
esTermino (V "x")                         == True
esTermino (P (V "x") (P (V "y") (V "z"))) == True
esTermino (P (V "x") (S (V "y") (V "z"))) == False
esTermino (S (V "x") (P (V "y") (V "z"))) == False
  • (esNormal a) se verifica si a está en forma normal. Por ejemplo,
esNormal (V "x")                                     == True
esNormal (P (V "x") (P (V "y") (V "z")))             == True
esNormal (S (V "x") (P (V "y") (V "z")))             == True
esNormal (P (V "x") (S (V "y") (V "z")))             == False
esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True
  • (normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:
(a+b)*c = a*c+b*c
c*(a+b) = c*a+c*b

Por ejemplo,

λ> normal (P (S (V "x") (V "y")) (V "z"))
S (P (V "x") (V "z")) (P (V "y") (V "z"))
λ> normal (P (V "z") (S (V "x") (V "y")))
S (P (V "z") (V "x")) (P (V "z") (V "y"))
λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))
S (S (P (V "x") (V "u")) (P (V "x") (V "v")))
   (S (P (V "y") (V "u")) (P (V "y") (V "v")))
λ> normal (S (P (V "x") (V "y")) (V "z"))
S (P (V "x") (V "y")) (V "z")
λ> normal (V "x")
V "x"

Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).

Nota. Para la comprobación se usará el siguiente generador de expresiones aritméticas

import Test.QuickCheck
import Control.Monad

instance Arbitrary Expr where
  arbitrary = sized arb
    where
      arb 0         = liftM V arbitrary
      arb n | n > 0 = oneof [liftM V arbitrary,
                             liftM2 S sub sub,
                             liftM2 P sub sub]
        where sub = arb (n `div` 2)

Leer más…

Recorrido en ZigZag

Misceláneas

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…

Sucesión de Recamán

Misceláneas

La sucesión de Recamán está definida como sigue:

a(0) = 0
a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

sucRecaman :: [Int]
invRecaman :: Int -> Int
graficaSucRecaman :: Int -> IO ()
graficaInvRecaman :: Int -> IO ()

tales que

  • sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,
λ> take 25 sucRecaman3
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
λ> sucRecaman !! 1000
3686
λ> sucRecaman !! 1000001
1057163
  • (invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,
invRecaman 10       ==  12
invRecaman 3686     ==  1000
invRecaman 1057163  ==  1000001
  • (graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja

Sucesión de Recamán

  • (graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja

Sucesión de Recamán

y (graficaInvRecaman 100) dibuja

Sucesión de Recamán

Leer más…

Operaciones con series de potencias

Misceláneas

Una serie de potencias es una serie de la forma

a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

type Serie a = [a]

Definir las siguientes funciones

opuesta      :: Num a => Serie a -> Serie a
suma         :: Num a => Serie a -> Serie a -> Serie a
resta        :: Num a => Serie a -> Serie a -> Serie a
producto     :: Num a => Serie a -> Serie a -> Serie a
cociente     :: Fractional a => Serie a -> Serie a -> Serie a
derivada     :: (Num a, Enum a) => Serie a -> Serie a
integral     :: (Fractional a, Enum a) => Serie a -> Serie a
expx         :: Serie Rational

tales que

  • (opuesta xs) es la opuesta de la serie xs. Por ejemplo,
λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]
  • (suma xs ys) es la suma de las series xs e ys. Por ejemplo,
λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]
  • (resta xs ys) es la resta de las series xs es ys. Por ejemplo,
λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]
  • (producto xs ys) es el producto de las series xs e ys. Por ejemplo,
λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]
  • (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,
λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]
  • (derivada xs) es la derivada de la serie xs. Por ejemplo,
λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]
  • (integral xs) es la integral de la serie xs. Por ejemplo,
λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]
  • expx es la serie de la función exponencial. Por ejemplo,
λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Leer más…

Operaciones con polinomios como diccionarios

Misceláneas

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

3 + 7x - 5x^3
4 + 5x^3 + x^5

se definen por

ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

  • (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,
λ> sumaPol ejPol1 ejPol2
fromList [(0,7),(1,7),(5,1)]
λ> sumaPol ejPol1 ejPol1
fromList [(0,6),(1,14),(3,-10)]
  • (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,
λ> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
fromList [(2,12),(4,3)]
  • (multPol p q) es el producto de los polinomios p y q. Por ejemplo,
λ> multPol ejPol1 ejPol2
fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
λ> multPol ejPol1 ejPol1
fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
λ> multPol ejPol2 ejPol2
fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Leer más…

Números como sumas de primos consecutivos.

Misceláneas

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
311 =  53 +  59 +  61 + 67 + 71
311 = 101 + 103 + 107
311 = 311

el número 41 se puede escribir de 4 formas

41 =  2 +  3 +  5 + 7 + 11 + 13
41 = 11 + 13 + 17
41 = 41

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,

λ> sumas 311
[[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
[53,59,61,67,71],[101,103,107],[311]]
λ> sumas 41
[[2,3,5,7,11,13],[11,13,17],[41]]
λ> sumas 14
[]
λ> [length (sumas n) | n <- [0..20]]
[0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0]
λ> maximum [length (sumas n) | n <- [1..600]]
5

Leer más…

Subnúmeros pares

Misceláneas

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

subnumeros       :: Integer -> [Integer]
nSubnumerosPares :: Integer -> Integer

tales que

  • (subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,
subnumerosPares 254   ==  [2,254,54,4]
subnumerosPares 154   ==  [154,54,4]
subnumerosPares 15    ==  []
  • (nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,
nSubnumerosPares 254   ==  4
nSubnumerosPares2 (4^(10^6))  ==  90625258498

Soluciones

import Data.List ( genericLength
                 , inits
                 , tails
                 )

subnumerosPares :: Integer -> [Integer]
subnumerosPares n =
  filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,
--    subnumeros 254  ==  [2,25,5,254,54,4]
subnumeros :: Integer -> [Integer]
subnumeros n =
  [read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,
--    sublistas "abc"  ==  ["a","ab","b","abc","bc","c"]
sublistas :: [a] -> [[a]]
sublistas xs =
  concat [init (tails ys) | ys <- tail (inits xs)]

-- 1ª definición
-- =============

nSubnumerosPares :: Integer -> Integer
nSubnumerosPares =
  genericLength . subnumerosPares

-- 2ª definición
-- =============

nSubnumerosPares2 :: Integer -> Integer
nSubnumerosPares2 =
  sum . posicionesDigitosPares

-- (posicionesDigitosPares x) es la lista de las posiciones de los
-- dígitos pares de x. Por ejemplo,
--    posicionesDigitosPares 254  ==  [1,3]
posicionesDigitosPares :: Integer -> [Integer]
posicionesDigitosPares x =
  [n | (n,y) <- zip [1..] (show x)
     , y `elem` "02468"]

-- Comparación de eficiencia
--    λ> nSubnumerosPares (2^(10^3))
--    22934
--    (2.83 secs, 3,413,414,872 bytes)
--    λ> nSubnumerosPares2 (2^(10^3))
--    22934
--    (0.01 secs, 0 bytes)

Elementos con su doble en el conjunto.

Misceláneas

Definir la función

conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
conDoble [2, 4, 8, 10]               ==  [2,4]
conDoble [7, 5, 11, 13, 1, 3]        ==  []
length (conDoble4 [1..10^6])         ==  500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Leer más…

Buscaminas

Misceláneas

El buscaminas es un juego cuyo objetivo es despejar un campo de minas sin detonar ninguna.

El campo de minas se representa mediante un cuadrado con NxN casillas. Algunas casillas tienen un número, este número indica las minas que hay en todas las casillas vecinas. Cada casilla tiene como máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda contiene dos minas, cada una representada por el número 9, y a la derecha se muestra el campo obtenido anotando las minas vecinas de cada casilla

9 0 0 0       9 1 0 0
0 0 0 0       2 2 1 0
0 9 0 0       1 9 1 0
0 0 0 0       1 1 1 0

de la misma forma, la anotación del siguiente a la izquierda es el de la derecha

9 9 0 0 0     9 9 1 0 0
0 0 0 0 0     3 3 2 0 0
0 9 0 0 0     1 9 1 0 0

En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra en aquí.

Los campos de minas se representan mediante matrices:

type Campo = Matrix Int

Por ejemplo, los anteriores campos de la izquierda se definen por

ejCampo1, ejCampo2 :: Campo
ejCampo1 = fromLists [[9,0,0,0],
                      [0,0,0,0],
                      [0,9,0,0],
                      [0,0,0,0]]
ejCampo2 = fromLists [[9,9,0,0,0],
                      [0,0,0,0,0],
                      [0,9,0,0,0]]

Definir la función

buscaminas :: Campo -> Campo

tal que (buscaminas c) es el campo obtenido anotando las minas vecinas de cada casilla. Por ejemplo,

λ> buscaminas ejCampo1
( 9 1 0 0 )
( 2 2 1 0 )
( 1 9 1 0 )
( 1 1 1 0 )

λ> buscaminas ejCampo2
( 9 9 1 0 0 )
( 3 3 2 0 0 )
( 1 9 1 0 0 )

Leer más…

Clases de equivalencia

Misceláneas

Definir la función

clasesEquivalencia :: Ord a =>
                      Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

λ> let c = fromList [-3..3]
λ> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
λ> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Leer más…

Ampliación de una matriz

Misceláneas

Definir, usando Data.Matrix, la función

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

ej1 :: Matrix Char
ej1 = fromLists [" x ",
                 "x x",
                 " x "]

entonces

λ> ampliaMatriz ej1 1 2
( ' ' ' ' 'x' 'x' ' ' ' ' )
( 'x' 'x' ' ' ' ' 'x' 'x' )
( ' ' ' ' 'x' 'x' ' ' ' ' )

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)
  xx
xx  xx
  xx
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)
 x
 x
x x
x x
 x
 x
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)
  xx
  xx
xx  xx
xx  xx
  xx
  xx
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)
   xxx
   xxx
xxx   xxx
xxx   xxx
   xxx
   xxx

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Leer más…

Problema de las jarras

Misceláneas

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

jarras :: (Int,Int,Int) -> Maybe [(Int,Int)]

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> jarras (5,3,4)
Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]

La interpretación de la solución anterior es

(0,0) se inicia con las dos jarras vacías,
(5,0) se llena la jarra de 5 con el grifo,
(2,3) se llena la de 3 con la de 5,
(2,0) se vacía la de 3,
(0,2) se pasa el contenido de la primera a la segunda,
(5,2) se llena la primera con el grifo,
(4,3) se llena la segunda con la primera.

Otros ejemplos:

λ> jarras (3,5,4)
Just [(0,0),(0,5),(3,2),(0,2),(2,0),(2,5),(3,4)]
λ> jarras (15,10,5)
Just [(0,0),(15,0),(5,10)]
λ> jarras (15,10,4)
Nothing
λ> length <$> jarras (181,179,100)
Just 199

Leer más…

El problema de las N torres

Misceláneas

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…

Densidades de números abundantes, perfectos y deficientes

Misceláneas

La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.

Definir las funciones

densidades :: Int -> (Double,Double,Double)
graficas   :: Imt -> IO ()

tales que

  • (densidades n) es la terna formada por la n-ésima densidad de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,
densidades 100     ==  (0.22,    2.0e-2, 0.76)
densidades 1000    ==  (0.246,   3.0e-3, 0.751)
densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)
densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)
  • (graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

Densidades de números abundantes, perfectos y deficientes

y (graficas 400) dibuja

Densidades de números abundantes, perfectos y deficientes

Leer más…

Enumeración de árboles binarios

Misceláneas

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

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

Por ejemplo, el árbol

      "B"
      / \
     /   \
    /     \
  "B"     "A"
  / \     / \
"A" "B" "C" "C"

se puede definir por

ej1 :: Arbol String
ej1 = N "B" (N "B" (H "A") (H "B")) (N "A" (H "C") (H "C"))

Definir la función

enumeraArbol :: Arbol t -> Arbol Int

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

λ> enumeraArbol ej1
N 6 (N 2 (H 0) (H 1)) (N 5 (H 3) (H 4))

Gráficamente,

      6
     / \
    /   \
   /     \
  2       5
 / \     / \
0   1   3   4

Leer más…

Agrupamiento según valores

Misceláneas

Definir la función

agrupa :: Ord c => (a -> c) -> [a] -> Map c [a]

tal que (agrupa f xs) es el diccionario obtenido agrupando los elementos de xs según sus valores mediante la función f. Por ejemplo,

λ> agrupa length ["hoy", "ayer", "ana", "cosa"]
fromList [(3,["hoy","ana"]),(4,["ayer","cosa"])]
λ> agrupa head ["claro", "ayer", "ana", "cosa"]
fromList [('a',["ayer","ana"]),('c',["claro","cosa"])]

Leer más…

Distancias entre primos consecutivos

Misceláneas

Los 15 primeros números primos son

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

La distribución de las distancias es

(1,1), (2,6), (4,5), (6,2)

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

cuentaDistancias        :: Int -> [(Int,Int)]
frecuenciasDistancias   :: Int -> [(Int,Float)]
graficas                :: [Int] -> IO ()
distanciasMasFrecuentes :: Int -> [Int]

tales que

  • (cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,
λ> cuentaDistancias 15
[(1,1),(2,6),(4,5),(6,2)]
λ> cuentaDistancias 100
[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]
  • (frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,
λ> frecuenciasDistancias 15
[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
λ> frecuenciasDistancias 30
[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]
  • (graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

Distancias entre primos consecutivos

(graficas [x*10^3 | x <- [1,2,3]]) dibuja

Distancias entre primos consecutivos

y (graficas [x*10^5 | x <- [1,2,3]]) dibuja

Distancias entre primos consecutivos

  • (distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,
distanciasMasFrecuentes 15   ==  [2]
distanciasMasFrecuentes 26   ==  [2,4]
distanciasMasFrecuentes 32   ==  [4]
distanciasMasFrecuentes 41   ==  [2,4,6]
distanciasMasFrecuentes 77   ==  [6]
distanciasMasFrecuentes 160  ==  [4,6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Leer más…

Rotaciones divisibles por 4

Misceláneas

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816. De las cuales, las divisibles por 4 son 928160, 816092, 160928 y 92816.

Definir la función

nRotacionesDivisibles :: Integer -> Int

tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,

nRotacionesDivisibles 928160          ==  4
nRotacionesDivisibles 44              ==  2
nRotacionesDivisibles (1234^50000)    ==  38684
nRotacionesDivisibles (1234^300000)   ==  231853

Leer más…

Potencias perfectas

Misceláneas

Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son

4 = 2², 8 = 2³, 9 = 3², 16 = 2⁴, 25 = 5², 27 = 3³, 32 = 2⁵,
36 = 6², 49 = 7², 64 = 2⁶, ...

Definir la sucesión

potenciasPerfectas :: [Integer]

cuyos términos son las potencias perfectas. Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 100   ==  6724

Definir el procedimiento

grafica :: Int -> IO ()

tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja

!Potencias perfectas](/images/Potencias_perfectas.png)

Leer más…

Sumas con sumandos distintos o con sumandos impares

Misceláneas

El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:

6 = 1 + 2 + 3
6 = 1 + 5
6 = 2 + 4
6 = 6

y también se puede descomponer de 4 formas distintas como suma con sumandos impares:

6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 3
6 = 1 + 5
6 = 3 + 3

Definir las siguientes funciones

sumasSumandosDistintos  :: Integer -> [[Integer]]
nSumasSumandosDistintos :: Integer -> Int
sumasSumandosImpares    :: Integer -> [[Integer]]
nSumasSumandosImpares   :: Integer -> Int
igualdadDeSumas         :: Integer -> Bool

tales que

  • (sumasSumandosDistintos n) es la lista de las descomposiciones de n como sumas con sumandos distintos. Por ejemplo,
sumasSumandosDistintos 5  ==  [[1,4],[2,3],[5]]
sumasSumandosDistintos 6  ==  [[1,2,3],[1,5],[2,4],[6]]
  • (nSumasSumandosDistintos n) es el número de descomposiciones de n como sumas con sumandos distintos. Por ejemplo,
nSumasSumandosDistintos 6  ==  4
nSumasSumandosDistintos 7  ==  5
  • (sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,
sumasSumandosImpares 5  ==  [[1,1,1,1,1],[1,1,3],[5]]
sumasSumandosImpares 6  ==  [[1,1,1,1,1,1],[1,1,1,3],[1,5],[3,3]]
  • (nSumasSumandosImpares n) es el número de descomposiciones de n como sumas con sumandos impares. Por ejemplo,
nSumasSumandosImpares 6  ==  4
nSumasSumandosImpares 7  ==  5
  • (igualdadDeSumas n) se verifica si, para todo k entre 1 y n, las funciones nSumasSumandosDistintos y nSumasSumandosImpares son iguales. Por ejemplo,
igualdadDeSumas 40  ==  True

Leer más…

Término ausente en una progresión aritmética.

Misceláneas

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]                ==  5
ausente [3,5,9,11]                ==  7
ausente [3,5,7,11]                ==  9
ausente ([1..9]++[11..])          ==  10
ausente2 ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay exactamente un término de la progresión aritmética que no está en la lista.

Leer más…

El problema del reciclado

Misceláneas

El problema del reciclado del reciclado N P consiste en lo siguiente: un grupo de personas disponen de N botellas de refresco vacía y las llevan a reciclar obteniendo una botella llena por cada P vacías; se beben inmediatamente el contenido de las botellas obtenidas y sus botellas vacías, junto con las no recicladas anteriormente, las canjean por botellas llenas. El proceso continúa hasta que no tienen suficientes botellas para canjear. El objetivo del problema es calcular el número de botellas que se han bebido.

Por ejemplo, si disponen de 10 botellas y por cada 2 obtienen 1, se producen cuatro canjeos:

  • en el primer canjeo entregan las 10 y obtienen 5;
  • en el segundo, entregan 4, le quedan 1 y obtienen 2;
  • en el tercero, entregan 2, le queda 1 y obtienen 1;
  • en el cuarto, entregan 2 y obtienen 1.

Por tanto, se han bebido 9 y le quedan 1 que no pueden canjear.

Definir la función

reciclado :: Int -> Int -> Int

tal que (reciclado n p) es el número de botellas que se beben en el reciclado comenzado con n botellas y canjeando p botellas vacías por una llena. Por ejemplo,

reciclado  9 3  ==  4
reciclado 10 2  ==  9

Leer más…

Orden simétrico

Misceláneas

Dada una lista de cadenas ordenadas por longitud, se puede ordenar de manera simétrica colocando la primera cadena en primer lugar, la segunda en el último, la tercera en el segundo, la cuarta en el penúltimo y así sucesivamente.

Por ejemplo, dada la lista

Pi
Eva
Luis
Paula
Alberto
Francisco

su ordenación simétrica es

Pi
Luis
Alberto
Francisco
Paula
Eva

Definir la función

simetrica :: [String] -> [String]

tal que (simetrica xs) es la ordenación simétrica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,

λ> simetrica ["Pi","Eva","Luis","Paula","Alberto","Francisco"]
["Pi","Luis","Alberto","Francisco","Paula","Eva"]
λ> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^6]]
"a"

Nota: Este ejercicio está basado en el problema Symmetric order de Kattis.

Leer más…

Puntos alcanzables en un mapa

Misceláneas

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…

Número de dígitos del factorial

Misceláneas

Definir las funciones

nDigitosFact :: Integer -> Integer
graficas     :: [Integer] -> IO ()

tales que

  • (nDigitosFact n) es el número de dígitos de n!. Por ejemplo,
nDigitosFact 0        ==  1
nDigitosFact 4        ==  2
nDigitosFact 5        ==  3
nDigitosFact 10       ==  7
nDigitosFact 100      ==  158
nDigitosFact 1000     ==  2568
nDigitosFact 10000    ==  35660
nDigitosFact 100000   ==  456574
nDigitosFact 1000000  ==  5565709
  • (graficas xs) dibuja las gráficas de los números de dígitos del factorial de k (para k en xs) y de la recta y = 5.5 x. Por ejemplo, (graficas [0,500..10^6]) dibuja

Número de dígitos del factorial

Nota: Este ejercicio está basado en el problema How many digits? de Kattis en donde se impone la restricción de calcular, en menos de 1 segundo, el número de dígitos de los factoriales de 10.000 números del rango [0,1.000.000].

Se puede simular como sigue

λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> maximum (map nDigitosFact4 xs)
5561492
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> maximum (map nDigitosFact4 xs)
5563303

Leer más…

Representación de conjuntos mediante intervalos

Misceláneas

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

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

tal que (intervalos xs) es lista ordenada de intervalos que representa al conjunto xs. Por ejemplo,

intervalos [2,7,4,3,9,6]  ==  [(2,4),(6,7),(9,9)]

Nota: Este ejercicio está basado en el problema Bus numbers de Kattis

Leer más…

Codificación matricial

Misceláneas

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

  • Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
  • Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
  • Se extiende el mensaje con N²-L puntos. En el ejemplo, el mensaje extendido es "todoparanada····"
  • Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es
| t o d o |
| p a r a |
| n a d a |
| · · · · |
  • Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es
| · n p t |
| · a a o |
| · d r d |
| · a a o |
  • Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "·npt·aap·drd·aao"
  • El mensaje codificado se obtiene eliminando los puntos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

codificado :: String -> String

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

codificado "todoparanada"    ==  "nptaaodrdaao"
codificado "nptaaodrdaao"    ==  "danaopadtora"
codificado "danaopadtora"    ==  "todoparanada"
codificado "entodolamedida"  ==  "dmdeaeondltiao"

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Leer más…

Suma de subconjuntos

Misceláneas

Los subconjuntos de [1, 4, 2] son

[], [1], [4], [1, 4], [2], [1, 2], [4, 2], [1, 4, 2]

Las sumas de sus elementos son

0, 1, 4, 5, 2, 3, 6, 7

Y la suma de las sumas es 28.

Definir la función

sumaSubconjuntos :: [Integer] -> Integer

tal que (sumaSubconjuntos xs) es la suma de las sumas de los subconjuntos de xs. Por ejemplo,

sumaSubconjuntos [1,2]                     == 6
sumaSubconjuntos [1,4,2]                   == 28
length (show (sumaSubconjuntos [1..10^6])) == 301042

Leer más…

Por 3 o más 5

Misceláneas

El enunciado del problema Por 3 o más 5 de ¡Acepta el reto! es el siguiente

Cuenta la leyenda que un famoso matemático, tras aprender a sumar y multiplicar a la tierna edad de 3 años en apenas 5 días, se dio cuenta de que, empezando por 1, podía generar un montón de números sin más que multiplicar por 3 o sumar 5 a alguno de los que ya hubiera generado antes.

Por ejemplo, el 23 (edad a la que se casaría) lo obtuvo así: ((1 + 5) × 3) + 5 Por su parte el 77 (edad a la que tendría su primer bisnieto) lo consiguió: (((1 × 3 + 5) × 3) × 3) + 5

Por mucho que lo intentó, algunos números, sin embargo, resultaron ser imposibles de obtener, como por ejemplo el 5, el 7 o el 15.

Se dice que un número es generable si se puede escribir como una sucesión (quizá vacía) de multiplicaciones por 3 y sumas de 5 al número 1.

Definir las siguientes funciones

generables     :: [Integer]
generable      :: Integer -> Bool
arbolGenerable :: Integer -> Tree Integer

tales que

  • generables es la sucesión de los números generables. Por ejemplo,
λ> take 20 generables
[1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]
λ> generables !! (10^6)
1250008
  • (generable x) se verifica si x es generable. Por ejemplo,
generable 23       ==  True
generable 77       ==  True
generable 15       ==  False
generable 1250008  ==  True
generable 1250010  ==  False
  • (arbolGenerable x) es el árbol de los números generables menores o iguales a x. Por ejemplo,
λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))
1
|
+- 3
|  |
|  +- 9
|  |
|  `- 8
|
`- 6
   |
   `- 11

Leer más…

Números cubifinitos

Misceláneas

El enunciado del problema Números cubifinitos de ¡Acepta el reto! es el siguiente

Se dice que un número es cubifinito cuando al elevar todos sus dígitos al cubo y sumarlos el resultado o bien es 1 o bien es un número cubifinito.

Por ejemplo, el número 1243 es cubifinito, pues al elevar todos sus dígitos al cubo obtenemos 100 que es cubifinito.

Por su parte, el 513 no es cubifinito, pues al elevar al cubo sus dígitos conseguimos el 153 que nunca podrá ser cubifinito, pues la suma de los cubos de sus dígitos vuelve a dar 153.

Definir las funciones

esCubifinito :: Int -> Bool
grafica :: Int -> IO ()

tales que

  • (esCubifinito n) se verifica si n es un número cubifinito. Por ejemplo,
esCubifinito 1      ==  True
esCubifinito 10     ==  True
esCubifinito 1243   ==  True
esCubifinito 87418  ==  True
esCubifinito 513    ==  False
  • (grafica n) dibuja la gráfica de la sucesión de los primeros n números cubifinitos. Por ejemplo, al evaluar (grafica 50) se dibuja

Números cubifinitos

Leer más…

Distribución de diferencias de dígitos consecutivos de pi

Misceláneas

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

Las diferencias de sus elementos consecutivos es

2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

distribucionDDCpi :: Int -> [Int]
graficas :: [Int] -> FilePath -> IO ()

tales que

  • (distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,
λ> distribucionDDCpi 18
[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
λ> distribucionDDCpi 100
[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
λ> distribucionDDCpi 200
[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
λ> distribucionDDCpi 1000
[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
λ> distribucionDDCpi 5000
[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]
  • (graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] "distribucionDDCpi.png" se escribe en el fichero "distribucionDDCpi.png" la siguiente gráfica

Distribución de diferencias de dígitos consecutivos de pi

Nota: Se puede usar la librería Data.Number.CReal.

Leer más…